• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/TCO16-2A-U/1A-U.cpp version [f1735c1808f6c994]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class LCMGCD { public:
           23  + string isPossible(vector <int> x, int t)
           24  + {
           25  +  pair<int,int> tt = crack(t);
           26  +  vector<pair<int,int>> ab;
           27  +  for(int xi: x) {
           28  +   pair<int, int> xx = crack(xi);
           29  +   ab.emplace_back(sign(xx.first, tt.first), sign(xx.second, tt.second));
           30  +  }
           31  +  return solve(ab) ? "Possible" : "Impossible";
           32  + }
           33  +
           34  + pair<int,int> crack(int x)
           35  + {
           36  +  int a=0, b=0;
           37  +  while(x%2==0) x/=2, a++;
           38  +  while(x%3==0) x/=3, b++;
           39  +  return make_pair(a,b);
           40  + }
           41  +
           42  + int sign(int x, int t)
           43  + {
           44  +  return x<t ? 0 : x==t ? 1 : 2;
           45  + }
           46  +
           47  + // can we make (1,1) by max and min?
           48  + bool solve(vector<pair<int,int>> x)
           49  + {
           50  +  set<vector<int>> vis;
           51  +  vector<int> sig(7);
           52  +  vis.insert(sig);
           53  +
           54  +  for(auto ab: x) {
           55  +   int s = ab.first*3 + ab.second;
           56  +   if(0<s&&s<8)
           57  +    if(sig[s-1]<5)
           58  +     sig[s-1]++;
           59  +  }
           60  +  goal = vector<int>(7); goal[3]=1;
           61  +  return rec(sig, vis);
           62  + }
           63  +
           64  + vector<int> goal;
           65  + bool rec(vector<int>& sig, set<vector<int>>& vis)
           66  + {
           67  +  if(sig[3] >= 2)
           68  +   return true;
           69  +  if(sig == goal)
           70  +   return true;
           71  +
           72  +  if(vis.count(sig))
           73  +   return false;
           74  +  vis.insert(sig);
           75  +
           76  +  for(int a=1; a<8; ++a) if(sig[a-1])
           77  +  for(int b=a; b<8; ++b) if(sig[b-1]) {
           78  +   if(b==a && sig[a-1]==1) continue;
           79  +   sig[a-1]--;
           80  +   sig[b-1]--;
           81  +   int z = max(a/3,b/3)*3 + max(a%3,b%3);
           82  +   if(0<z && z<8) {
           83  +    sig[z-1]++;
           84  +    if(rec(sig, vis)) return true;
           85  +    sig[z-1]--;
           86  +   } else {
           87  +    if(rec(sig, vis)) return true;
           88  +   }
           89  +   z = min(a/3,b/3)*3 + min(a%3,b%3);
           90  +   if(0<z && z<8) {
           91  +    sig[z-1]++;
           92  +    if(rec(sig, vis)) return true;
           93  +    sig[z-1]--;
           94  +   } else {
           95  +    if(rec(sig, vis)) return true;
           96  +   }
           97  +   sig[a-1]++;
           98  +   sig[b-1]++;
           99  +  }
          100  +  return false;
          101  + }
          102  +};
          103  +
          104  +// BEGIN CUT HERE
          105  +#include <ctime>
          106  +double start_time; string timer()
          107  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          108  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          109  + { os << "{ ";
          110  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          111  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          112  +void verify_case(const string& Expected, const string& Received) {
          113  + bool ok = (Expected == Received);
          114  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          115  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          116  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          117  +#define END  verify_case(_, LCMGCD().isPossible(x, t));}
          118  +int main(){
          119  +
          120  +CASE(0)
          121  + int x_[] = {2,3};
          122  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          123  + int t = 6;
          124  + string _ = "Possible";
          125  +END
          126  +CASE(1)
          127  + int x_[] = {4,9};
          128  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          129  + int t = 6;
          130  + string _ = "Impossible";
          131  +END
          132  +CASE(2)
          133  + int x_[] = {6,12,24,18,36,72,54,108,216};
          134  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          135  + int t = 36;
          136  + string _ = "Possible";
          137  +END
          138  +CASE(3)
          139  + int x_[] = {6,27,81,729};
          140  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          141  + int t = 6;
          142  + string _ = "Impossible";
          143  +END
          144  +CASE(4)
          145  + int x_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
          146  + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
          147  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          148  + int t = 1;
          149  + string _ = "Possible";
          150  +END
          151  +CASE(5)
          152  + int x_[] = {72,16,16,16,16,16,27,27,27,27,27,27,27,27,27};
          153  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          154  + int t = 72;
          155  + string _ = "Possible";
          156  +END
          157  +CASE(6)
          158  + int x_[] = {100663296, 544195584, 229582512, 59049};
          159  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          160  + int t = 60466176;
          161  + string _ = "Possible";
          162  +END
          163  +CASE(7)
          164  + int x_[] = {2,4,8,16,32,64};
          165  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          166  + int t = 256;
          167  + string _ = "Impossible";
          168  +END
          169  +CASE(8)
          170  + int x_[] = {6,9};
          171  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          172  + int t = 6;
          173  + string _ = "Impossible";
          174  +END
          175  +CASE(9)
          176  + int x_[] = {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
          177  + 18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18};
          178  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          179  + int t = 6;
          180  + string _ = "Impossible";
          181  +END
          182  +CASE(8)
          183  + int x_[] = {6,6,9};
          184  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          185  + int t = 6;
          186  + string _ = "Possible";
          187  +END
          188  +CASE(8)
          189  + int x_[] = {9,18,12};
          190  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          191  + int t = 6;
          192  + string _ = "Possible";
          193  +END
          194  +}
          195  +// END CUT HERE