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

Added SRM/522-U/1A.cpp version [e8ec418b9332bc9f]

            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 RowAndCoins { public:
           23  + string getWinner(string cells)
           24  + {
           25  +  int n = cells.size();
           26  +  int v = 0;
           27  +  for(int i=0; i<n; ++i)
           28  +   v = (v<<1) | (cells[i]=='B');
           29  +  memo.clear();
           30  +  return rec(0, v, n, 0) ? "Bob" : "Alice";
           31  + }
           32  +
           33  + vector<int> memo;
           34  + int rec(int p, const int v, const int n, int mask)
           35  + {
           36  +  int key = mask*2+p;
           37  +  if( key >= memo.size() )
           38  +   memo.resize(key+1, -1);
           39  +  if( memo[key] >= 0 )
           40  +   return memo[key];
           41  +
           42  +  for(int i=0; i<n; ++i)
           43  +   if( mask == (1<<n)-1 - (1<<i) )
           44  +    return memo[key] = (v&(1<<i) ? 1 : 0);
           45  +
           46  +  bool p_win = false;
           47  +  for(int s=0; s<n; ++s)
           48  +   for(int e=s+1; e<=n; ++e) if( e-s != n ) {
           49  +    int mm = mask;
           50  +    for(int i=s; i<e; ++i) {
           51  +     if( mask&(1<<i) )
           52  +      goto next;
           53  +     mm |= (1<<i);
           54  +    }
           55  +    if( mm == (1<<n)-1 )
           56  +     goto next;
           57  +    if( p == rec(p^1, v, n, mm) )
           58  +     p_win = true;
           59  +   next:;
           60  +   }
           61  +  return memo[key] = (p_win ?  p : p^1);
           62  + }
           63  +};
           64  +
           65  +// BEGIN CUT HERE
           66  +#include <ctime>
           67  +double start_time; string timer()
           68  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           69  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           70  + { os << "{ ";
           71  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           72  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           73  +void verify_case(const string& Expected, const string& Received) {
           74  + bool ok = (Expected == Received);
           75  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           76  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           77  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           78  +#define END  verify_case(_, RowAndCoins().getWinner(cells));}
           79  +int main(){
           80  +
           81  +CASE(0)
           82  + string cells = "ABBB";
           83  + string _ = "Alice";
           84  +END
           85  +CASE(1)
           86  + string cells = "BBBB";
           87  + string _ = "Bob";
           88  +END
           89  +CASE(2)
           90  + string cells = "BA";
           91  + string _ = "Alice";
           92  +END
           93  +CASE(3)
           94  + string cells = "BABBABBB";
           95  + string _ = "Bob";
           96  +END
           97  +CASE(4)
           98  + string cells = "ABABBBABAABBAA";
           99  + string _ = "Alice";
          100  +END
          101  +CASE(5)
          102  + string cells = "BBBAAABBAAABBB";
          103  + string _ = "Bob";
          104  +END
          105  +CASE(6)
          106  + string cells = "A";
          107  + string _ = "Alice";
          108  +END
          109  +CASE(7)
          110  + string cells = "B";
          111  + string _ = "Bob";
          112  +END
          113  +
          114  +}
          115  +// END CUT HERE

Added SRM/522-U/1B.cpp version [34827d4e4ac8d217]

            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 CorrectMultiplication { public:
           23  + long long getMinimum(int a, int b, int c)
           24  + {
           25  +  return solve(a,b,c);
           26  + }
           27  +
           28  + LL solve(LL a, LL b, LL c)
           29  + {
           30  +  if( a > b )
           31  +   swap(a,b);
           32  +  LL vv = (1LL<<62);
           33  +  for(LL A=1; A*A <= (a+b+c)*2; ++A)
           34  +   vv = min(vv, best_of(A,a,b,c));
           35  +  return vv;
           36  + }
           37  +
           38  + LL best_of(LL A, LL a, LL b, LL c)
           39  + {
           40  +  LL Bl = 1;
           41  +  LL Br = a+b+c;
           42  +  while( Bl+3 < Br )
           43  +  {
           44  +   LL Bc1 = (Bl*2+Br*1) / 3;
           45  +   LL Bc2 = (Bl*1+Br*2) / 3;
           46  +   LL cc1 = abs(A-a)+abs(Bc1-b)+abs(A*Bc1-c);
           47  +   LL cc2 = abs(A-a)+abs(Bc2-b)+abs(A*Bc2-c);
           48  +   if(cc1 < cc2)
           49  +    Br = Bc2;
           50  +   else
           51  +    Bl = Bc1;
           52  +  }
           53  +  LL vv = (1LL<<62);
           54  +  for(LL B=Bl; B<=Br; ++B)
           55  +   vv = min(vv, abs(A-a)+abs(B-b)+abs(A*B-c));
           56  +  return vv;
           57  + }
           58  +};
           59  +
           60  +// BEGIN CUT HERE
           61  +#include <ctime>
           62  +double start_time; string timer()
           63  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           64  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           65  + { os << "{ ";
           66  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           67  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           68  +void verify_case(const long long& Expected, const long long& Received) {
           69  + bool ok = (Expected == Received);
           70  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           71  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           72  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           73  +#define END  verify_case(_, CorrectMultiplication().getMinimum(a, b, c));}
           74  +int main(){
           75  +
           76  +CASE(0)
           77  + int a = 19;
           78  + int b = 28;
           79  + int c = 522;
           80  + long long _ = 2LL;
           81  +END
           82  +CASE(1)
           83  + int a = 10;
           84  + int b = 30;
           85  + int c = 500;
           86  + long long _ = 11LL;
           87  +END
           88  +CASE(2)
           89  + int a = 11111;
           90  + int b = 11111;
           91  + int c = 123454321;
           92  + long long _ = 0LL;
           93  +END
           94  +CASE(3)
           95  + int a = 1000;
           96  + int b = 100;
           97  + int c = 10;
           98  + long long _ = 1089LL;
           99  +END
          100  +CASE(4)
          101  + int a = 399;
          102  + int b = 522;
          103  + int c = 199999;
          104  + long long _ = 24LL;
          105  +END
          106  +CASE(5)
          107  + int a = 1000000000;
          108  + int b = 1000000000;
          109  + int c = 1000000000;
          110  + long long _ = -1LL;
          111  +END
          112  +/*
          113  +CASE(6)
          114  + int a = ;
          115  + int b = ;
          116  + int c = ;
          117  + long long _ = LL;
          118  +END
          119  +*/
          120  +}
          121  +// END CUT HERE

Added SRM/522-U/1C-U.cpp version [2049344b195d192d]

            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 PointErasing { public:
           23  + vector<int> ans;
           24  +
           25  + vector <int> getOutcomes(vector <int> y)
           26  + {
           27  +  rec(1, y, y[0], y[1], 1);
           28  +  return ans;
           29  + }
           30  +
           31  + void rec(int i, const vector<int>& y, int lo, int hi, int c)
           32  + {
           33  +  if( i == y.size() ) {
           34  +   if(c>1)
           35  +    ans.push_back(c);
           36  +   return;
           37  +  }
           38  +  rec(i+1, y, lo, hi, c);
           39  +
           40  +  if( lo < y[i] && y[i] < hi ) {
           41  +   ans.push_back(c+1);
           42  +   return;
           43  +  }
           44  +
           45  + }
           46  +};
           47  +
           48  +// BEGIN CUT HERE
           49  +#include <ctime>
           50  +double start_time; string timer()
           51  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           52  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           53  + { os << "{ ";
           54  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           55  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           56  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           57  + bool ok = (Expected == Received);
           58  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           59  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           60  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           61  +#define END  verify_case(_, PointErasing().getOutcomes(y));}
           62  +int main(){
           63  +
           64  +CASE(0)
           65  + int y_[] = { 1, 2, 1, 1, 0, 4, 3 };
           66  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           67  + int __[] = {4, 6 };
           68  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           69  +END
           70  +CASE(1)
           71  + int y_[] = { 0, 0, 4, 4, 8, 8, 4, 4 };
           72  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           73  + int __[] = {6 };
           74  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           75  +END
           76  +CASE(2)
           77  + int y_[] = { 522 };
           78  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           79  + int __[] = {1 };
           80  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           81  +END
           82  +CASE(3)
           83  + int y_[] = { 19, 19, 19, 19, 19, 19 };
           84  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           85  + int __[] = {6 };
           86  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           87  +END
           88  +CASE(4)
           89  + int y_[] = { 0, 1, 2, 3, 4 };
           90  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           91  + int __[] = {2 };
           92  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           93  +END
           94  +CASE(5)
           95  + int y_[] = { 7, 8, 8, 7, 6, 7, 9, 3, 5, 0 };
           96  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
           97  + int __[] = {3, 4, 5 };
           98  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           99  +END
          100  +CASE(6)
          101  + int y_[] = { 3, 2, 3, 3, 4, 3, 4, 3, 3, 1, 5, 3 };
          102  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          103  + int __[] = {4, 5, 6, 7, 9 };
          104  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          105  +END
          106  +CASE(7)
          107  + int y_[] = { 5, 5, 4, 4, 5, 8, 5, 5, 5, 5, 5, 9, 2, 0, 9, 4, 5, 5, 3, 4, 4, 4, 4, 7, 4 };
          108  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          109  + int __[] = {6, 7, 8, 10, 11, 12, 13, 15, 16, 17 };
          110  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          111  +END
          112  +CASE(8)
          113  + int y_[] = ;
          114  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          115  + int __[] = ;
          116  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          117  +END
          118  +CASE(9)
          119  + int y_[] = ;
          120  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          121  + int __[] = ;
          122  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          123  +END
          124  +
          125  +}
          126  +// END CUT HERE