Overview
| SHA1 Hash: | 4a28d1c3b15f02ebe2fa9a9d80a4c51427e046ad |
|---|---|
| Date: | 2015-02-18 00:16:16 |
| User: | kinaba |
| Comment: | 649 |
| 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/649-U/1A.cpp version [824929308b649ea7]
> 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 Decipherability { public: > 23 string check(string s, int K) > 24 { > 25 return has_unique_ans(s, s.size()-K) ? "Certain" : "Uncertain"; > 26 } > 27 > 28 bool has_unique_ans(const string& s, int R) > 29 { > 30 if(R == 0) > 31 return true; > 32 > 33 for(int a=0; a<s.size(); ++a) > 34 for(int b=a+1; b<s.size(); ++b) if(s[a] == s[b]) { > 35 if(a + 1 + (s.size()-b-1) >= R) > 36 return false; > 37 } > 38 return true; > 39 } > 40 }; > 41 > 42 // BEGIN CUT HERE > 43 #include <ctime> > 44 double start_time; string timer() > 45 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 46 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 47 { os << "{ "; > 48 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 49 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 50 void verify_case(const string& Expected, const string& Received) { > 51 bool ok = (Expected == Received); > 52 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 53 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 54 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 55 #define END verify_case(_, Decipherability().check(s, K));} > 56 int main(){ > 57 > 58 CASE(0) > 59 string s = "snuke"; > 60 int K = 2; > 61 string _ = "Certain"; > 62 END > 63 CASE(1) > 64 string s = "aba"; > 65 int K = 1; > 66 string _ = "Certain"; > 67 END > 68 CASE(2) > 69 string s = "aba"; > 70 int K = 2; > 71 string _ = "Uncertain"; > 72 END > 73 CASE(3) > 74 string s = "abcdabcd"; > 75 int K = 3; > 76 string _ = "Certain"; > 77 END > 78 CASE(4) > 79 string s = "koukyoukoukokukikou"; > 80 int K = 2; > 81 string _ = "Uncertain"; > 82 END > 83 CASE(5) > 84 string s = "wolfsothe"; > 85 int K = 8; > 86 string _ = "Uncertain"; > 87 END > 88 CASE(6) > 89 string s = "aa"; > 90 int K = 2; > 91 string _ = "Certain"; > 92 END > 93 /* > 94 CASE(7) > 95 string s = ; > 96 int K = ; > 97 string _ = ; > 98 END > 99 CASE(8) > 100 string s = ; > 101 int K = ; > 102 string _ = ; > 103 END > 104 */ > 105 } > 106 // END CUT HERE
Added SRM/649-U/1B.cpp version [19b2bb7588a58abf]
> 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 XorSequence { public: > 23 long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) > 24 { > 25 vector<int> A(sz); > 26 A[0] = A0; > 27 A[1] = A1; > 28 for(int i=2; i<sz; i++) > 29 A[i] = int((A[i-2]*LL(P) + A[i-1]*LL(Q) + R) % N); > 30 > 31 int LN = 1; > 32 while((1<<LN) != N) ++LN; > 33 > 34 return solve(LN, A); > 35 } > 36 > 37 LL solve(int LN, const vector<int>& A) > 38 { > 39 LL total = 0; > 40 > 41 vector<vector<int>> Sec(1, A); > 42 for(int Bit=LN-1; Bit>=0; --Bit) { > 43 vector<vector<int>> Next_Sec; > 44 > 45 LL p01=0, p10=0; > 46 for(vector<int>& A: Sec) { > 47 vector<int> A0, A1; > 48 LL n0=0, n1=0; > 49 for(int i=0; i<A.size(); ++i) { > 50 if((1<<Bit)&A[i]) { > 51 p01 += n0; > 52 ++n1; > 53 A1.push_back(A[i]); > 54 } else { > 55 p10 += n1; > 56 ++n0; > 57 A0.push_back(A[i]); > 58 } > 59 } > 60 if(Bit) { > 61 if(!A0.empty())Next_Sec.emplace_back(std > 62 if(!A1.empty())Next_Sec.emplace_back(std > 63 } > 64 } > 65 Sec.swap(Next_Sec); > 66 > 67 total += max(p01, p10); > 68 } > 69 return total; > 70 } > 71 }; > 72 > 73 // BEGIN CUT HERE > 74 #include <ctime> > 75 double start_time; string timer() > 76 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 77 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 78 { os << "{ "; > 79 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 80 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 81 void verify_case(const long long& Expected, const long long& Received) { > 82 bool ok = (Expected == Received); > 83 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 84 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 85 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 86 #define END verify_case(_, XorSequence().getmax(N, sz, A0, A1, P, Q, R));} > 87 int main(){ > 88 > 89 CASE(0) > 90 int N = 4; > 91 int sz = 6; > 92 int A0 = 3; > 93 int A1 = 2; > 94 int P = 0; > 95 int Q = 1; > 96 int R = 3; > 97 long long _ = 8LL; > 98 END > 99 CASE(1) > 100 int N = 8; > 101 int sz = 8; > 102 int A0 = 2; > 103 int A1 = 5; > 104 int P = 3; > 105 int Q = 1; > 106 int R = 4; > 107 long long _ = 13LL; > 108 END > 109 CASE(2) > 110 int N = 8; > 111 int sz = 7; > 112 int A0 = 3; > 113 int A1 = 0; > 114 int P = 1; > 115 int Q = 2; > 116 int R = 4; > 117 long long _ = 12LL; > 118 END > 119 CASE(3) > 120 int N = 32; > 121 int sz = 15; > 122 int A0 = 7; > 123 int A1 = 9; > 124 int P = 11; > 125 int Q = 2; > 126 int R = 1; > 127 long long _ = 60LL; > 128 END > 129 CASE(4) > 130 int N = 131072; > 131 int sz = 131072; > 132 int A0 = 7; > 133 int A1 = 7; > 134 int P = 1; > 135 int Q = 0; > 136 int R = 0; > 137 long long _ = 0LL; > 138 END > 139 CASE(5) > 140 int N = 131072; > 141 int sz = 131070; > 142 int A0 = 411; > 143 int A1 = 415; > 144 int P = 398; > 145 int Q = 463; > 146 int R = 9191; > 147 long long _ = 4302679760LL; > 148 END > 149 /* > 150 CASE(6) > 151 int N = ; > 152 int sz = ; > 153 int A0 = ; > 154 int A1 = ; > 155 int P = ; > 156 int Q = ; > 157 int R = ; > 158 long long _ = LL; > 159 END > 160 CASE(7) > 161 int N = ; > 162 int sz = ; > 163 int A0 = ; > 164 int A1 = ; > 165 int P = ; > 166 int Q = ; > 167 int R = ; > 168 long long _ = LL; > 169 END > 170 */ > 171 } > 172 // END CUT HERE
Added SRM/649-U/1C-U.cpp version [62008e3877180504]
> 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 CartInSupermarket { public: > 23 int calcmin(vector <int> a, int b) > 24 { > 25 int L=0, R=*max_element(a.begin(), a.end()); // can do in (L,R] > 26 while(R-L>1) { > 27 int C = (L+R)/2; > 28 (can(a,b,C) ? R : L) = C; > 29 } > 30 return R; > 31 } > 32 > 33 bool can(vector<int> a, int b, int C) { > 34 int sp = 0; > 35 for(auto ai: a) { > 36 int spx; > 37 if(!need_split(ai, C, &spx)) > 38 return false; > 39 sp += spx; > 40 } > 41 return sp <= b; > 42 } > 43 > 44 // Can we process A in C minutes? If so, return minimal necessary split > 45 bool need_split(int A, int C, int* spx) { > 46 LL preM = 0; > 47 for(int b=max(0,A/C-1) ;; ++b) { > 48 LL M = cover(C, b); > 49 if(M <= preM) > 50 return false; > 51 preM = M; > 52 if(A<=M) { > 53 *spx = b; > 54 return true; > 55 } > 56 } > 57 } > 58 > 59 // C minutes, b splits. How many we can cover. > 60 LL cover(int C, int b) { > 61 vector<pair<int,int>> stock(1, make_pair(C,1)); > 62 while(b) { > 63 if(b>=stock[0].second) { > 64 b -= stock[0].second; > 65 stock[0] = make_pair(stock[0].first-1, stock[0]. > 66 } else { > 67 stock[0].second -= b; > 68 stock.emplace_back(stock[0].first-1, b*2); > 69 break; > 70 } > 71 } > 72 > 73 LL ans = 0; > 74 for(auto cn: stock) { > 75 if(cn.first<=0) > 76 return -1; > 77 ans += LL(cn.first)*cn.second; > 78 } > 79 return ans; > 80 } > 81 }; > 82 > 83 // BEGIN CUT HERE > 84 #include <ctime> > 85 double start_time; string timer() > 86 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 87 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 88 { os << "{ "; > 89 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 90 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 91 void verify_case(const int& Expected, const int& Received) { > 92 bool ok = (Expected == Received); > 93 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 94 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 95 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 96 #define END verify_case(_, CartInSupermarket().calcmin(a, b));} > 97 int main(){ > 98 > 99 CASE(0) > 100 int a_[] = {8}; > 101 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 102 int b = 3; > 103 int _ = 4; > 104 END > 105 CASE(1) > 106 int a_[] = {6,6,5}; > 107 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 108 int b = 3; > 109 int _ = 4; > 110 END > 111 CASE(2) > 112 int a_[] = {12,5,6,2,6,8}; > 113 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 114 int b = 4; > 115 int _ = 6; > 116 END > 117 CASE(3) > 118 int a_[] = {15,20,11,13,18,24,25,21,22,10,15,14,19}; > 119 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 120 int b = 0; > 121 int _ = 25; > 122 END > 123 CASE(4) > 124 int a_[] = {671122748,846444748,84701624,608579554,672060899,967957440,3 > 125 ,80693344,211737743,85405464,444633541,293184188,935462519,146753109,972886045,4 > 126 ,257574086,958464570,6294570,546189534,668105964,601197313,784337929,921840143,7 > 127 ,253400894,56411549,811940644,152086353,122638884,776352066,118932182,177589709, > 128 ,523761221,290027568,734517444,819458123,699130727,784698122,810265337,283326309 > 129 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 130 int b = 6478; > 131 int _ = 3805054; > 132 END > 133 CASE(5) > 134 int a_[] = {977827843, 601538780, 476956916, 821358251, 646377015, 47942 > 135 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 136 int b = 278304610; > 137 int _ = -1; > 138 END > 139 > 140 /* > 141 CASE(6) > 142 int a_[] = ; > 143 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 144 int b = ; > 145 int _ = ; > 146 END > 147 */ > 148 } > 149 // END CUT HERE