Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Пятница. Ice Bucket Challenge / 3 сообщений из 3, страница 1 из 1
23.01.2015, 04:14
    #38861309
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятница. Ice Bucket Challenge
Доброго времени суток, Сообщество C:

Сегодня разминался (всё жду когда один товарищ принесёт мне Страуструпа), и решал одну задачу .
Не сложно решить её перебором:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
#include <stdio.h>
#include <stdlib.h>

#define COUNT_BUCKET 3

int max[3];//вместимость трёх ведер

int mix2bucket(int v, int i, int j) //i<-j  v-текущее состояние трёх вёдер, переливаем из ведра j в ведро i  
{
	int res[COUNT_BUCKET];
	res[0] = v % 1000;
	res[1] = ((v - res[0]) / 1000) % 1000;
	res[2] = ((v - res[0] - 1000 * res[1]) / 1000000);

	int sh1 = max[i] - res[i];
	int sh2 = max[j] - res[j];
	
	if (sh1 >= res[j])
	{
		res[i] += res[j];
		res[j] = 0;
	}
	else
	{
		res[i] += sh1;
		res[j] -= sh1;
	}
	return res[0] + 1000 * res[1] + 1000000 * res[2];
}

struct Cloud
{
	int size;
	int levels;
	int count_on_ll;//количество элементов на последнем уровне
	int* ar;
};

int addtoCloud(struct Cloud* cloud, int v)
{
	for (int i = 0; i < cloud->size; ++i)//проверка на то, что такой элемент уже существует в облаке
	{
		if (cloud->ar[i] == v)
			return -1;
	}
	cloud->size += 1;
	cloud->count_on_ll += 1;
	cloud->ar = (int*)realloc(cloud->ar, cloud->size*sizeof(int));
	cloud->ar[cloud->size - 1] = v;
	return 0;
}

struct Cloud* createCloud(int v)
{
	struct Cloud* cloud = (struct Cloud*)malloc(sizeof(Cloud));
	cloud->size = 3;
	cloud->levels = 1;
	cloud->count_on_ll = 2;
	cloud->ar = NULL;
	cloud->ar = (int*)malloc(sizeof(int)* 3);
	cloud->ar[0] = v;

	cloud->ar[1] = mix2bucket(v, 1, 0);
	cloud->ar[2] = mix2bucket(v, 2, 0);
	return cloud;
}


int main()
{
	//reading data
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int t;//требуемый объём
	//установка максимальных значений облака
	for (int i = 0; i < COUNT_BUCKET; ++i)
	{
		fscanf(in, "%i", &max[i]);
	}
	fscanf(in, "%i", &t);
	fclose(in);


	//data processing
	struct Cloud* cloud = createCloud(max[0]);
	while (cloud->count_on_ll)//до тех пор пока добавляются новые комбинации
	{
		for (int i = cloud->size - cloud->count_on_ll; i < cloud->size; ++i)//проверка на то, что искомая комбинация найдена на предыдущем уровне
		{
			if (t == cloud->ar[i] % 1000)//если решение найдено
				goto end_looploop;
		}

		cloud->levels += 1;
		int shift = cloud->count_on_ll;
		int end = cloud->size;
		cloud->count_on_ll = 0;
		for (int i = cloud->size - shift; i < end; ++i) //цикл по последним добавленным вариантам
		{
			for (int k = 0; k < COUNT_BUCKET; ++k) //делаю все возможные переливания
			{
				for (int g = 0; g < COUNT_BUCKET; ++g)
				{
					if (g != k)
						addtoCloud(cloud, mix2bucket(cloud->ar[i], k, g));
				}
			}
		}
	}

	if (1)
	{
		fprintf(out, "IMPOSSIBLE");
	}
	else
	{
	end_looploop:;
		fprintf(out, "%i", cloud->levels);
	}
	fclose(out);
	free(cloud->ar);
	free(cloud);
	return 0;
}




Но я уверен, что у неё существует нормальное аналитическое решение. Было бы интересно его найти. У меня сразу не получилось. Возможно кто-нибудь предложит свой алгоритм ;)
...
Рейтинг: 0 / 0
23.01.2015, 13:30
    #38861693
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятница. Ice Bucket Challenge
Почему назвал "Облако" ?
...
Рейтинг: 0 / 0
24.01.2015, 06:16
    #38862205
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пятница. Ice Bucket Challenge
Облако всех возможных вариантов. Такое название мне показалось логичным :)
...
Рейтинг: 0 / 0
Форумы / C++ [игнор отключен] [закрыт для гостей] / Пятница. Ice Bucket Challenge / 3 сообщений из 3, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]