Overview
| SHA1 Hash: | 0b26cb3f9a0f2e99d0a4796d8400d98029f55a47 |
|---|---|
| Date: | 2012-05-29 13:35:51 |
| User: | kinaba |
| Comment: | 544 |
| 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/544/1A.cpp version [1e07ad54dbeb74d6]
> 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 ElectionFraudDiv1 { public: > 23 int MinimumVoters(vector <int> percentages) > 24 { > 25 for(int voter=1; voter<=100000; ++voter) > 26 if(possible(voter, percentages)) > 27 return voter; > 28 return -1; > 29 } > 30 > 31 bool possible(int V, const vector<int>& P) > 32 { > 33 int L=0, R=0; > 34 for(int i=0; i<P.size(); ++i) > 35 { > 36 int p = P[i]; > 37 > 38 // p-0.5 <= x/V*100 < p+0.5 > 39 // 2p-1 <= x/V*200 < 2p+1 > 40 > 41 int ll = (2*p-1)*V; > 42 int rr = (2*p+1)*V; > 43 > 44 // ll <= x*200 < rr > 45 > 46 int l = max(0, (ll+199)/200); > 47 int r = min(V, rr/200 - (rr%200 ? 0 : 1)); > 48 > 49 // l <= x <= r > 50 > 51 if( l <= r ) > 52 L+=l, R+=r; > 53 else > 54 return false; > 55 } > 56 return L<=V && V<=R; > 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 int& Expected, const int& 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(_, ElectionFraudDiv1().MinimumVoters(percentages)); > 74 int main(){ > 75 > 76 CASE(0) > 77 int percentages_[] = {33, 33, 33}; > 78 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 79 int _ = 3; > 80 END > 81 CASE(1) > 82 int percentages_[] = {29, 29, 43}; > 83 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 84 int _ = 7; > 85 END > 86 CASE(2) > 87 int percentages_[] = {12, 12, 12, 12, 12, 12, 12, 12}; > 88 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 89 int _ = -1; > 90 END > 91 CASE(3) > 92 int percentages_[] = {13, 13, 13, 13, 13, 13, 13, 13}; > 93 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 94 int _ = 8; > 95 END > 96 CASE(4) > 97 int percentages_[] = {0, 1, 100}; > 98 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 99 int _ = 200; > 100 END > 101 CASE(5) > 102 int percentages_[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, > 103 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 104 int _ = 97; > 105 END > 106 /* > 107 CASE(6) > 108 int percentages_[] = ; > 109 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 110 int _ = ; > 111 END > 112 CASE(7) > 113 int percentages_[] = ; > 114 vector <int> percentages(percentages_, percentages_+sizeof(percentages > 115 int _ = ; > 116 END > 117 */ > 118 } > 119 // END CUT HERE
Added SRM/544/1B.cpp version [83e9a8df96eca9df]
> 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 FlipGame { public: > 23 int minOperations(vector <string> board) > 24 { > 25 int cnt = 0; > 26 while( !all_zero(board) ) { > 27 next(board); > 28 ++cnt; > 29 } > 30 return cnt; > 31 } > 32 > 33 bool all_zero(const vector <string>& board) > 34 { > 35 for(int i=0; i<board.size(); ++i) > 36 if( count(board[i].begin(), board[i].end(), '0') != boar > 37 return false; > 38 return true; > 39 } > 40 > 41 void next(vector<string>& board) > 42 { > 43 int X=0; > 44 for(int y=0; y<board.size(); ++y) > 45 { > 46 int last1 = X-1; > 47 for(int x=X; x<board[y].size(); ++x) > 48 if( board[y][x] == '1' ) > 49 last1 = x; > 50 X = last1+1; > 51 for(int x=0; x<X; ++x) > 52 board[y][x] = char('0'+'1'-board[y][x]); > 53 } > 54 } > 55 }; > 56 > 57 // BEGIN CUT HERE > 58 #include <ctime> > 59 double start_time; string timer() > 60 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 61 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 62 { os << "{ "; > 63 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 64 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 65 void verify_case(const int& Expected, const int& Received) { > 66 bool ok = (Expected == Received); > 67 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 68 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 69 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 70 #define END verify_case(_, FlipGame().minOperations(board));} > 71 int main(){ > 72 > 73 CASE(0) > 74 string board_[] = {"1000", > 75 "1110", > 76 "1111"}; > 77 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 78 int _ = 1; > 79 END > 80 CASE(1) > 81 string board_[] = {"1111", > 82 "1111", > 83 "1111"}; > 84 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 85 int _ = 1; > 86 END > 87 CASE(2) > 88 string board_[] = {"00", > 89 "00", > 90 "00"}; > 91 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 92 int _ = 0; > 93 END > 94 CASE(3) > 95 string board_[] = { > 96 "00000000", > 97 "00100000", > 98 "01000000", > 99 "00001000", > 100 "00000000"}; > 101 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 102 int _ = 4; > 103 END > 104 CASE(4) > 105 string board_[] = {"000000000000001100000000000000", > 106 "000000000000011110000000000000", > 107 "000000000000111111000000000000", > 108 "000000000001111111100000000000", > 109 "000000000011111111110000000000", > 110 "000000000111111111111000000000", > 111 "000000001100111111001100000000", > 112 "000000011000011110000110000000", > 113 "000000111100111111001111000000", > 114 "000001111111111111111111100000", > 115 "000011111111111111111111110000", > 116 "000111111111000000111111111000", > 117 "001111111111100001111111111100", > 118 "011111111111110011111111111110", > 119 "111111111111111111111111111111"}; > 120 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 121 int _ = 29; > 122 END > 123 /* > 124 CASE(5) > 125 string board_[] = ; > 126 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 127 int _ = ; > 128 END > 129 CASE(6) > 130 string board_[] = ; > 131 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 132 int _ = ; > 133 END > 134 */ > 135 } > 136 // END CUT HERE
Added SRM/544/1C.cpp version [26bf2a688a29c24d]
> 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 static const int MODVAL = 1000000007; // must be prime for op/ > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} // x>=0 > 28 mint(size_t x):val(x%MODVAL) {} // x>=0 > 29 mint(LL x):val(x%MODVAL) {} // x>=0 > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 mint operator-(mint x) { return mint(0) - x; } > 38 > 39 vector<mint> vMul( const vector< vector<mint> >& A, const vector<mint>& B ) > 40 { > 41 const int n = A.size(); > 42 > 43 vector<mint> C(n); > 44 for(int i=0; i<n; ++i) > 45 for(int j=0; j<n; ++j) > 46 C[i] += A[i][j] * B[j]; > 47 return C; > 48 } > 49 > 50 vector< vector<mint> > mMul( const vector< vector<mint> >& A, const vector< vect > 51 { > 52 const int n = A.size(); > 53 > 54 vector< vector<mint> > C(n, vector<mint>(n)); > 55 for(int i=0; i<n; ++i) > 56 for(int j=0; j<n; ++j) { > 57 mint Cij = 0; > 58 for(int k=0; k<n; ++k) > 59 Cij += A[i][k] * B[k][j]; > 60 C[i][j] = Cij; > 61 } > 62 return C; > 63 } > 64 > 65 vector< vector<mint> > mPow( vector< vector<mint> > M, LL t ) // t>0 > 66 { > 67 vector< vector<mint> > R; > 68 for(; t; t>>=1, M=mMul(M,M)) > 69 if( t&1 ) > 70 R = (R.empty() ? M : mMul(R,M)); > 71 return R; > 72 } > 73 > 74 class SplittingFoxes { public: > 75 int sum(long long n, int S_, int L_, int R_) > 76 { > 77 mint S(S_), L(L_), R(R_); > 78 > 79 enum {PR, PT, PL, PB, XR, XT, XL, XB, YR, YT, YL, YB, __}; > 80 vector< vector<mint> > M(13, vector<mint>(13)); > 81 M[PR][PR] = S; M[PR][YR] = S; M[PR][PT] = L; M[PR][PB] = R; > 82 M[PT][PT] = S; M[PT][XT] = S; M[PT][PL] = L; M[PT][PR] = R; > 83 M[PL][PL] = S; M[PL][YL] =-S; M[PL][PB] = L; M[PL][PT] = R; > 84 M[PB][PB] = S; M[PB][XB] =-S; M[PB][PR] = L; M[PB][PL] = R; > 85 M[XR][XR] = S; M[XR][__] = S; M[XR][XT] = L; M[XR][XB] = R; > 86 M[XT][XT] = S; M[XT][__] = 0; M[XT][XL] = L; M[XT][XR] = R; > 87 M[XL][XL] = S; M[XL][__] =-S; M[XL][XB] = L; M[XL][XT] = R; > 88 M[XB][XB] = S; M[XB][__] = 0; M[XB][XR] = L; M[XB][XL] = R; > 89 M[YR][YR] = S; M[YR][__] = 0; M[YR][YT] = L; M[YR][YB] = R; > 90 M[YT][YT] = S; M[YT][__] = S; M[YT][YL] = L; M[YT][YR] = R; > 91 M[YL][YL] = S; M[YL][__] = 0; M[YL][YB] = L; M[YL][YT] = R; > 92 M[YB][YB] = S; M[YB][__] =-S; M[YB][YR] = L; M[YB][YL] = R; > 93 M[__][__] = S+L+R; > 94 vector<mint> V(13); > 95 V[__] = 1; > 96 return vMul(mPow(M, n), V)[PR].val; > 97 } > 98 }; > 99 > 100 // BEGIN CUT HERE > 101 #include <ctime> > 102 double start_time; string timer() > 103 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 104 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 105 { os << "{ "; > 106 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 107 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 108 void verify_case(const int& Expected, const int& Received) { > 109 bool ok = (Expected == Received); > 110 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 111 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 112 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 113 #define END verify_case(_, SplittingFoxes().sum(n, S, L, R));} > 114 int main(){ > 115 > 116 CASE(0) > 117 long long n = 58LL; > 118 int S = 2; > 119 int L = 0; > 120 int R = 0; > 121 int _ = 0; > 122 END > 123 CASE(1) > 124 long long n = 3LL; > 125 int S = 1; > 126 int L = 1; > 127 int R = 0; > 128 int _ = 1; > 129 END > 130 CASE(2) > 131 long long n = 5LL; > 132 int S = 1; > 133 int L = 3; > 134 int R = 2; > 135 int _ = 34; > 136 END > 137 CASE(3) > 138 long long n = 5LL; > 139 int S = 1; > 140 int L = 2; > 141 int R = 3; > 142 int _ = 999999973; > 143 END > 144 CASE(4) > 145 long long n = 123456789LL; > 146 int S = 987654321; > 147 int L = 544; > 148 int R = 544; > 149 int _ = 0; > 150 END > 151 CASE(5) > 152 long long n = 65536LL; > 153 int S = 1024; > 154 int L = 512; > 155 int R = 4096; > 156 int _ = 371473914; > 157 END > 158 /* > 159 CASE(6) > 160 long long n = LL; > 161 int S = ; > 162 int L = ; > 163 int R = ; > 164 int _ = ; > 165 END > 166 CASE(7) > 167 long long n = LL; > 168 int S = ; > 169 int L = ; > 170 int R = ; > 171 int _ = ; > 172 END > 173 */ > 174 } > 175 // END CUT HERE