Advertisement
Guest User

Untitled

a guest
Mar 5th, 2011
441
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.52 KB | None
  1. /*
  2.     Proof for the problem Harry Potter and the Sorting Hat
  3.  
  4.     Author: Natalia Bondarenko
  5. */
  6. #pragma comment(linker, "/STACK:64000000")
  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. {  
  73.     forn(mask, (1 << 4))
  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.  
  201. void add_letter(int i)
  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]++;
  238.                     add_letter(i);
  239.                     ok = true;
  240.                 }
  241.             }
  242.             if (!ok)
  243.             {
  244.                 forv(i, cur)
  245.                 {
  246.                     if (a[i] == 0)
  247.                     {
  248.                         a[i]++;
  249.                         add_letter(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. }
Advertisement
RAW Paste Data Copied
Advertisement