Overview
| SHA1 Hash: | f51ca8bd9d67e7db7bfbaee6c6ce90de8c78bf45 |
|---|---|
| Date: | 2011-07-02 15:37:18 |
| User: | kinaba |
| Comment: | TCO11-R2 |
| 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-2-U/1A.cpp version [e1aea37918978601]
> 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 static const int MODVAL = 1000000007; > 23 > 24 class GuessTheNumberGame { public: > 25 int possibleClues(int n) > 26 { > 27 vector<bool> isPrime(n+1, true); > 28 vector<int> ps; > 29 for(LL p=2; p<=n; ++p) > 30 if( isPrime[p] ) { > 31 ps.push_back(p); > 32 for(LL q=p*p; q<=n; q+=p) > 33 isPrime[q] = false; > 34 } > 35 > 36 LL cnt = 1; > 37 for(int i=0; i<ps.size(); ++i) > 38 { > 39 LL p = ps[i]; > 40 LL k = 1, pk = p; > 41 while( pk*p <= n ) > 42 pk*=p, k++; > 43 cnt = cnt*(k+1) % MODVAL; > 44 } > 45 return cnt; > 46 } > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, GuessTheNumberGame().possibleClues(n));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int n = 5; > 67 int _ = 12; > 68 END > 69 CASE(1) > 70 int n = 16; > 71 int _ = 240; > 72 END > 73 CASE(2) > 74 int n = 1; > 75 int _ = 1; > 76 END > 77 CASE(3) > 78 int n = 1000000; > 79 int _ = 677298706; > 80 END > 81 CASE(4) > 82 int n = 10000000; > 83 int _ = -1; > 84 END > 85 CASE(5) > 86 int n = 1; > 87 int _ = 1; > 88 END > 89 CASE(6) > 90 int n = 6; > 91 int _ = 12; > 92 END > 93 CASE(7) > 94 int n = 7; > 95 int _ = 24; > 96 END > 97 CASE(8) > 98 int n = 8; > 99 int _ = 32; > 100 END > 101 > 102 } > 103 // END CUT HERE
Added SRM/TCO11-2-U/1B-U.cpp version [4b292360dba25290]
> 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 STable { public: > 23 string getString(string s, string t, long long pos) > 24 { > 25 const int S = s.size(); > 26 const int T = t.size(); > 27 vector< vector<LL> > len(S+1, vector<LL>(T+1)); > 28 for(int i=1; i<=S; ++i) > 29 len[i][0] = 1; > 30 for(int k=1; k<=T; ++k) > 31 len[0][k] = 1; > 32 for(int i=1; i<=S; ++i) > 33 for(int k=1; k<=T; ++k) > 34 len[i][k] = len[i-1][k] + len[i][k-1]; > 35 > 36 string ans; > 37 for(LL p=pos; p<min(pos+50, len[S][T]); ++p) > 38 ans += theChar(s, t, len, p, S, T); > 39 return ans; > 40 } > 41 > 42 char theChar(const string& s, const string & t, const vector< vector<LL> > 43 { > 44 if(i==0) > 45 return t[k-1]; > 46 if(k==0) > 47 return s[i-1]; > 48 > 49 if( early(s, t, i-1, k, i, k-1) ) > 50 if( p < len[i-1][k] ) > 51 return theChar(s,t,len,p,i-1,k); > 52 else > 53 return theChar(s,t,len,p-len[i-1][k],i,k-1); > 54 else > 55 if( p < len[i][k-1] ) > 56 return theChar(s,t,len,p,i,k-1); > 57 else > 58 return theChar(s,t,len,p-len[i][k-1],i-1,k); > 59 } > 60 > 61 bool early(const string& s, const string & t, int i, int k, int ii, int > 62 { > 63 string le,ri; > 64 for(int x=0; x<i; ++x) le += s[x]; > 65 for(int x=0; x<k; ++x) le += t[x]; > 66 for(int x=0; x<ii; ++x) ri += s[x]; > 67 for(int x=0; x<kk; ++x) ri += t[x]; > 68 sort(le.begin(), le.end()); > 69 sort(ri.begin(), ri.end()); > 70 return le <= ri; > 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 string& Expected, const string& 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(_, STable().getString(s, t, pos));} > 88 int main(){ > 89 > 90 CASE(0) > 91 string s = "ad"; > 92 string t = "cb"; > 93 long long pos = 0LL; > 94 string _ = "acbacd"; > 95 END > 96 CASE(1) > 97 string s = "fox"; > 98 string t = "cat"; > 99 long long pos = 0LL; > 100 string _ = "acfcfoacftacfcfocfox"; > 101 END > 102 CASE(2) > 103 string s = "Ra6b1t"; > 104 string t = "W0lf"; > 105 long long pos = 66LL; > 106 string _ = "RWab0RWRWa0RWl0RWRWa6RWa0RWRWa6RWa6RWab0RWRWa6RWa6"; > 107 END > 108 CASE(3) > 109 string s = "M0HAXG"; > 110 string t = "COFU12"; > 111 long long pos = 919LL; > 112 string _ = "MOFU2"; > 113 END > 114 CASE(4) > 115 string s = "a0B1c2D3e4F5gHiJkLmN"; > 116 string t = "A9b8C7d6EfGhIjKlMn"; > 117 long long pos = 9876543210LL; > 118 string _ = "B10AaB1c0Aa9Aa0AaB0AaB10AaB1c0AaB1c20Aa9Aa0AaB0Aa9"; > 119 END > 120 CASE(5) > 121 string s = "TCOR2"; > 122 string t = "MEDiUm"; > 123 long long pos = 350LL; > 124 string _ = "MTDEMTiCMTEMTDEMTDEMTiDEMTiUCMTEMTCMTOCMTEMTDEMTCM"; > 125 END > 126 CASE(6) > 127 string s = "b"; > 128 string t = "a"; > 129 long long pos = 0LL; > 130 string _ = "ab"; > 131 END > 132 CASE(6) > 133 string s = "b"; > 134 string t = "a"; > 135 long long pos = 1LL; > 136 string _ = "b"; > 137 END > 138 CASE(7) > 139 string s = "01234abcdefghijklmnopqrstuvwxyz"; > 140 string t = "56789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; > 141 long long pos = 999999999LL; > 142 string _ = "??"; > 143 END > 144 > 145 } > 146 // END CUT HERE