Overview
| SHA1 Hash: | 6d771c8da166e4aa669b3e9ba7dc58d71c34fb97 |
|---|---|
| Date: | 2011-07-10 14:46:28 |
| User: | kinaba |
| Comment: | TCO11-3 |
| 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/TCO11-3/1A.cpp version [7c3fa8bfe90815c9]
> 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 int gcd(int x, int y) > 23 { > 24 while(x) > 25 swap(x, y%=x); > 26 return y; > 27 } > 28 > 29 int lcm(int x, int y) > 30 { > 31 return x/gcd(x,y)*y; > 32 } > 33 > 34 class ArtShift { public: > 35 int maxShifts(string sequence) > 36 { > 37 int B=0, W=0; > 38 for(int i=0; i<sequence.size(); ++i) > 39 (sequence[i]=='B' ? B : W)++; > 40 memo.assign(31*31, set<int>()); > 41 for(int b=0; b<=B; ++b) memo[b*31+0].insert(1); > 42 for(int w=0; w<=W; ++w) memo[0*31+w].insert(1); > 43 return *rec(B,W).rbegin(); > 44 } > 45 > 46 vector< set<int> > memo; > 47 const set<int>& rec(int B, int W) > 48 { > 49 set<int>& result = memo[B*31+W]; > 50 if( !result.empty() ) > 51 return result; > 52 > 53 result.insert(B+W); > 54 for(int b= 0; b<=B; ++b) > 55 for(int w=!b; w<=W; ++w) { > 56 const set<int>& x = rec(b,w); > 57 const set<int>& y = rec(B-b,W-w); > 58 for(set<int>::const_iterator it=x.begin(); it!=x.end(); > 59 for(set<int>::const_iterator jt=y.begin(); jt!=y.end(); > 60 result.insert(lcm(*it,*jt)); > 61 } > 62 return result; > 63 } > 64 }; > 65 > 66 // BEGIN CUT HERE > 67 #include <ctime> > 68 double start_time; string timer() > 69 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 70 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 71 { os << "{ "; > 72 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 73 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 74 void verify_case(const int& Expected, const int& Received) { > 75 bool ok = (Expected == Received); > 76 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 77 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 78 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 79 #define END verify_case(_, ArtShift().maxShifts(sequence));} > 80 int main(){ > 81 > 82 CASE(0) > 83 string sequence = "BW"; > 84 int _ = 2; > 85 END > 86 CASE(1) > 87 string sequence = "BBBWBBB"; > 88 int _ = 7; > 89 END > 90 CASE(2) > 91 string sequence = "BWBWB"; > 92 int _ = 6; > 93 END > 94 CASE(3) > 95 string sequence = "WWWWWWWWW"; > 96 int _ = 1; > 97 END > 98 CASE(4) > 99 string sequence = "WWWWWWWWWBBWB"; > 100 int _ = 60; > 101 END > 102 CASE(5) > 103 string sequence = "W"; > 104 int _ = 1; > 105 END > 106 CASE(6) > 107 string sequence = "B"; > 108 int _ = 1; > 109 END > 110 CASE(7) > 111 string sequence = "BB"; > 112 int _ = 1; > 113 END > 114 CASE(8) > 115 string sequence = "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW"; > 116 int _ = -1; > 117 END > 118 > 119 } > 120 // END CUT HERE
Added SRM/TCO11-3/1B.cpp version [b1fd16df13023b5a]
> 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 PrefixFreeSuperset { public: > 23 long long minSumLength(vector <string> cur, long long k) > 24 { > 25 map<int,LL> open; { > 26 string me(""); > 27 rec(me, cur, open); > 28 } > 29 > 30 LL totalLen = 0; > 31 for(int i=0; i<cur.size(); ++i) > 32 totalLen += cur[i].size(); > 33 k -= cur.size(); > 34 > 35 while(k) { > 36 if( open.empty() ) > 37 return -1; > 38 map<int,LL>::iterator it = open.begin(); > 39 int lll = it->first; > 40 LL ccc = it->second; > 41 open.erase(it); > 42 > 43 if( k <= ccc ) { > 44 totalLen += lll*k; > 45 k = 0; > 46 } > 47 else if( k <= ccc + open[lll+1] ) { > 48 totalLen += lll*ccc; > 49 k -= ccc; > 50 } > 51 else if( k <= ccc*2 + open[lll+1] ) { > 52 LL div = k - (ccc+open[lll+1]); > 53 open[lll+1] += div*2; > 54 totalLen += (ccc-div)*lll; > 55 k -= (ccc-div); > 56 } > 57 else > 58 open[lll+1] += ccc*2; > 59 } > 60 return totalLen; > 61 } > 62 > 63 void rec(string& me, const vector<string>& prefix, map<int,LL>& open) > 64 { > 65 bool iamprefix = false; > 66 for(int i=0; i<prefix.size(); ++i) > 67 if( me == prefix[i] ) > 68 return; > 69 else if( is_prefix(me, prefix[i]) ) > 70 iamprefix = true; > 71 if( iamprefix ) > 72 { > 73 me += '0'; > 74 rec(me, prefix, open); > 75 me.resize(me.size()-1); > 76 me += '1'; > 77 rec(me, prefix, open); > 78 me.resize(me.size()-1); > 79 } > 80 else > 81 { > 82 open[me.size()] ++; > 83 } > 84 } > 85 > 86 bool is_prefix(const string& s, const string& t) > 87 { > 88 return s.size()<=t.size() && s==t.substr(0,s.size()); > 89 } > 90 }; > 91 > 92 // BEGIN CUT HERE > 93 #include <ctime> > 94 double start_time; string timer() > 95 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 96 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 97 { os << "{ "; > 98 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 99 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 100 void verify_case(const long long& Expected, const long long& Received) { > 101 bool ok = (Expected == Received); > 102 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 103 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 104 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 105 #define END verify_case(_, PrefixFreeSuperset().minSumLength(cur, k));} > 106 int main(){ > 107 > 108 CASE(0) > 109 string cur_[] = {"010"}; > 110 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 111 long long k = 4LL; > 112 long long _ = 9LL; > 113 END > 114 CASE(1) > 115 string cur_[] = {"01","000"}; > 116 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 117 long long k = 4LL; > 118 long long _ = 9LL; > 119 END > 120 CASE(2) > 121 string cur_[] = {"0011","011110101","11101010111","11101010100000000","1 > 122 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 123 long long k = 1000000000000LL; > 124 long long _ = 39971901640560LL; > 125 END > 126 CASE(3) > 127 string cur_[] = {"010","00","011","1"}; > 128 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 129 long long k = 4LL; > 130 long long _ = 9LL; > 131 END > 132 CASE(4) > 133 string cur_[] = {"010","00","011","1"}; > 134 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 135 long long k = 5LL; > 136 long long _ = -1LL; > 137 END > 138 CASE(5) > 139 string cur_[] = {"0011010", > 140 "0011011110", > 141 "00110111001", > 142 "0011011111", > 143 "00110111000", > 144 }; > 145 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 146 long long k = 9LL; > 147 long long _ = 58LL; > 148 END > 149 /* > 150 CASE(6) > 151 string cur_[] = ; > 152 vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_)); > 153 long long k = LL; > 154 long long _ = LL; > 155 END > 156 */ > 157 } > 158 // END CUT HERE
Added SRM/TCO11-3/1C.cpp version [bb93038d2c81fe7f]
> 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 template<typename T> > 23 struct DP3x > 24 { > 25 int N1, N2, N3; > 26 vector<T> data; > 27 DP3x(int, int N2, int N3, const T& t = T()) > 28 : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()* > 29 T& operator()(int i1, int i2, int i3) > 30 { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } > 31 }; > 32 > 33 static const int MODVAL = 1000000007; > 34 > 35 class RowOfColors { public: > 36 int countWays(int w, int h, int k) > 37 { > 38 DP3x<LL> dp(w+1, h+1, k+1); > 39 for(int i=w; i>=0; --i) > 40 for(int stack=0; stack<=h; ++stack) > 41 for(int used =0; used <=k; ++used) > 42 if( i == w ) > 43 dp(i,stack,used) = (stack==1 && used==k ? 1 : 0) > 44 else { > 45 LL cnt = 0; > 46 if(stack+1<=h && used+1<=k) // push new color > 47 cnt += dp(i+1,stack+1,used+1); > 48 if(stack) // continue the same color > 49 cnt += dp(i+1,stack,used); > 50 if(stack && used+1<=k) // replace top > 51 cnt += dp(i+1,stack,used+1); > 52 if(stack>=2) // pop > 53 cnt += dp(i+1,stack-1,used); > 54 dp(i,stack,used) = cnt % MODVAL; > 55 } > 56 LL v = dp(0,0,0); > 57 for(int i=1; i<=k; ++i) > 58 v = (v*i) % MODVAL; > 59 return int(v); > 60 } > 61 }; > 62 > 63 // BEGIN CUT HERE > 64 #include <ctime> > 65 double start_time; string timer() > 66 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 67 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 68 { os << "{ "; > 69 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 70 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 71 void verify_case(const int& Expected, const int& Received) { > 72 bool ok = (Expected == Received); > 73 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 74 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 75 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 76 #define END verify_case(_, RowOfColors().countWays(w, h, k));} > 77 int main(){ > 78 > 79 CASE(0) > 80 int w = 4; > 81 int h = 1; > 82 int k = 2; > 83 int _ = 6; > 84 END > 85 CASE(1) > 86 int w = 4; > 87 int h = 3; > 88 int k = 2; > 89 int _ = 12; > 90 END > 91 CASE(2) > 92 int w = 4; > 93 int h = 4; > 94 int k = 10; > 95 int _ = 0; > 96 END > 97 CASE(3) > 98 int w = 14; > 99 int h = 28; > 100 int k = 14; > 101 int _ = 178290591; > 102 END > 103 /* > 104 CASE(4) > 105 int w = ; > 106 int h = ; > 107 int k = ; > 108 int _ = ; > 109 END > 110 CASE(5) > 111 int w = ; > 112 int h = ; > 113 int k = ; > 114 int _ = ; > 115 END > 116 */ > 117 } > 118 // END CUT HERE