Overview
| SHA1 Hash: | c5054cb313941687e8d5aa8f6af507763078dde8 |
|---|---|
| Date: | 2011-07-26 10:52:19 |
| User: | kinaba |
| Comment: | 512 |
| 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
Modified CheckList.pptx from [dcb9bdddd36bb3bb] to [dc7db7f8ce6a9e9f].
cannot compute difference between binary files
Added SRM/512-U/1A.cpp version [0f86d3bb71a9b2cc]
> 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 MysteriousRestaurant { public: > 23 int maxDays(vector <string> prices, int budget) > 24 { > 25 for(int D=prices.size(); D>=0; --D) > 26 if( ok(D, prices, budget) ) > 27 return D; > 28 return 0; > 29 } > 30 > 31 bool ok(int D, const vector<string>& prices, int budget) > 32 { > 33 int M = prices[0].size(); > 34 > 35 vector< vector<int> > p(7, vector<int>(M)); > 36 for(int i=0; i<D; ++i) > 37 for(int m=0; m<M; ++m) > 38 p[i%7][m] += toPrice(prices[i][m]); > 39 > 40 int cost = 0; > 41 for(int i=0; i<7; ++i) > 42 { > 43 int least = 0x7fffffff; > 44 for(int m=0; m<M; ++m) > 45 least = min(least, p[i][m]); > 46 cost += least; > 47 } > 48 return cost <= budget; > 49 } > 50 > 51 int toPrice(char c) > 52 { > 53 if(c<='9') > 54 return c-'0'; > 55 if(c<='Z') > 56 return c-'A'+10; > 57 return c-'a'+36; > 58 } > 59 }; > 60 > 61 // BEGIN CUT HERE > 62 #include <ctime> > 63 double start_time; string timer() > 64 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 65 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 66 { os << "{ "; > 67 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 68 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 69 void verify_case(const int& Expected, const int& Received) { > 70 bool ok = (Expected == Received); > 71 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 73 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 74 #define END verify_case(_, MysteriousRestaurant().maxDays(prices, budget)); > 75 int main(){ > 76 > 77 CASE(0) > 78 string prices_[] = {"26", "14", "72", "39", "32", "85", "06"}; > 79 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 80 int budget = 13; > 81 int _ = 5; > 82 END > 83 CASE(1) > 84 string prices_[] = {"26", "14", "72", "39", "32", "85", "06", "91"}; > 85 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 86 int budget = 20; > 87 int _ = 8; > 88 END > 89 CASE(2) > 90 string prices_[] = {"SRM", "512"}; > 91 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 92 int budget = 4; > 93 int _ = 0; > 94 END > 95 CASE(3) > 96 string prices_[] = {"Dear", "Code", "rsHa", "veFu", "nInT", "heCh", "all > 97 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 98 int budget = 256; > 99 int _ = 10; > 100 END > 101 /* > 102 CASE(4) > 103 string prices_[] = ; > 104 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 105 int budget = ; > 106 int _ = ; > 107 END > 108 CASE(5) > 109 string prices_[] = ; > 110 vector <string> prices(prices_, prices_+sizeof(prices_)/sizeof(*prices > 111 int budget = ; > 112 int _ = ; > 113 END > 114 */ > 115 } > 116 // END CUT HERE
Added SRM/512-U/1B-U.cpp version [44710d18d6a7b173]
> 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 SubFibonacci { public: > 23 vector<LL> fib; > 24 > 25 int maxElements(vector <int> S) > 26 { > 27 fib.assign(100, 0); > 28 fib[0] = 0; > 29 fib[1] = 1; > 30 for(size_t k=2; k<fib.size(); ++k) > 31 fib[k] = fib[k-2] + fib[k-1]; > 32 > 33 sort(S.begin(), S.end()); > 34 int result = 0; > 35 for(int i=0; i<S.size(); ++i) // 50 > 36 result = max(result, longestFib(S,0,i)+longestFib(S,i,S. > 37 return result; > 38 } > 39 > 40 int longestFib(const vector<int>& S, int s, int e) > 41 { > 42 set<int> all(S.begin()+s, S.begin()+e); > 43 int result = min(2, e-s); > 44 for(int i=s; i<e; ++i) // 50 > 45 for(int j=i+1; j<e; ++j) // 50 > 46 { > 47 LL a = S[i]; > 48 LL b = S[j]; > 49 for(int k=1; fib[k-1]*a<=b; ++k) // fib^-1(10000 > 50 { > 51 LL x = (b-fib[k-1]*a) / fib[k]; > 52 if( x && x!=a && fib[k-1]*a + fib[k]*x = > 53 LL p = a; > 54 LL q = x; > 55 int len = 2; > 56 for(;;) { > 57 if( q == b ) > 58 break; > 59 if(a<q && all.count(q)) > 60 LL pp = p; > 61 p = q; > 62 q = pp+q; > 63 } > 64 result = max(result, len); > 65 } > 66 } > 67 } > 68 return result; > 69 } > 70 }; > 71 > 72 // BEGIN CUT HERE > 73 #include <ctime> > 74 double start_time; string timer() > 75 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 76 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 77 { os << "{ "; > 78 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 79 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 80 void verify_case(const int& Expected, const int& Received) { > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 83 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 84 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 85 #define END verify_case(_, SubFibonacci().maxElements(S));} > 86 int main(){ > 87 > 88 CASE(0) > 89 int S_[] = {8, 1, 20, 3, 10}; > 90 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 91 int _ = 5; > 92 END > 93 CASE(1) > 94 int S_[] = {19, 47, 50, 58, 77, 99}; > 95 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 96 int _ = 4; > 97 END > 98 CASE(2) > 99 int S_[] = {512}; > 100 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 101 int _ = 1; > 102 END > 103 CASE(3) > 104 int S_[] = {3, 5, 7, 10, 13, 15, 20, 90}; > 105 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 106 int _ = 7; > 107 END > 108 CASE(4) > 109 int S_[] = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89}; > 110 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 111 int _ = 10; > 112 END > 113 CASE(5) > 114 int S_[] = {1}; > 115 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 116 int _ = 1; > 117 END > 118 CASE(6) > 119 int S_[] = {1,2}; > 120 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 121 int _ = 2; > 122 END > 123 CASE(7) > 124 int S_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, > 125 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 126 int _ = 11; > 127 END > 128 CASE(8) > 129 int S_[] = {1,3,4,5,61,97,157}; > 130 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 131 int _ = 6; > 132 END > 133 CASE(8) > 134 int S_[] = {2,4,6,10,999,1000}; > 135 vector <int> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 136 int _ = 6; > 137 END > 138 } > 139 // END CUT HERE
Added SRM/512-U/1C-U.cpp version [4a5bd572b13e0e84]
> 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 LL C[201][201]; > 24 > 25 class PickAndDelete { public: > 26 int count(vector <string> S_) > 27 { > 28 init_C(); > 29 vector<int> S; > 30 { > 31 string s = accumulate(S_.begin(), S_.end(), string("")); > 32 stringstream ss(s); > 33 for(int v; ss>>v; ) > 34 S.push_back(v); > 35 } > 36 sort(S.begin(), S.end()); > 37 return solve(S); > 38 } > 39 > 40 void init_C() > 41 { > 42 for(int n=0; n<=200; ++n) > 43 for(int k=0; k<=n; ++k) > 44 if( k==0 || k==n ) > 45 C[n][k] = 1; > 46 else > 47 C[n][k] = (C[n-1][k-1] + C[n-1][k]) % MO > 48 } > 49 > 50 int solve(const vector<int>& S) > 51 { > 52 map<multiset<int>, LL> dp; > 53 dp[multiset<int>()] = 1; > 54 > 55 for(int i=0; i<S.size(); ++i) > 56 { > 57 int next = S[i]; > 58 map<multiset<int>, LL> dp2; > 59 for(map<multiset<int>,LL>::iterator it=dp.begin(); it!=d > 60 { > 61 const multiset<int>& sig = it->first; > 62 if( sig.size() < next ) { > 63 multiset<int> new_sig = sig; > 64 new_sig.insert(1); > 65 (dp2[new_sig] += it->second*(next-sig.si > 66 } > 67 for(multiset<int>::const_iterator jt=sig.begin() > 68 { > 69 multiset<int> new_sig = sig; > 70 new_sig.erase(*jt); > 71 new_sig.insert(*jt+1); > 72 (dp2[new_sig] += it->second) %= MODVAL; > 73 } > 74 } > 75 dp.swap(dp2); > 76 } > 77 > 78 LL sum = 0; > 79 for(map<multiset<int>,LL>::iterator it=dp.begin(); it!=dp.end(); > 80 { > 81 LL n = it->second; > 82 int tt = S.size(); > 83 for(multiset<int>::const_iterator jt=it->first.begin(); > 84 (n *= C[tt][*jt]) %= MODVAL; > 85 tt -= *jt; > 86 } > 87 sum += n; > 88 } > 89 return int(sum % MODVAL); > 90 } > 91 }; > 92 > 93 // BEGIN CUT HERE > 94 #include <ctime> > 95 double start_time; string timer() > 96 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 97 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 98 { os << "{ "; > 99 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 100 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 101 void verify_case(const int& Expected, const int& Received) { > 102 bool ok = (Expected == Received); > 103 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 104 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 105 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 106 #define END verify_case(_, PickAndDelete().count(S));} > 107 int main(){ > 108 > 109 CASE(0) > 110 string S_[] = {"1 2"}; > 111 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 112 int _ = 3; > 113 END > 114 CASE(1) > 115 string S_[] = {"2 2 2 2 2 2 2 2 2"}; > 116 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 117 int _ = 512; > 118 END > 119 CASE(2) > 120 string S_[] = {"5", " 1 ", "2"}; > 121 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 122 int _ = 34; > 123 END > 124 CASE(3) > 125 string S_[] = {"3 ", "14159 265", "3589 7", " 932"}; > 126 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 127 int _ = 353127147; > 128 END > 129 /* > 130 CASE(4) > 131 string S_[] = ; > 132 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 133 int _ = ; > 134 END > 135 CASE(5) > 136 string S_[] = ; > 137 vector <string> S(S_, S_+sizeof(S_)/sizeof(*S_)); > 138 int _ = ; > 139 END > 140 */ > 141 } > 142 // END CUT HERE