# Untitled

a guest
Mar 5th, 2011
441
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2.     Proof for the problem Harry Potter and the Sorting Hat
3.
4.     Author: Natalia Bondarenko
5. */
7. #define _CRT_SECURE_NO_WARNINGS
8.
9. #include <iostream>
10. #include <vector>
11. #include <string>
12. #include <map>
13. #include <set>
14. #include <queue>
15. #include <algorithm>
16. #include <cmath>
17. #include <cassert>
18. #include <sstream>
19.
20. using namespace std;
21.
22. #define forn(i, n) for (int i = 0; i < int(n); i++)
23. #define for1(i, n) for (int i = 1; i <= int(n); i++)
24. #define forv(i, v) forn(i, v.size())
25.
26. #define all(x) x.begin(), x.end()
27. #define pb push_back
28. #define mp make_pair
29.
30. #define COUT_FILE "output.txt"
31.
32. #define pi 3.1415926535897932
33.
34. typedef pair<int, int> pii;
35. typedef long long ll;
36. typedef long double ld;
37.
38. #define INF 1000000009
39. #define NMAX 1000006
40.
41. typedef vector<vector<int> > State;
42.
43. int n;
44. State s[NMAX];
45. int prev[NMAX], pval[NMAX];
46. vector<int> pr[NMAX];
47. vector<vector<int> > seq;
48.
49. void rec(vector<int>& v)
50. {
51.     bool finish = false;
52.     forv(i, v)
53.     {
54.         if (v[i] == -1)
55.         {
56.             for (int j = 1; j <= 3; j++)
57.             {
58.                 v[i] = j;
59.                 rec(v);
60.             }
61.             break;
62.             finish = true;
63.         }
64.     }
65.
66.     if (!finish)
67.     {
68.         seq.pb(v);
69.     }
70. }
71. void gen_seq()
72. {
74.     {
75.         if (mask == 0) continue;
76.         vector<int> v;
77.         v.resize(4);
78.         forn(i, 4)
79.         {
80.             if (mask & (1 << i)) v[i] = 0;
81.             else v[i] = -1;
82.         }
83.
84.         rec(v);
85.     }
86. }
87. void init()
88. {
89.     State start;
90.     vector<int> zero;
91.     forn(i, 4) zero.pb(0);
92.     start.pb(zero);
93.
94.     s[n++] = start;
95.     gen_seq();
96.     sort(all(seq));
97. }
98.
99. vector<int> norm(State& a)
100. {
101.     vector<int> r;
102.     forn(i, 4) r.pb(0);
103.
104.     forn(i, 4)
105.     {
106.         int mn = INF;
107.         forv(j, a)
108.         {
109.             mn = min(mn, a[j][i]);
110.         }
111.
112.         r[i] = mn;
113.         forv(j, a)
114.         {
115.             a[j][i] -= mn;
116.         }
117.     }
118.
119.     sort(all(a));
120.     a.erase(unique(all(a)), a.end());
121.
122.     return r;
123. }
124.
125. int max_size = 0;
126.
127. void correct(State b)
128. {
129.     assert(b.size() <= 13);
130.     max_size = max(max_size, (int)b.size());
131.
132.     vector<int> s;
133.     forv(i, b)
134.     {
135.         int sum = 0;
136.         int cnt2 = 0;
137.         forv(j, b[i])
138.         {
139.             sum += b[i][j];
140.             if (b[i][j] == 2) cnt2++;
141.             assert(b[i][j] < 3);
142.         }
143.
144.         s.pb(sum);
145.     }
146.     forv(i, b) assert(s[i] == s[0]);
147. }
148. void apply(vector<int>& a, vector<int>& v, State& b)
149. {
150.     vector<int> cur;
151.     cur.resize(4);
152.     int mn = INF;
153.     forn(i, 4)
154.     {
155.         cur[i] = a[i] + v[i];
156.         mn = min(cur[i], mn);
157.     }
158.
159.     forn(i, 4)
160.     {
161.         if (cur[i] == mn)
162.         {
163.             a[i]++;
164.             b.pb(a);
165.             a[i]--;
166.         }
167.     }
168. }
169.
170. void go(State a, int ind)
171. {
172.     forv(i, seq)
173.     {
174.         State b;
175.         forv(j, a)
176.         {
177.             apply(a[j], seq[i], b);
178.         }
179.         vector<int> rest = norm(b);
180.         bool ok = false;
181.         forn(j, n)
182.         {
183.             if (s[j] == b)
184.             {
185.                 ok = true;
186.                 break;
187.             }
188.         }
189.
190.         if (!ok)
191.         {
192.             prev[n] = ind;
193.             pval[n] = i;
194.             pr[n] = rest;
195.             s[n++] = b;
196.             correct(b);
197.         }
198.     }
199. }
200.
202. {
203.     if (i == 0) printf("G");
204.     if (i == 1) printf("H");
205.     if (i == 2) printf("R");
206.     if (i == 3) printf("S");
207. }
208.
209. void build_test(int i)
210. {
211.     vector<int> s1, s2;
212.     vector<vector<int> > rest;
213.     while (i > 0)
214.     {
215.         s1.pb(prev[i]);
216.         s2.pb(pval[i]);
217.         rest.pb(pr[i]);
218.         i = prev[i];
219.     }
220.     reverse(all(s1));
221.     reverse(all(s2));
222.     reverse(all(rest));
223.
224.     vector<int> a;
225.     forn(i, 4) a.pb(0);
226.
227.     forv(j, s2)
228.     {
229.         vector<int> cur = seq[s2[j]];
230.         while (a != cur)
231.         {
232.             bool ok = false;
233.             forv(i, cur)
234.             {
235.                 if (a[i] < cur[i])
236.                 {
237.                     a[i]++;
239.                     ok = true;
240.                 }
241.             }
242.             if (!ok)
243.             {
244.                 forv(i, cur)
245.                 {
246.                     if (a[i] == 0)
247.                     {
248.                         a[i]++;
250.                     }
251.                 }
252.             }
253.
254.             //norm
255.             int mn = INF;
256.             forv(i, a) mn = min(mn, a[i]);
257.             forv(i, a) a[i] -= mn;
258.         }
259.         printf("?");
260.
261.         forv(i, a) a[i] += rest[j][i];
262.             int mn = INF;
263.             forv(i, a) mn = min(mn, a[i]);
264.             forv(i, a) a[i] -= mn;
265.     }
266. }
267. int main()
268. {
269.     freopen(COUT_FILE, "wt", stdout);
270.
271.     init();
272.
273.     forn(i, n)
274.     {
275.         go(s[i], i);
276.         cerr << n << endl;
277.     }
278.
279.     /*
280.     forn(i, n)
281.     {
282.         if (s[i].size() == 13)
283.         {
284.             build_test(i);
285.             break;
286.         }
287.     }
288.     */
289.
290.     vector<vector<int> > v;
291.     forn(i, n)
292.     {
293.         forv(j, s[i])
294.         {
295.             v.pb(s[i][j]);
296.         }
297.     }
298.
299.     sort(all(v));
300.     v.erase(unique(all(v)), v.end());
301.
302.     forv(i, v)
303.     {
304.         forv(j, v[i])
305.         {
306.             cout << v[i][j] << " ";
307.         }
308.         cout << endl;
309.     }
310.
311.     cout << max_size << endl;
312.
313.     return 0;
314. }