Overview
| SHA1 Hash: | 2e8a7a70fdd7c248865b80a5b06c0c28d6cb9f64 |
|---|---|
| Date: | 2014-12-09 16:08:19 |
| User: | kinaba |
| Comment: | 639 |
| 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/639-U/1A-U.cpp version [fca3dc328f41b941]
> 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 AliceGame { public: > 23 long long findMinimumValue(long long x, long long y) > 24 { > 25 LL c = (LL)sqrt(x+y); > 26 for(LL n=max(0LL, c-10); n<=c+10; ++n) > 27 if(n*n == x+y) > 28 return solve(int(n), x); > 29 return -1; > 30 } > 31 > 32 LL solve(int n, LL x) > 33 { > 34 int cnt = 0; > 35 for(int t=n; t>=1; --t) > 36 { > 37 int s = 2*t-1; > 38 if(s <= x) { > 39 x -= s; > 40 cnt ++; > 41 } > 42 } > 43 return cnt; > 44 } > 45 }; > 46 > 47 // BEGIN CUT HERE > 48 #include <ctime> > 49 double start_time; string timer() > 50 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 51 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 52 { os << "{ "; > 53 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 54 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 55 void verify_case(const long long& Expected, const long long& Received) { > 56 bool ok = (Expected == Received); > 57 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 58 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 59 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 60 #define END verify_case(_, AliceGame().findMinimumValue(x, y));} > 61 int main(){ > 62 > 63 CASE(0) > 64 long long x = 8LL; > 65 long long y = 17LL; > 66 long long _ = 2LL; > 67 END > 68 CASE(1) > 69 long long x = 17LL; > 70 long long y = 8LL; > 71 long long _ = 3LL; > 72 END > 73 CASE(2) > 74 long long x = 0LL; > 75 long long y = 0LL; > 76 long long _ = 0LL; > 77 END > 78 CASE(3) > 79 long long x = 9LL; > 80 long long y = 9LL; > 81 long long _ = -1LL; > 82 END > 83 CASE(4) > 84 long long x = 500000LL; > 85 long long y = 500000LL; > 86 long long _ = 294LL; > 87 END > 88 CASE(5) > 89 long long x = 0LL; > 90 long long y = 4LL; > 91 long long _ = 0LL; > 92 END > 93 CASE(6) > 94 long long x = 4LL; > 95 long long y = 0LL; > 96 long long _ = 2LL; > 97 END > 98 } > 99 // END CUT HERE
Added SRM/639-U/1B.cpp version [b6a2a6266ec7de62]
> 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 BoardFolding { public: > 23 int howMany(int N, int M, vector <string> compressedPaper) > 24 { > 25 // decode > 26 int tonumber[128]; > 27 for(char c='0'; c<='9'; ++c) tonumber[c] = c-'0'; > 28 for(char c='a'; c<='z'; ++c) tonumber[c] = c-'a' + 10; > 29 for(char c='A'; c<='Z'; ++c) tonumber[c] = c-'A' + 36; > 30 tonumber['#'] = 62; > 31 tonumber['@'] = 63; > 32 > 33 vector<vector<int>> P(N, vector<int>(M)); > 34 for(int i=0; i<N; ++i) > 35 for(int j=0; j<M; ++j) > 36 P[i][j] = (tonumber[compressedPaper[i][j / 6]] >> (j % 6 > 37 > 38 // solve > 39 return solve(N, M, P); > 40 } > 41 > 42 int solve(int H, int W, const vector<vector<int>>& P) > 43 { > 44 // transpose > 45 vector<vector<int>> PT(W, vector<int>(H)); > 46 for(int y=0; y<H; ++y) > 47 for(int x=0; x<W; ++x) > 48 PT[x][y] = P[y][x]; > 49 > 50 // solve_each > 51 return solve_one(P) * solve_one(PT); > 52 } > 53 > 54 int solve_one(const vector<vector<int>>& P) > 55 { > 56 // hash > 57 vector<int> PH; > 58 map<vector<int>, int> hash; > 59 for(const auto& Pi: P) { > 60 if(!hash.count(Pi)) { > 61 int id = hash.size(); > 62 hash[Pi] = id; > 63 } > 64 PH.push_back(hash[Pi]); > 65 } > 66 > 67 // solve > 68 return solve_one(PH); > 69 } > 70 > 71 int solve_one(const vector<int>& P) > 72 { > 73 const int N = P.size(); > 74 > 75 vector<int> ok_range(N); > 76 for(int m=0; m<N; ++m) > 77 for(int w=1; m-w>=0 && m+w<=N; ++w) { > 78 if(P[m-w] != P[m+w-1]) > 79 break; > 80 ok_range[m] = w; > 81 } > 82 > 83 vector<vector<bool>> vis(N, vector<bool>(N+1)); > 84 > 85 function<void(int,int)> rec; > 86 rec = [&](int s, int e) { > 87 if(vis[s][e]) > 88 return; > 89 vis[s][e] = true; > 90 for(int m=s+1; m<e; ++m) > 91 if(ok_range[m] >= min(m-s, e-m)) { > 92 if(m-s <= e-m) > 93 rec(m, e); > 94 if(e-m <= m-s) > 95 rec(s, m); > 96 } > 97 }; > 98 rec(0, N); > 99 > 100 int cnt = 0; > 101 for(int s=0; s<N; ++s) > 102 for(int e=s+1; e<=N; ++e) > 103 if(vis[s][e] == 1) > 104 ++cnt; > 105 return cnt; > 106 } > 107 }; > 108 > 109 // BEGIN CUT HERE > 110 #include <ctime> > 111 double start_time; string timer() > 112 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 113 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 114 { os << "{ "; > 115 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 116 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 117 void verify_case(const int& Expected, const int& Received) { > 118 bool ok = (Expected == Received); > 119 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 120 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 121 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 122 #define END verify_case(_, BoardFolding().howMany(N, M, compressedPaper));} > 123 int main(){ > 124 > 125 CASE(1) > 126 int N = 2; > 127 int M = 7; > 128 string compressedPaper_[] = {"@@", "@@"}; > 129 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 130 int _ = 84; > 131 END > 132 CASE(0) > 133 int N = 2; > 134 int M = 2; > 135 string compressedPaper_[] = {"1", "3"}; > 136 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 137 int _ = 1; > 138 END > 139 CASE(2) > 140 int N = 4; > 141 int M = 4; > 142 string compressedPaper_[] = {"6", "9", "9", "6"}; > 143 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 144 int _ = 9; > 145 END > 146 CASE(3) > 147 int N = 6; > 148 int M = 1; > 149 string compressedPaper_[] = {"0", "2", "6", "@", "4", "A"}; > 150 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 151 int _ = 6; > 152 END > 153 CASE(4) > 154 int N = 3; > 155 int M = 3; > 156 string compressedPaper_[] = {"0", "2", "0"} > 157 ; > 158 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 159 int _ = 1; > 160 END > 161 /* > 162 CASE(5) > 163 int N = ; > 164 int M = ; > 165 string compressedPaper_[] = ; > 166 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 167 int _ = ; > 168 END > 169 CASE(6) > 170 int N = ; > 171 int M = ; > 172 string compressedPaper_[] = ; > 173 vector <string> compressedPaper(compressedPaper_, compressedPaper_+siz > 174 int _ = ; > 175 END > 176 */ > 177 } > 178 // END CUT HERE
Added SRM/639-U/1C-U.cpp version [526b59207f22295c]
> 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 LL gcd(LL a, LL b) > 23 { > 24 while(a) > 25 swap(a, b%=a); > 26 return b; > 27 } > 28 > 29 class ElectronicPet { public: > 30 vector<long long> minimumSec(vector <int> period1, vector <int> time1, v > 31 { > 32 vector<LL> Q; > 33 for(int i=0; i<period1.size(); ++i) > 34 Q.push_back(solve(period1[i], period2[i], time1[i], time > 35 return Q; > 36 } > 37 > 38 LL solve(LL P1, LL P2, LL T1, LL T2) > 39 { > 40 LL a1 = P1*(T1-1); > 41 LL b1 = P2*(T2-1); > 42 > 43 if(gcd(P1, P2) != 1) > 44 return a1==b1 ? a1+1 : max(a1,b1); > 45 > 46 // (P1, T1) is dominant. > 47 if(a1<b1 || (a1==b1 && P1<P2)) { > 48 swap(P1, P2); > 49 swap(T1, T2); > 50 } > 51 > 52 // -1 == P2*k mod P1? > 53 // TODO: xgcd > 54 LL k=1; > 55 while(P2*k%P1 != P1-1) > 56 ++k; > 57 // During (P2*k+1)/P1+1 p1, I can use k p2. > 58 LL v = (P2*k+1)/P1+1; > 59 LL consume = T1/v*k; > 60 return max(P1*(T1-1), P1*(max(1LL,T1/v*v)-1)+1+P2*(max(1LL,T2-co > 61 } > 62 }; > 63 > 64 // BEGIN CUT HERE > 65 #include <ctime> > 66 double start_time; string timer() > 67 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 68 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 69 { os << "{ "; > 70 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 71 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 72 void verify_case(const vector<long long>& Expected, const vector<long long>& Rec > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, ElectronicPet().minimumSec(period1, time1, perio > 78 int main(){ > 79 > 80 CASE(0) > 81 int period1_[] = {2}; > 82 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 83 int time1_[] = {2}; > 84 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 85 int period2_[] = {2}; > 86 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 87 int time2_[] = {3}; > 88 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 89 long long __[] = {4 }; > 90 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 91 END > 92 CASE(1) > 93 int period1_[] = {1}; > 94 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 95 int time1_[] = {10}; > 96 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 97 int period2_[] = {2}; > 98 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 99 int time2_[] = {4}; > 100 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 101 long long __[] = {13 }; > 102 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 103 END > 104 CASE(2) > 105 int period1_[] = {7357,10,2}; > 106 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 107 int time1_[] = {7356,50,1000000}; > 108 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 109 int period2_[] = {7356,3,3}; > 110 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 111 int time2_[] = {7357,167,900000}; > 112 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 113 long long __[] = {54110737, 510, 2799998 }; > 114 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 115 END > 116 CASE(3) > 117 int period1_[] = {407682800,484877059,830674177,227281073,19285523,56093 > 118 316159340,674806519,329433665,738538481,641235893,765181213,174785202,336152284, > 119 570921683,400867251,774285402,943390771,837295831,294507056,493790893,522227203, > 120 497924687,598834705,475831075,475114141,905813209,170832752,641484603,289813259, > 121 862545694,178944781,755931661,620338556,970867185,83941427,135674814,895365643, > 122 473440918,718282949,499031452,245406771,472643639,857414603,969063773,78465926, > 123 1,7,2,8,7,7,3,8,1,2,8,6,1,7,10,5,3,10,1,5,5,7,1,1,10,9,3,8,5,6,7,3,7,7,5,3,1,4, > 124 9,8,1,5,9,7,4,7,9,1}; > 125 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 126 int time1_[] = {685321887,561847762,364868210,867285301,914945601,118787 > 127 803650261,960301524,266477641,39110673,474718169,71340489,687134789,493401968, > 128 653058743,55748625,509077445,269937973,742890796,52585495,726357125,68477490, > 129 4,7,9,9,7,6,1,7,3,8,6,9,1,9,9,6,10,6,8,8,10,9,6,5,781250147,170878774,855135226, > 130 549059143,654877349,801427166,673830906,386629440,851395517,900791233,449728383, > 131 250397037,69109668,512878462,27237926,285837889,66688537,91054902,717783650,3882 > 132 228914249,989188885,502709264,663817744,6,5,7,6,8,7,8,9,8,4,4,8,8,8,6,8,5,3,6,2, > 133 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 134 int period2_[] = {986705763,927574445,892948254,704066415,535436162,5903 > 135 856566021,518519690,225440136,785919924,5,5,5,9,9,4,7,10,7,9,4,4,818956627,41713 > 136 248892046,146009149,739277785,109423195,440198141,605525655,728478703,626172069, > 137 630370468,130076349,4,1,5,4,9,10,3,1,4,9,3,1,583089191,388870099,453827819,11151 > 138 844765437,521615016,829962743,292223139,131621553,188850119,791754731,848542169, > 139 1,9,10,3,9,4,3,4,4,4,278700059,895269545,67783376,711864145,956734152,422403629, > 140 81840569,351747691,160762278,343337051,756026313,407474198,3,1,2,5,6,7,8,9,7,8,1 > 141 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 142 int time2_[] = {682390001,180499376,576561187,900180870,848774944,346873 > 143 814962202,251766107,732807531,131595022,598147784,3,2,3,3,7,10,637954336,3809970 > 144 636675367,968908554,354172494,436377372,1,8,7,7,8,3,419710297,126884289,57114341 > 145 264634798,264801163,157605826,4,4,6,8,5,5,485199156,117420995,773034099,41980156 > 146 687631343,469269453,4,6,6,7,5,9,456349996,696828998,843725003,829027352,36926715 > 147 515309802,7,6,8,2,10,6,75700282,191511000,510072386,297737413,817129266,66460254 > 148 8,6,10,2,6,2,325802862,171214036,503091306,72109356,917444714,754965240,1,2,10,9 > 149 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 150 long long __[] = {673318145613570000, 272427089959414899, 51483930436286 > 151 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 152 END > 153 /* > 154 CASE(4) > 155 int period1_[] = ; > 156 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 157 int time1_[] = ; > 158 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 159 int period2_[] = ; > 160 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 161 int time2_[] = ; > 162 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 163 long long __[] = ; > 164 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 165 END > 166 CASE(5) > 167 int period1_[] = ; > 168 vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*perio > 169 int time1_[] = ; > 170 vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_)); > 171 int period2_[] = ; > 172 vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*perio > 173 int time2_[] = ; > 174 vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_)); > 175 long long __[] = ; > 176 vector<long long> _(__, __+sizeof(__)/sizeof(*__)); > 177 END > 178 */ > 179 } > 180 // END CUT HERE