Overview
| SHA1 Hash: | c179640bd893e4446027df3cc0fea55a0d1953dd |
|---|---|
| Date: | 2013-04-26 14:43:10 |
| User: | kinaba |
| Comment: | tco13 2b |
| 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/TCO13-2B-U/1A.cpp version [2b5324448e8be251]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 int gcd(int a, int b) > 23 { > 24 while(a) > 25 swap(a, b%=a); > 26 return b; > 27 } > 28 > 29 class FruitTrees { public: > 30 int maxDist(int apple, int kiwi, int grape) > 31 { > 32 int best = 0; > 33 for(int k0=0; k0<kiwi; ++k0) { > 34 int ak = calc(apple, 0, kiwi, k0); > 35 for(int g0=0; g0<grape; ++g0) > 36 best = max(best, min(ak, min(calc(apple, 0, grap > 37 } > 38 return best; > 39 } > 40 > 41 int calc(int a, int a0, int b, int b0) > 42 { > 43 //int x = abs(b0-a0); > 44 int x = b0-a0; > 45 int g = gcd(a, b); > 46 return min(x%g, g-x%g); > 47 } > 48 }; > 49 > 50 // BEGIN CUT HERE > 51 #include <ctime> > 52 double start_time; string timer() > 53 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 54 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 55 { os << "{ "; > 56 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 57 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 58 void verify_case(const int& Expected, const int& Received) { > 59 bool ok = (Expected == Received); > 60 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 61 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 62 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 63 #define END verify_case(_, FruitTrees().maxDist(apple, kiwi, grape));} > 64 int main(){ > 65 > 66 CASE(0) > 67 int apple = 1; > 68 int kiwi = 5; > 69 int grape = 8; > 70 int _ = 0; > 71 END > 72 CASE(1) > 73 int apple = 3; > 74 int kiwi = 3; > 75 int grape = 6; > 76 int _ = 1; > 77 END > 78 CASE(2) > 79 int apple = 40; > 80 int kiwi = 30; > 81 int grape = 20; > 82 int _ = 5; > 83 END > 84 CASE(3) > 85 int apple = 899; > 86 int kiwi = 1073; > 87 int grape = 1147; > 88 int _ = 14; > 89 END > 90 CASE(4) > 91 int apple = 2000; > 92 int kiwi = 2000; > 93 int grape = 2000; > 94 int _ = 666; > 95 END > 96 CASE(5) > 97 int apple = 100; > 98 int kiwi = 36; > 99 int grape = 225; > 100 int _ = -1; > 101 END > 102 /* > 103 CASE(6) > 104 int apple = ; > 105 int kiwi = ; > 106 int grape = ; > 107 int _ = ; > 108 END > 109 */ > 110 } > 111 // END CUT HERE
Added SRM/TCO13-2B-U/1B-U.cpp version [357463870fd0d422]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class ScotlandYard { public: > 23 int maxMoves(vector <string> taxi, vector <string> bus, vector <string> > 24 { > 25 const int N = taxi.size(); > 26 vector<LL> n[3]; > 27 for(int i=0; i<N; ++i) { > 28 LL n0=0, n1=0, n2=0; > 29 for(int k=0; k<N; ++k) { > 30 if(taxi[i][k]=='Y') > 31 n0 |= 1LL << k; > 32 if(bus[i][k]=='Y') > 33 n1 |= 1LL << k; > 34 if(metro[i][k]=='Y') > 35 n2 |= 1LL << k; > 36 } > 37 n[0].push_back(n0); > 38 n[1].push_back(n1); > 39 n[2].push_back(n2); > 40 } > 41 > 42 set<LL> vis; > 43 try { > 44 return rec((1LL<<N)-1, n, vis); > 45 } catch(...) { > 46 return -1; > 47 } > 48 } > 49 > 50 int rec(LL cur, const vector<LL> n_tbl[3], set<LL>& vis) > 51 { > 52 if((cur & (cur-1)) == 0) > 53 return 0; > 54 if(!vis.insert(cur).second) > 55 throw "infinite!"; > 56 > 57 LL next[] = {0,0,0}; > 58 for(int i=0; (1LL<<i)<=cur; ++i) > 59 if(cur & (1LL<<i)) { > 60 next[0] |= n_tbl[0][i]; > 61 next[1] |= n_tbl[1][i]; > 62 next[2] |= n_tbl[2][i]; > 63 } > 64 int r0 = next[0] ? rec(next[0], n_tbl, vis)+1 : 0; > 65 int r1 = next[1] ? rec(next[1], n_tbl, vis)+1 : 0; > 66 int r2 = next[2] ? rec(next[2], n_tbl, vis)+1 : 0; > 67 vis.erase(cur); > 68 return max(r0, max(r1, r2)); > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, ScotlandYard().maxMoves(taxi, bus, metro));} > 86 int main(){ > 87 > 88 CASE(0) > 89 string taxi_[] = {"NYN", > 90 "NNY", > 91 "NNN"}; > 92 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 93 string bus_[] = {"NNN", > 94 "NNN", > 95 "NNN"}; > 96 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 97 string metro_[] = {"NNN", > 98 "NNN", > 99 "NNN"}; > 100 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 101 int _ = 2; > 102 END > 103 CASE(1) > 104 string taxi_[] = {"NYY", > 105 "NNN", > 106 "NNN"}; > 107 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 108 string bus_[] = {"NNN", > 109 "NNN", > 110 "NNN"}; > 111 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 112 string metro_[] = {"NNN", > 113 "NNN", > 114 "NNN"}; > 115 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 116 int _ = 1; > 117 END > 118 CASE(2) > 119 string taxi_[] = {"NYYY", > 120 "YNYY", > 121 "YYNY", > 122 "YYYN"}; > 123 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 124 string bus_[] = {"NNNN", > 125 "NNNN", > 126 "NNNN", > 127 "NNNN"}; > 128 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 129 string metro_[] = {"NNNN", > 130 "NNNN", > 131 "NNNN", > 132 "NNNN"}; > 133 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 134 int _ = -1; > 135 END > 136 CASE(3) > 137 string taxi_[] = {"NNY", > 138 "NNY", > 139 "NNN"}; > 140 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 141 string bus_[] = {"NYN", > 142 "NNY", > 143 "NNN"}; > 144 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 145 string metro_[] = {"NNN", > 146 "NNN", > 147 "YNN"}; > 148 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 149 int _ = 2; > 150 END > 151 CASE(4) > 152 string taxi_[] = {"NNN", > 153 "YNY", > 154 "NNN"}; > 155 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 156 string bus_[] = {"NNN", > 157 "YNN", > 158 "YNN"}; > 159 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 160 string metro_[] = {"NNN", > 161 "NNN", > 162 "YYN"}; > 163 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 164 int _ = -1; > 165 END > 166 CASE(5) > 167 string taxi_[] = {"NNNNYNNNYY", > 168 "NNYNNYYYYY", > 169 "NNNNNNNNNN", > 170 "YYNNYYNNNY", > 171 "NNYNNNNNNN", > 172 "YNYNYNNNYN", > 173 "NNYNYNNNYN", > 174 "NNNNNNYNNN", > 175 "NNNNNNNNNN", > 176 "NNNNNNYNNN"}; > 177 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 178 string bus_[] = {"NNYNNNYNNY", > 179 "YNYNNYYNYY", > 180 "NNNNNNNNNN", > 181 "YNYNNYNYNY", > 182 "NNYNNNNNYN", > 183 "YNYNYNYNYN", > 184 "NNYNNNNNNY", > 185 "YNYNNNNNNN", > 186 "NNNNNNNNNN", > 187 "NNYNYNNNNN"}; > 188 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 189 string metro_[] = {"NNNNNNNYNN", > 190 "YNYNNNNNYN", > 191 "NNNNNNNNNN", > 192 "NYNNYNNNYY", > 193 "NNYNNNNNNN", > 194 "YNYNNNNNYY", > 195 "NNNNYNNNYN", > 196 "NNYNNNYNNN", > 197 "NNNNNNNNNY", > 198 "NNYNYNNNNN"}; > 199 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 200 int _ = 21; > 201 END > 202 CASE(6) > 203 string taxi_[] = { > 204 "NYYNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 205 "YNYNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 206 "NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN", > 207 "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN", > 208 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN", > 209 "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN", > 210 "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN", > 211 "NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN", > 212 "NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", > 213 "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", > 214 "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN", > 215 "NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN", > 216 "NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", > 217 "NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN", > 218 "NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN", > 219 "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN", > 220 "NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", > 221 "NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN", > 222 "NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", > 223 "NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", > 224 "NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN", > 225 "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN", > 226 "NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN", > 227 "NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", > 228 "NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN", > 229 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN", > 230 "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", > 231 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", > 232 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY", > 233 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 234 }; > 235 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 236 string bus_[] = { > 237 "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 238 "YNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 239 "NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN", > 240 "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN", > 241 "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN", > 242 "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN", > 243 "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN", > 244 "NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN", > 245 "NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", > 246 "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", > 247 "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN", > 248 "NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN", > 249 "NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN", > 250 "NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN", > 251 "NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN", > 252 "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN", > 253 "NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", > 254 "NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN", > 255 "NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", > 256 "NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", > 257 "NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN", > 258 "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN", > 259 "NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN", > 260 "NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", > 261 "NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN", > 262 "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN", > 263 "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", > 264 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN", > 265 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY", > 266 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 267 }; > 268 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 269 string metro_[] = { > 270 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 271 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 272 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 273 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 274 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 275 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 276 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 277 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 278 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 279 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 280 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 281 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 282 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 283 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 284 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 285 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 286 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 287 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 288 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 289 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 290 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 291 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 292 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 293 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 294 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 295 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 296 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 297 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 298 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 299 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", > 300 }; > 301 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 302 int _ = -1; > 303 END > 304 /* > 305 CASE(7) > 306 string taxi_[] = ; > 307 vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_)); > 308 string bus_[] = ; > 309 vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_)); > 310 string metro_[] = ; > 311 vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_)); > 312 int _ = ; > 313 END > 314 */ > 315 } > 316 // END CUT HERE