• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           53  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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::move(A0));
           62  +     if(!A1.empty())Next_Sec.emplace_back(std::move(A1));
           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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           84  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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] minutes
           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 to *spx.
           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].second*2);
           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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           94  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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,31438849,734849843,376589643,904285209
          125  +,80693344,211737743,85405464,444633541,293184188,935462519,146753109,972886045,496631016,601669536
          126  +,257574086,958464570,6294570,546189534,668105964,601197313,784337929,921840143,70408284,722040626
          127  +,253400894,56411549,811940644,152086353,122638884,776352066,118932182,177589709,538122558,127914469
          128  +,523761221,290027568,734517444,819458123,699130727,784698122,810265337,283326309,593596316,368671876};
          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, 479421294, 631863623, 446866211, 147800371, 777376159, 997915782, 317155640, 611683333, 461303085, 473215018, 363166652, 39746841, 109934430, 391345044, 41220128, 379970887, 445787345, 801764390, 886145854, 494435459, 974163022, 126739284, 708338618, 775199509, 378383243, 928615727, 606884963};
          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