Overview
| SHA1 Hash: | 5cbddaf9a469cad05b63d304b74933b907a347ef |
|---|---|
| Date: | 2017-05-20 17:56:15 |
| User: | kinaba |
| Comment: | tco17 |
| 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-2A-U/1A.cpp version [d18b982672b1ce1e]
> 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 > 30 class FoxAndCake2 { public: > 31 string isPossible(int c, int s) > 32 { > 33 return solve(c, s) ? "Possible" : "Impossible"; > 34 } > 35 > 36 bool solve(int a, int b) > 37 { > 38 if (gcd(a, b) != 1) > 39 return true; > 40 > 41 for (int x = 2; x <= 100 && x < a; ++x) > 42 for (int y = 2; y <= 100 && y < b; ++y) > 43 if (gcd(x, y) != 1 && gcd(a - x, b - y) != 1) > 44 return true; > 45 return false; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const string& Expected, const string& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, FoxAndCake2().isPossible(c, s));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int c = 74; > 67 int s = 109; > 68 string _ = "Possible"; > 69 END > 70 CASE(1) > 71 int c = 1000000000; > 72 int s = 1000000000; > 73 string _ = "Possible"; > 74 END > 75 CASE(2) > 76 int c = 1; > 77 int s = 58; > 78 string _ = "Impossible"; > 79 END > 80 CASE(3) > 81 int c = 223092871; > 82 int s = 446185741; > 83 string _ = "Possible"; > 84 END > 85 /* > 86 CASE(4) > 87 int c = ; > 88 int s = ; > 89 string _ = ; > 90 END > 91 */ > 92 } > 93 // END CUT HERE
Added SRM/TCO17-2A-U/1B-C.cpp version [5207bb27f05cf282]
> 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 DistanceZeroAndOne { public: > 23 vector <string> construct(vector <int> dist0, vector <int> dist1) > 24 { > 25 const vector<string> IMPOSSIBLE; > 26 const int N = dist0.size(); > 27 const int d01 = dist0[1]; > 28 if (dist0[0] != 0) return IMPOSSIBLE; > 29 if (dist1[1] != 0) return IMPOSSIBLE; > 30 if (dist0[1] != dist1[0]) return IMPOSSIBLE; > 31 > 32 map<pair<int, int>, int> repr; > 33 for (int x = 0; x < N; ++x) > 34 repr[make_pair(dist0[x], dist1[x])] = x; > 35 > 36 vector<string> ans(N, string(N, 'N')); > 37 ans[0][1] = ans[1][0] = d01 == 1 ? 'Y' : 'N'; > 38 for (int x = 2; x < N; ++x) { > 39 const int d0 = dist0[x]; > 40 const int d1 = dist1[x]; > 41 if (d0==0 || d1==0 || d0+d1<d01) > 42 return IMPOSSIBLE; > 43 if (d0 == 1) ans[0][x] = ans[x][0] = 'Y'; > 44 if (d1 == 1) ans[1][x] = ans[x][1] = 'Y'; > 45 > 46 if (d0 + d1 == d01) { // bone > 47 if (repr.count(make_pair(d0 - 1, d1 + 1))) { > 48 int p = repr[make_pair(d0 - 1, d1 + 1)]; > 49 ans[p][x] = ans[x][p] = 'Y'; > 50 } > 51 else { > 52 return IMPOSSIBLE; > 53 } > 54 > 55 if (repr.count(make_pair(d0 + 1, d1 - 1))) { > 56 int p = repr[make_pair(d0 + 1, d1 - 1)]; > 57 ans[p][x] = ans[x][p] = 'Y'; > 58 } > 59 else { > 60 return IMPOSSIBLE; > 61 } > 62 } > 63 else if(abs(d0 - d1) == d01) { // d0/d1 children > 64 if (repr.count(make_pair(d0 - 1, d1 - 1))) { > 65 int p = repr[make_pair(d0 - 1, d1 - 1)]; > 66 ans[p][x] = ans[x][p] = 'Y'; > 67 } > 68 else { > 69 return IMPOSSIBLE; > 70 } > 71 } > 72 else { > 73 // mid > 74 if (repr.count(make_pair(d0 - 1, d1 - 1))) { > 75 int p = repr[make_pair(d0 - 1, d1 - 1)]; > 76 ans[p][x] = ans[x][p] = 'Y'; > 77 } > 78 else { > 79 if (repr.count(make_pair(d0 - 1, d1 + 1) > 80 int p = repr[make_pair(d0 - 1, d > 81 ans[p][x] = ans[x][p] = 'Y'; > 82 } > 83 else if (repr.count(make_pair(d0 - 1, d1 > 84 int p = repr[make_pair(d0 - 1, d > 85 ans[p][x] = ans[x][p] = 'Y'; > 86 } else { > 87 return IMPOSSIBLE; > 88 } > 89 > 90 if (repr.count(make_pair(d0 + 1, d1 - 1) > 91 int p = repr[make_pair(d0 + 1, d > 92 ans[p][x] = ans[x][p] = 'Y'; > 93 } > 94 else if (repr.count(make_pair(d0, d1 - 1 > 95 int p = repr[make_pair(d0, d1 - > 96 ans[p][x] = ans[x][p] = 'Y'; > 97 } else { > 98 return IMPOSSIBLE; > 99 } > 100 } > 101 } > 102 } > 103 return ans; > 104 } > 105 }; > 106 > 107 // BEGIN CUT HERE > 108 #include <ctime> > 109 double start_time; string timer() > 110 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 111 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 112 { os << "{ "; > 113 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 114 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 115 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 116 bool ok = (Expected == Received); > 117 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 118 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 119 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 120 #define END verify_case(_, DistanceZeroAndOne().construct(dist0, dist1));} > 121 int main(){ > 122 > 123 CASE(0) > 124 int dist0_[] = {0,2,1}; > 125 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 126 int dist1_[] = {2,0,1}; > 127 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 128 string __[] = {"NNY", "NNY", "YYN" }; > 129 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 130 END > 131 CASE(1) > 132 int dist0_[] = {0,2,1}; > 133 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 134 int dist1_[] = {1,0,2}; > 135 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 136 vector <string> _; > 137 END > 138 CASE(2) > 139 int dist0_[] = {3,1,1,1}; > 140 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 141 int dist1_[] = {1,0,1,1}; > 142 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 143 vector <string> _; > 144 END > 145 CASE(3) > 146 int dist0_[] = {0,1,1,1}; > 147 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 148 int dist1_[] = {1,0,1,1}; > 149 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 150 string __[] = {"NYYY", "YNYY", "YYNN", "YYNN" }; > 151 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 152 END > 153 CASE(4) > 154 int dist0_[] = {0,3,1,2,2,3,4,4}; > 155 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 156 int dist1_[] = {3,0,2,1,2,3,4,4}; > 157 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 158 string __[] = {"NNYNNNNN", "NNNYNNNN", "YNNYYNNN", "NYYNYNNN", "NNYYNYNN > 159 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 160 END > 161 CASE(5) > 162 int dist0_[] = {0,1}; > 163 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 164 int dist1_[] = {1,0}; > 165 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 166 string __[] = {"NY", "YN" }; > 167 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 168 END > 169 /* > 170 CASE(6) > 171 int dist0_[] = ; > 172 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 173 int dist1_[] = ; > 174 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 175 string __[] = ; > 176 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 177 END > 178 CASE(7) > 179 int dist0_[] = ; > 180 vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_)); > 181 int dist1_[] = ; > 182 vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_)); > 183 string __[] = ; > 184 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 185 END > 186 */ > 187 } > 188 // END CUT HERE