powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Пятница. Ice Bucket Challenge
3 сообщений из 3, страница 1 из 1
Пятница. Ice Bucket Challenge
    #38861309
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Доброго времени суток, Сообщество 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
Пятница. Ice Bucket Challenge
    #38861693
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему назвал "Облако" ?
...
Рейтинг: 0 / 0
Пятница. Ice Bucket Challenge
    #38862205
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Облако всех возможных вариантов. Такое название мне показалось логичным :)
...
Рейтинг: 0 / 0
3 сообщений из 3, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Пятница. Ice Bucket Challenge
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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