Overview
| SHA1 Hash: | 272cda822f12a795a4ada4899bdef5e7534efd85 |
|---|---|
| Date: | 2017-08-19 11:17:59 |
| User: | kinaba |
| Comment: | tco17a3 |
| 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/TCO17-3A-U/1A.cpp version [3bd5d04ce69009dd]
> 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 int gcd(int a, int b) > 23 { > 24 while (a) > 25 swap(a, b %= a); > 26 return b; > 27 } > 28 > 29 bool is_coprime(int a, int b) > 30 { > 31 return gcd(a, b) == 1; > 32 } > 33 > 34 class CoprimeMatrix { public: > 35 vector<bool> is_p; > 36 vector<int> primes; > 37 > 38 string isPossible(vector <string> coprime) > 39 { > 40 // eratos > 41 if (is_p.empty()) { > 42 is_p.assign(60, true); > 43 is_p[0] = is_p[1] = false; > 44 for (int p = 2; p < is_p.size(); ++p) if (is_p[p]) { > 45 primes.push_back(p); > 46 for (int q = p + p; q < is_p.size(); q += p) > 47 is_p[q] = false; > 48 } > 49 } > 50 > 51 return solve(coprime) ? "Possible" : "Impossible"; > 52 } > 53 > 54 bool solve(const vector<string>& coprime) > 55 { > 56 const int N = coprime.size(); > 57 > 58 // sanity > 59 for (int i = 0; i < N; ++i) > 60 for (int k = 0; k < N; ++k) > 61 if (coprime[i][k] != coprime[k][i]) > 62 return false; > 63 > 64 // trivial case > 65 for (int i = 0; i < N; ++i) > 66 for (int k = 0; k < N; ++k) > 67 if (is_coprime(1 + i, 1 + k) != (coprime[i][k] == 'Y')) > 68 goto nontrivial; > 69 return true; > 70 > 71 nontrivial: > 72 for (int i = 0; i < N; ++i) > 73 if(coprime[i][i]=='Y') > 74 return false; > 75 > 76 vector<vector<bool>> cos; > 77 for (int off = 0; off < N; ++off) { > 78 vector<bool> co; > 79 for (int t = 0; t + off < N; ++t) > 80 co.push_back(coprime[off][off + t] == 'Y'); > 81 > 82 // x+off coprime with k in 0,1,2,,,,co.size()-1 iff co[k > 83 > 84 if (!can(co)) > 85 return false; > 86 cos.push_back(co); > 87 } > 88 > 89 for (int p = 2; p < N; ++p) if (is_p[p]) { > 90 int last = -1; > 91 for(int o=0; o<cos.size() && cos[o].size()>p; ++o) > 92 if (cos[o][p] == false) { > 93 if (last!=-1 && (o-last)!=p) > 94 return false; > 95 last = o; > 96 } > 97 else { > 98 if (o - last >= p) > 99 return false; > 100 } > 101 } > 102 > 103 return true; > 104 } > 105 > 106 bool can(const vector<bool>& co) > 107 { > 108 // Can there be a positive n such that coprime(n,i) == co[i] ? > 109 vector<int> prime_factors; > 110 for (int p = 2; p < co.size(); ++p) > 111 if (is_p[p] && !co[p]) > 112 prime_factors.push_back(p); > 113 > 114 for (int k = 0; k < co.size(); ++k) > 115 if (is_coprimev(k, prime_factors) != co[k]) { > 116 prime_factors.push_back(primes.back()); > 117 for (int k = 0; k < co.size(); ++k) > 118 if (is_coprimev(k, prime_factors) != co[ > 119 return false; > 120 return true; > 121 } > 122 return true; > 123 } > 124 > 125 bool is_coprimev(int k, const vector<int>& pfs) > 126 { > 127 for (int p : pfs) > 128 if (k%p == 0) > 129 return false; > 130 return true; > 131 } > 132 }; > 133 > 134 // BEGIN CUT HERE > 135 #include <ctime> > 136 double start_time; string timer() > 137 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 138 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 139 { os << "{ "; > 140 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 141 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 142 void verify_case(const string& Expected, const string& Received) { > 143 bool ok = (Expected == Received); > 144 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 145 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 146 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 147 #define END verify_case(_, CoprimeMatrix().isPossible(coprime));} > 148 int main(){ > 149 > 150 CASE(0) > 151 string coprime_[] = {"NYNYN", > 152 "YNYYN", > 153 "NYNYN", > 154 "YYYNY", > 155 "NNNYN"}; > 156 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 157 string _ = "Possible"; > 158 END > 159 CASE(1) > 160 string coprime_[] = {"NY", > 161 "NN"}; > 162 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 163 string _ = "Impossible"; > 164 END > 165 CASE(2) > 166 string coprime_[] = {"NYYYYN", > 167 "YNYNNN", > 168 "YYNYYY", > 169 "YNYNYN", > 170 "YNYYNY", > 171 "NNYNYN"}; > 172 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 173 string _ = "Possible"; > 174 END > 175 CASE(3) > 176 string coprime_[] = {"NN", > 177 "NN"}; > 178 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 179 string _ = "Impossible"; > 180 END > 181 CASE(4) > 182 // both x and x+1 and x+2 are coprime with 2 > 183 string coprime_[] = > 184 { > 185 "NYYY", > 186 "YNYY", > 187 "YYNY", > 188 "YYYN", > 189 }; > 190 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 191 string _ = "Impossible"; > 192 END > 193 CASE(5) > 194 // x+1 == 1 > 195 string coprime_[] = { "NY", "YY" }; > 196 vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*co > 197 string _ = "Impossible"; > 198 END > 199 CASE(6) > 200 string coprime_[] = { "Y" }; > 201 vector <string> coprime(coprime_, coprime_ + sizeof(coprime_) / sizeof(*coprime_ > 202 string _ = "Possible"; > 203 END > 204 } > 205 // END CUT HERE