Overview
| SHA1 Hash: | 712c7ed383b130a4049879d219164f41d4570f48 |
|---|---|
| Date: | 2013-03-06 11:28:40 |
| User: | kinaba |
| Comment: | 571 |
| 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/571-U/1A-U.cpp version [b5579a44800aff38]
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 FoxAndMp3 { public: 23 + set<int> used; 24 + vector <string> playList(int n) 25 + { 26 + vector<string> answer; 27 + int v = 1; 28 + while(answer.size() <= 50) 29 + { 30 + used.insert(v); 31 + answer.push_back(to_s(v)+".mp3"); 32 + int vv; 33 + if(!next(v,n,&vv)) 34 + break; 35 + v=vv; 36 + if(v==0) 37 + break; 38 + } 39 + return answer; 40 + } 41 + 42 + string to_s(int v) 43 + { 44 + stringstream ss; 45 + ss << v; 46 + return ss.str(); 47 + } 48 + 49 + bool next(int v, int n, int* vv) 50 + { 51 + if(v*10<=n) { 52 + *vv = v*10; 53 + return true; 54 + } 55 + if(v+1 <= n && (v+1)%10!=0) { 56 + *vv = v+1; 57 + return true; 58 + } 59 + if(v+1 > n || (v+1)%10==0) { 60 + *vv=v/10+1; 61 + return !used.count(*vv); 62 + } 63 + return false; 64 + } 65 +}; 66 + 67 +// BEGIN CUT HERE 68 +#include <ctime> 69 +double start_time; string timer() 70 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 71 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 72 + { os << "{ "; 73 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 74 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 75 +void verify_case(const vector <string>& Expected, const vector <string>& Received) { 76 + bool ok = (Expected == Received); 77 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 78 + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 79 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 80 +#define END verify_case(_, FoxAndMp3().playList(n));} 81 +int main(){ 82 + 83 +CASE(0) 84 + int n = 3; 85 + string __[] = {"1.mp3", "2.mp3", "3.mp3" }; 86 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 87 +END 88 +CASE(1) 89 + int n = 10; 90 + string __[] = {"1.mp3", "10.mp3", "2.mp3", "3.mp3", "4.mp3", "5.mp3", "6.mp3", "7.mp3", "8.mp3", "9.mp3" }; 91 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 92 +END 93 +CASE(2) 94 + int n = 16; 95 + string __[] = {"1.mp3", "10.mp3", "11.mp3", "12.mp3", "13.mp3", "14.mp3", "15.mp3", "16.mp3", "2.mp3", "3.mp3", "4.mp3", "5.mp3", "6.mp3", "7.mp3", "8.mp3", "9.mp3" }; 96 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 97 +END 98 +CASE(3) 99 + int n = 32; 100 + string __[] = {"1.mp3", "10.mp3", "11.mp3", "12.mp3", "13.mp3", "14.mp3", "15.mp3", "16.mp3", "17.mp3", "18.mp3", "19.mp3", "2.mp3", "20.mp3", "21.mp3", "22.mp3", "23.mp3", "24.mp3", "25.mp3", "26.mp3", "27.mp3", "28.mp3", "29.mp3", "3.mp3", "30.mp3", "31.mp3", "32.mp3", "4.mp3", "5.mp3", "6.mp3", "7.mp3", "8.mp3", "9.mp3" }; 101 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 102 +END 103 +CASE(4) 104 + int n = 100000009; 105 + string __[] = {"1.mp3", "10.mp3", "100.mp3", "1000.mp3", "10000.mp3", "100000.mp3", "1000000.mp3", "10000000.mp3", "100000000.mp3", "100000001.mp3", "100000002.mp3", "100000003.mp3", "100000004.mp3", "100000005.mp3", "100000006.mp3", "100000007.mp3", "100000008.mp3", "100000009.mp3", "10000001.mp3", "10000002.mp3", "10000003.mp3", "10000004.mp3", "10000005.mp3", "10000006.mp3", "10000007.mp3", "10000008.mp3", "10000009.mp3", "1000001.mp3", "10000010.mp3", "10000011.mp3", "10000012.mp3", "10000013.mp3", "10000014.mp3", "10000015.mp3", "10000016.mp3", "10000017.mp3", "10000018.mp3", "10000019.mp3", "1000002.mp3", "10000020.mp3", "10000021.mp3", "10000022.mp3", "10000023.mp3", "10000024.mp3", "10000025.mp3", "10000026.mp3", "10000027.mp3", "10000028.mp3", "10000029.mp3", "1000003.mp3" }; 106 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 107 +END 108 +CASE(5) 109 + int n = 1; 110 + string __[] = {"1.mp3" }; 111 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 112 +END 113 +/* 114 +CASE(6) 115 + int n = ; 116 + string __[] = ; 117 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 118 +END 119 +CASE(7) 120 + int n = ; 121 + string __[] = ; 122 + vector <string> _(__, __+sizeof(__)/sizeof(*__)); 123 +END 124 +*/ 125 +} 126 +// END CUT HERE
Added SRM/571-U/1C-U.cpp version [b84cafe08aca6eff]
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 complex<double> CMP; 20 + 21 +class CandyOnDisk { public: 22 + string ableToAchieve(vector <int> x_, vector <int> y_, vector <int> r_, int sx, int sy, int tx, int ty) 23 + { 24 + if(sx==tx && sy==ty) 25 + return "YES"; 26 + 27 + vector<LL> x,y,r; 28 + { 29 + map<pair<LL,LL>,LL> xyr; 30 + for(int i=0; i<x_.size(); ++i) 31 + xyr[make_pair(x_[i],y_[i])] = max<LL>(xyr[make_pair(x_[i],y_[i])], r_[i]); 32 + for(map<pair<LL,LL>,LL>::iterator it=xyr.begin(); it!=xyr.end(); ++it) { 33 + x.push_back(it->first.first); 34 + y.push_back(it->first.second); 35 + r.push_back(it->second); 36 + } 37 + } 38 + 39 + const int N = x.size(); 40 + map<int, double> p; 41 + { 42 + for(int i=0; i<N; ++i) 43 + { 44 + LL dd = (sx-x[i])*(sx-x[i])+(sy-y[i])*(sy-y[i]); 45 + if( dd <= r[i]*r[i] ) 46 + { 47 + if( dd == (tx-x[i])*(tx-x[i])+(ty-y[i])*(ty-y[i]) ) 48 + return "YES"; 49 + bool ok = false; 50 + for(int k=0; k<N; ++k) if(k!=i) 51 + { 52 + LL d = (x[i]-x[k])*(x[i]-x[k]) + (y[i]-y[k])*(y[i]-y[k]); 53 + if( d <= (r[i]+r[k])*(r[i]+r[k]) ) 54 + ok = true; 55 + } 56 + if(ok) 57 + p[i] = sqrt((double)dd); 58 + } 59 + } 60 + } 61 + 62 + for(;;) 63 + { 64 + bool upd = false; 65 + map<int,double> p2 = p; 66 + for(map<int,double>::iterator it=p.begin(); it!=p.end(); ++it) 67 + { 68 + int i = it->first; 69 + double d = it->second; 70 + 71 + LL dd = (tx-x[i])*(tx-x[i])+(ty-y[i])*(ty-y[i]); 72 + if(d*d <= dd && dd <= r[i]*r[i]) 73 + return "YES"; 74 + 75 + for(int k=0; k<N; ++k) if(k!=i) 76 + { 77 + double z = abs(CMP(x[i],y[i])-CMP(x[k],y[k])); 78 + if(max(0.0, z-r[k]) <= d) { 79 + double dk = max(0.0, z-r[i]); 80 + if(!p2.count(k) || p2[k]>dk) { 81 + upd = true; 82 + p2[k] = dk; 83 + } 84 + } 85 + } 86 + } 87 + if(!upd) 88 + break; 89 + p.swap(p2); 90 + } 91 + 92 + return "NO"; 93 + } 94 +}; 95 + 96 +// BEGIN CUT HERE 97 +#include <ctime> 98 +double start_time; string timer() 99 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 100 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 101 + { os << "{ "; 102 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 103 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 104 +void verify_case(const string& Expected, const string& Received) { 105 + bool ok = (Expected == Received); 106 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 107 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 108 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 109 +#define END verify_case(_, CandyOnDisk().ableToAchieve(x, y, r, sx, sy, tx, ty));} 110 +int main(){ 111 + 112 +CASE(0) 113 + int x_[] = {0, 4}; 114 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 115 + int y_[] = {0, 0}; 116 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 117 + int r_[] = {3, 3}; 118 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 119 + int sx = -1; 120 + int sy = -2; 121 + int tx = 6; 122 + int ty = 1; 123 + string _ = "YES"; 124 +END 125 +CASE(1) 126 + int x_[] = {0, 3}; 127 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 128 + int y_[] = {0, 0}; 129 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 130 + int r_[] = {5, 3}; 131 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 132 + int sx = -4; 133 + int sy = 0; 134 + int tx = -2; 135 + int ty = 0; 136 + string _ = "YES"; 137 +END 138 +CASE(2) 139 + int x_[] = {0}; 140 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 141 + int y_[] = {0}; 142 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 143 + int r_[] = {1}; 144 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 145 + int sx = 0; 146 + int sy = 0; 147 + int tx = 571; 148 + int ty = 571; 149 + string _ = "NO"; 150 +END 151 +CASE(3) 152 + int x_[] = {0}; 153 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 154 + int y_[] = {0}; 155 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 156 + int r_[] = {1}; 157 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 158 + int sx = 571; 159 + int sy = 571; 160 + int tx = 571; 161 + int ty = 571; 162 + string _ = "YES"; 163 +END 164 +CASE(4) 165 + int x_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; 166 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 167 + int y_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; 168 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 169 + int r_[] = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; 170 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 171 + int sx = 2; 172 + int sy = 2; 173 + int tx = 19; 174 + int ty = 19; 175 + string _ = "YES"; 176 +END 177 +CASE(5) 178 + int x_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; 179 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 180 + int y_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; 181 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 182 + int r_[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}; 183 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 184 + int sx = 2; 185 + int sy = 2; 186 + int tx = 19; 187 + int ty = 19; 188 + string _ = "NO"; 189 +END 190 +/* 191 +CASE(6) 192 + int x_[] = ; 193 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 194 + int y_[] = ; 195 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 196 + int r_[] = ; 197 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 198 + int sx = ; 199 + int sy = ; 200 + int tx = ; 201 + int ty = ; 202 + string _ = ; 203 +END 204 +CASE(7) 205 + int x_[] = ; 206 + vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 207 + int y_[] = ; 208 + vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 209 + int r_[] = ; 210 + vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_)); 211 + int sx = ; 212 + int sy = ; 213 + int tx = ; 214 + int ty = ; 215 + string _ = ; 216 +END 217 +*/ 218 +} 219 +// END CUT HERE