Доброго времени суток, Сообщество C:
Сегодня разминался (всё жду когда один товарищ принесёт мне Страуструпа), и решал одну
задачу .
Не сложно решить её перебором:
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;
}
Но я уверен, что у неё существует нормальное аналитическое решение. Было бы интересно его найти. У меня сразу не получилось. Возможно кто-нибудь предложит свой алгоритм ;)
