Overview
| SHA1 Hash: | f79e63c2fdfd83ffa5cf3eaf78318281f63e190b |
|---|---|
| Date: | 2016-05-26 10:11:25 |
| User: | kinaba |
| Comment: | R2A |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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 > 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) > 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 > 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() > 115 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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