Overview
| SHA1 Hash: | 4b1cd240b3650c12ab89a29cfaa02656f11c063b |
|---|---|
| Date: | 2015-08-25 23:38:00 |
| User: | kinaba |
| Comment: | TCO152D |
| 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/TCO15-2D-U/1A.cpp version [fd2a8960b68fd451]
> 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 BalancedSubstrings { public: > 23 int countSubstrings(string s) > 24 { > 25 const int N = s.size(); > 26 > 27 int numAllZeroRange = 0; > 28 for(int i=0; i<N; ++i) > 29 for(int k=i; k<N && s[k]=='0'; ++k) > 30 ++numAllZeroRange; > 31 > 32 vector<int> leftZero(N), rightZero(N); > 33 for(int i=1; i<N; ++i) > 34 leftZero[i] = (s[i-1]=='0' ? leftZero[i-1]+1 : 0); > 35 for(int i=N-2; i>=0; --i) > 36 rightZero[i] = (s[i+1]=='0' ? rightZero[i+1]+1 : 0); > 37 > 38 set<pair<int,int>> OneOneRange; > 39 for(int c=0; c<N; ++c) { > 40 // take c as the center. > 41 // enumerate all balanced [L, R]. > 42 int L=c, R=c, Lw=0, Rw=0; > 43 if(s[L]=='1') > 44 OneOneRange.emplace(L,R); > 45 while(0<=L && R<N) { > 46 const bool moveL = (Lw<Rw || Lw==Rw); > 47 const bool moveR = (Lw>Rw || Lw==Rw); > 48 > 49 if(moveL) > 50 while(--L>=0) > 51 if(s[L]=='1') { > 52 Lw += (c-L); > 53 break; > 54 } > 55 if(moveR) > 56 while(++R<N) > 57 if(s[R]=='1') { > 58 Rw += (R-c); > 59 break; > 60 } > 61 if(0<=L && R<N && Lw==Rw) > 62 OneOneRange.emplace(L, R); > 63 } > 64 } > 65 int numOtherRange = 0; > 66 for(auto lr: OneOneRange) { > 67 int L = lr.first, R = lr.second; > 68 numOtherRange += (leftZero[L]+1) * (rightZero[R]+1); > 69 } > 70 return numAllZeroRange + numOtherRange; > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const int& Expected, const int& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, BalancedSubstrings().countSubstrings(s));} > 88 int main(){ > 89 > 90 CASE(0) > 91 string s = "011"; > 92 int _ = 4; > 93 END > 94 CASE(1) > 95 string s = "10111"; > 96 int _ = 10; > 97 END > 98 CASE(2) > 99 string s = "00000"; > 100 int _ = 15; > 101 END > 102 CASE(3) > 103 string s = "0000001000000"; > 104 int _ = 91; > 105 END > 106 CASE(4) > 107 string s = "100110001001"; > 108 int _ = 49; > 109 END > 110 CASE(5) > 111 string s = "0"; > 112 int _ = 1; > 113 END > 114 CASE(5) > 115 string s = "1"; > 116 int _ = 1; > 117 END > 118 CASE(5) > 119 string s = "111111111111111111111111111111111111111111111111111111111111 > 120 int _ = 1563750; > 121 END > 122 CASE(5) > 123 string s = "000000000000000000000000000000000000000000000000000000000000 > 124 int _ = 3126250; > 125 END > 126 CASE(5) > 127 string s = "100011101001000101101101101000010110100101100100101010100101 > 128 int _ = 36497; > 129 END > 130 } > 131 // END CUT HERE
Added SRM/TCO15-2D-U/1B.cpp version [2d1a81027397e941]
> 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 BallsInBoxes { public: > 23 long long maxTurns(long long N, long long K) > 24 { > 25 if(N < 2*K) > 26 return shortCase(N, K); > 27 if(N < 3*K) > 28 return 1 + shortCase((N+K)/2, K); > 29 if(N < 10*K) > 30 return 1 + maxTurns(N-K, K); > 31 return (N/K-4) + maxTurns(N - (N/K-4)*K, K); > 32 } > 33 > 34 LL shortCase(LL N, LL K) { > 35 // The case where N is small enough and all positions are possoi > 36 return solve(N-K); > 37 } > 38 > 39 LL solve(LL N) { > 40 // Determine what number in [0,N] out of N boxes are filled. > 41 return N ? solve(N/2)+1 : 0; > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const long long& Expected, const long long& Received) { > 54 bool ok = (Expected == Received); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, BallsInBoxes().maxTurns(N, K));} > 59 int main(){ > 60 > 61 CASE(0) > 62 long long N = 10LL; > 63 long long K = 10LL; > 64 long long _ = 0LL; > 65 END > 66 CASE(1) > 67 long long N = 100LL; > 68 long long K = 1LL; > 69 long long _ = 99LL; > 70 END > 71 CASE(2) > 72 long long N = 1000LL; > 73 long long K = 999LL; > 74 long long _ = 1LL; > 75 END > 76 CASE(3) > 77 long long N = 10LL; > 78 long long K = 5LL; > 79 long long _ = 3LL; > 80 END > 81 CASE(4) > 82 long long N = 1234567898765LL; > 83 long long K = 658167578LL; > 84 long long _ = -1LL; > 85 END > 86 /* > 87 CASE(5) > 88 long long N = LL; > 89 long long K = LL; > 90 long long _ = LL; > 91 END > 92 */ > 93 } > 94 // END CUT HERE