Overview
| SHA1 Hash: | 98499b8c6b8b606de7de224380038f5bce20a629 |
|---|---|
| Date: | 2011-11-12 16:09:45 |
| User: | kinaba |
| Comment: | 522 |
| 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/522-U/1A.cpp version [e8ec418b9332bc9f]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class RowAndCoins { public: > 23 string getWinner(string cells) > 24 { > 25 int n = cells.size(); > 26 int v = 0; > 27 for(int i=0; i<n; ++i) > 28 v = (v<<1) | (cells[i]=='B'); > 29 memo.clear(); > 30 return rec(0, v, n, 0) ? "Bob" : "Alice"; > 31 } > 32 > 33 vector<int> memo; > 34 int rec(int p, const int v, const int n, int mask) > 35 { > 36 int key = mask*2+p; > 37 if( key >= memo.size() ) > 38 memo.resize(key+1, -1); > 39 if( memo[key] >= 0 ) > 40 return memo[key]; > 41 > 42 for(int i=0; i<n; ++i) > 43 if( mask == (1<<n)-1 - (1<<i) ) > 44 return memo[key] = (v&(1<<i) ? 1 : 0); > 45 > 46 bool p_win = false; > 47 for(int s=0; s<n; ++s) > 48 for(int e=s+1; e<=n; ++e) if( e-s != n ) { > 49 int mm = mask; > 50 for(int i=s; i<e; ++i) { > 51 if( mask&(1<<i) ) > 52 goto next; > 53 mm |= (1<<i); > 54 } > 55 if( mm == (1<<n)-1 ) > 56 goto next; > 57 if( p == rec(p^1, v, n, mm) ) > 58 p_win = true; > 59 next:; > 60 } > 61 return memo[key] = (p_win ? p : p^1); > 62 } > 63 }; > 64 > 65 // BEGIN CUT HERE > 66 #include <ctime> > 67 double start_time; string timer() > 68 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 69 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 70 { os << "{ "; > 71 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 72 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 73 void verify_case(const string& Expected, const string& Received) { > 74 bool ok = (Expected == Received); > 75 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 76 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 77 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 78 #define END verify_case(_, RowAndCoins().getWinner(cells));} > 79 int main(){ > 80 > 81 CASE(0) > 82 string cells = "ABBB"; > 83 string _ = "Alice"; > 84 END > 85 CASE(1) > 86 string cells = "BBBB"; > 87 string _ = "Bob"; > 88 END > 89 CASE(2) > 90 string cells = "BA"; > 91 string _ = "Alice"; > 92 END > 93 CASE(3) > 94 string cells = "BABBABBB"; > 95 string _ = "Bob"; > 96 END > 97 CASE(4) > 98 string cells = "ABABBBABAABBAA"; > 99 string _ = "Alice"; > 100 END > 101 CASE(5) > 102 string cells = "BBBAAABBAAABBB"; > 103 string _ = "Bob"; > 104 END > 105 CASE(6) > 106 string cells = "A"; > 107 string _ = "Alice"; > 108 END > 109 CASE(7) > 110 string cells = "B"; > 111 string _ = "Bob"; > 112 END > 113 > 114 } > 115 // END CUT HERE
Added SRM/522-U/1B.cpp version [34827d4e4ac8d217]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class CorrectMultiplication { public: > 23 long long getMinimum(int a, int b, int c) > 24 { > 25 return solve(a,b,c); > 26 } > 27 > 28 LL solve(LL a, LL b, LL c) > 29 { > 30 if( a > b ) > 31 swap(a,b); > 32 LL vv = (1LL<<62); > 33 for(LL A=1; A*A <= (a+b+c)*2; ++A) > 34 vv = min(vv, best_of(A,a,b,c)); > 35 return vv; > 36 } > 37 > 38 LL best_of(LL A, LL a, LL b, LL c) > 39 { > 40 LL Bl = 1; > 41 LL Br = a+b+c; > 42 while( Bl+3 < Br ) > 43 { > 44 LL Bc1 = (Bl*2+Br*1) / 3; > 45 LL Bc2 = (Bl*1+Br*2) / 3; > 46 LL cc1 = abs(A-a)+abs(Bc1-b)+abs(A*Bc1-c); > 47 LL cc2 = abs(A-a)+abs(Bc2-b)+abs(A*Bc2-c); > 48 if(cc1 < cc2) > 49 Br = Bc2; > 50 else > 51 Bl = Bc1; > 52 } > 53 LL vv = (1LL<<62); > 54 for(LL B=Bl; B<=Br; ++B) > 55 vv = min(vv, abs(A-a)+abs(B-b)+abs(A*B-c)); > 56 return vv; > 57 } > 58 }; > 59 > 60 // BEGIN CUT HERE > 61 #include <ctime> > 62 double start_time; string timer() > 63 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 64 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 65 { os << "{ "; > 66 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 67 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 68 void verify_case(const long long& Expected, const long long& Received) { > 69 bool ok = (Expected == Received); > 70 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 71 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 72 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 73 #define END verify_case(_, CorrectMultiplication().getMinimum(a, b, c));} > 74 int main(){ > 75 > 76 CASE(0) > 77 int a = 19; > 78 int b = 28; > 79 int c = 522; > 80 long long _ = 2LL; > 81 END > 82 CASE(1) > 83 int a = 10; > 84 int b = 30; > 85 int c = 500; > 86 long long _ = 11LL; > 87 END > 88 CASE(2) > 89 int a = 11111; > 90 int b = 11111; > 91 int c = 123454321; > 92 long long _ = 0LL; > 93 END > 94 CASE(3) > 95 int a = 1000; > 96 int b = 100; > 97 int c = 10; > 98 long long _ = 1089LL; > 99 END > 100 CASE(4) > 101 int a = 399; > 102 int b = 522; > 103 int c = 199999; > 104 long long _ = 24LL; > 105 END > 106 CASE(5) > 107 int a = 1000000000; > 108 int b = 1000000000; > 109 int c = 1000000000; > 110 long long _ = -1LL; > 111 END > 112 /* > 113 CASE(6) > 114 int a = ; > 115 int b = ; > 116 int c = ; > 117 long long _ = LL; > 118 END > 119 */ > 120 } > 121 // END CUT HERE
Added SRM/522-U/1C-U.cpp version [2049344b195d192d]
> 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 <cstring> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class PointErasing { public: > 23 vector<int> ans; > 24 > 25 vector <int> getOutcomes(vector <int> y) > 26 { > 27 rec(1, y, y[0], y[1], 1); > 28 return ans; > 29 } > 30 > 31 void rec(int i, const vector<int>& y, int lo, int hi, int c) > 32 { > 33 if( i == y.size() ) { > 34 if(c>1) > 35 ans.push_back(c); > 36 return; > 37 } > 38 rec(i+1, y, lo, hi, c); > 39 > 40 if( lo < y[i] && y[i] < hi ) { > 41 ans.push_back(c+1); > 42 return; > 43 } > 44 > 45 } > 46 }; > 47 > 48 // BEGIN CUT HERE > 49 #include <ctime> > 50 double start_time; string timer() > 51 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 52 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 53 { os << "{ "; > 54 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 55 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 56 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 57 bool ok = (Expected == Received); > 58 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 59 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 60 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 61 #define END verify_case(_, PointErasing().getOutcomes(y));} > 62 int main(){ > 63 > 64 CASE(0) > 65 int y_[] = { 1, 2, 1, 1, 0, 4, 3 }; > 66 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 67 int __[] = {4, 6 }; > 68 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 69 END > 70 CASE(1) > 71 int y_[] = { 0, 0, 4, 4, 8, 8, 4, 4 }; > 72 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 73 int __[] = {6 }; > 74 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 75 END > 76 CASE(2) > 77 int y_[] = { 522 }; > 78 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 79 int __[] = {1 }; > 80 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 81 END > 82 CASE(3) > 83 int y_[] = { 19, 19, 19, 19, 19, 19 }; > 84 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 85 int __[] = {6 }; > 86 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 87 END > 88 CASE(4) > 89 int y_[] = { 0, 1, 2, 3, 4 }; > 90 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 91 int __[] = {2 }; > 92 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 93 END > 94 CASE(5) > 95 int y_[] = { 7, 8, 8, 7, 6, 7, 9, 3, 5, 0 }; > 96 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 97 int __[] = {3, 4, 5 }; > 98 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 99 END > 100 CASE(6) > 101 int y_[] = { 3, 2, 3, 3, 4, 3, 4, 3, 3, 1, 5, 3 }; > 102 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 103 int __[] = {4, 5, 6, 7, 9 }; > 104 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(7) > 107 int y_[] = { 5, 5, 4, 4, 5, 8, 5, 5, 5, 5, 5, 9, 2, 0, 9, 4, 5, 5, 3, 4, > 108 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 109 int __[] = {6, 7, 8, 10, 11, 12, 13, 15, 16, 17 }; > 110 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 111 END > 112 CASE(8) > 113 int y_[] = ; > 114 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 115 int __[] = ; > 116 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 CASE(9) > 119 int y_[] = ; > 120 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 121 int __[] = ; > 122 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 123 END > 124 > 125 } > 126 // END CUT HERE