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) > 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 > 75 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 76 bool ok = (Expected == Received); > 77 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 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 > 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" > 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" > 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", "1 > 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_, > 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_p > 32 for(map<pair<LL,LL>,LL>::iterator it=xyr.begin(); it!=xy > 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])* > 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]) + > 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(); > 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 > 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) > 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 > 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() > 107 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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, > 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, 1 > 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, 1 > 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, 1 > 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, 1 > 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