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

Added SRM/544/1A.cpp version [1e07ad54dbeb74d6]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class ElectionFraudDiv1 { public:
           23  + int MinimumVoters(vector <int> percentages)
           24  + {
           25  +  for(int voter=1; voter<=100000; ++voter)
           26  +   if(possible(voter, percentages))
           27  +    return voter;
           28  +  return -1;
           29  + }
           30  +
           31  + bool possible(int V, const vector<int>& P)
           32  + {
           33  +  int L=0, R=0;
           34  +  for(int i=0; i<P.size(); ++i)
           35  +  {
           36  +   int p = P[i];
           37  +
           38  +   // p-0.5 <= x/V*100 < p+0.5
           39  +   // 2p-1  <= x/V*200 < 2p+1
           40  +
           41  +   int ll = (2*p-1)*V;
           42  +   int rr = (2*p+1)*V;
           43  +
           44  +   // ll <= x*200 < rr
           45  +
           46  +   int l = max(0, (ll+199)/200);
           47  +   int r = min(V, rr/200 - (rr%200 ? 0 : 1));
           48  +
           49  +   // l <= x <= r
           50  +
           51  +   if( l <= r )
           52  +    L+=l, R+=r;
           53  +   else
           54  +    return false;
           55  +  }
           56  +  return L<=V && V<=R;
           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 int& Expected, const int& 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(_, ElectionFraudDiv1().MinimumVoters(percentages));}
           74  +int main(){
           75  +
           76  +CASE(0)
           77  + int percentages_[] = {33, 33, 33};
           78  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
           79  + int _ = 3;
           80  +END
           81  +CASE(1)
           82  + int percentages_[] = {29, 29, 43};
           83  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
           84  + int _ = 7;
           85  +END
           86  +CASE(2)
           87  + int percentages_[] = {12, 12, 12, 12, 12, 12, 12, 12};
           88  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
           89  + int _ = -1;
           90  +END
           91  +CASE(3)
           92  + int percentages_[] = {13, 13, 13, 13, 13, 13, 13, 13};
           93  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
           94  + int _ = 8;
           95  +END
           96  +CASE(4)
           97  + int percentages_[] = {0, 1, 100};
           98  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
           99  + int _ = 200;
          100  +END
          101  +CASE(5)
          102  + int percentages_[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4};
          103  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
          104  + int _ = 97;
          105  +END
          106  +/*
          107  +CASE(6)
          108  + int percentages_[] = ;
          109  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
          110  + int _ = ;
          111  +END
          112  +CASE(7)
          113  + int percentages_[] = ;
          114  +   vector <int> percentages(percentages_, percentages_+sizeof(percentages_)/sizeof(*percentages_));
          115  + int _ = ;
          116  +END
          117  +*/
          118  +}
          119  +// END CUT HERE

Added SRM/544/1B.cpp version [83e9a8df96eca9df]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class FlipGame { public:
           23  + int minOperations(vector <string> board)
           24  + {
           25  +  int cnt = 0;
           26  +  while( !all_zero(board) ) {
           27  +   next(board);
           28  +   ++cnt;
           29  +  }
           30  +  return cnt;
           31  + }
           32  +
           33  + bool all_zero(const vector <string>& board)
           34  + {
           35  +  for(int i=0; i<board.size(); ++i)
           36  +   if( count(board[i].begin(), board[i].end(), '0') != board[i].size() )
           37  +    return false;
           38  +  return true;
           39  + }
           40  +
           41  + void next(vector<string>& board)
           42  + {
           43  +  int X=0;
           44  +  for(int y=0; y<board.size(); ++y)
           45  +  {
           46  +   int last1 = X-1;
           47  +   for(int x=X; x<board[y].size(); ++x)
           48  +    if( board[y][x] == '1' )
           49  +     last1 = x;
           50  +   X = last1+1;
           51  +   for(int x=0; x<X; ++x)
           52  +    board[y][x] = char('0'+'1'-board[y][x]);
           53  +  }
           54  + }
           55  +};
           56  +
           57  +// BEGIN CUT HERE
           58  +#include <ctime>
           59  +double start_time; string timer()
           60  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           61  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           62  + { os << "{ ";
           63  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           64  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           65  +void verify_case(const int& Expected, const int& Received) {
           66  + bool ok = (Expected == Received);
           67  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           68  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           69  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           70  +#define END  verify_case(_, FlipGame().minOperations(board));}
           71  +int main(){
           72  +
           73  +CASE(0)
           74  + string board_[] = {"1000",
           75  + "1110",
           76  + "1111"};
           77  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           78  + int _ = 1;
           79  +END
           80  +CASE(1)
           81  + string board_[] = {"1111",
           82  + "1111",
           83  + "1111"};
           84  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           85  + int _ = 1;
           86  +END
           87  +CASE(2)
           88  + string board_[] = {"00",
           89  + "00",
           90  + "00"};
           91  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           92  + int _ = 0;
           93  +END
           94  +CASE(3)
           95  + string board_[] = {
           96  + "00000000",
           97  + "00100000",
           98  + "01000000",
           99  + "00001000",
          100  + "00000000"};
          101  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          102  + int _ = 4;
          103  +END
          104  +CASE(4)
          105  + string board_[] = {"000000000000001100000000000000",
          106  + "000000000000011110000000000000",
          107  + "000000000000111111000000000000",
          108  + "000000000001111111100000000000",
          109  + "000000000011111111110000000000",
          110  + "000000000111111111111000000000",
          111  + "000000001100111111001100000000",
          112  + "000000011000011110000110000000",
          113  + "000000111100111111001111000000",
          114  + "000001111111111111111111100000",
          115  + "000011111111111111111111110000",
          116  + "000111111111000000111111111000",
          117  + "001111111111100001111111111100",
          118  + "011111111111110011111111111110",
          119  + "111111111111111111111111111111"};
          120  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          121  + int _ = 29;
          122  +END
          123  +/*
          124  +CASE(5)
          125  + string board_[] = ;
          126  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          127  + int _ = ;
          128  +END
          129  +CASE(6)
          130  + string board_[] = ;
          131  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          132  + int _ = ;
          133  +END
          134  +*/
          135  +}
          136  +// END CUT HERE

Added SRM/544/1C.cpp version [26bf2a688a29c24d]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +static const int MODVAL = 1000000007; // must be prime for op/
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {} // x>=0
           28  + mint(size_t x):val(x%MODVAL) {} // x>=0
           29  + mint(LL     x):val(x%MODVAL) {} // x>=0
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x+=y; }
           35  +mint operator-(mint x, mint y) { return x-=y; }
           36  +mint operator*(mint x, mint y) { return x*=y; }
           37  +mint operator-(mint x) { return mint(0) - x; }
           38  +
           39  +vector<mint> vMul( const vector< vector<mint> >& A, const vector<mint>& B )
           40  +{
           41  + const int n = A.size();
           42  +
           43  + vector<mint> C(n);
           44  + for(int i=0; i<n; ++i)
           45  +  for(int j=0; j<n; ++j)
           46  +   C[i] += A[i][j] * B[j];
           47  + return C;
           48  +}
           49  +
           50  +vector< vector<mint> > mMul( const vector< vector<mint> >& A, const vector< vector<mint> >& B )
           51  +{
           52  + const int n = A.size();
           53  +
           54  + vector< vector<mint> > C(n, vector<mint>(n));
           55  + for(int i=0; i<n; ++i)
           56  +  for(int j=0; j<n; ++j) {
           57  +   mint Cij = 0;
           58  +   for(int k=0; k<n; ++k)
           59  +    Cij += A[i][k] * B[k][j];
           60  +   C[i][j] = Cij;
           61  +  }
           62  + return C;
           63  +}
           64  +
           65  +vector< vector<mint> > mPow( vector< vector<mint> > M, LL t ) // t>0
           66  +{
           67  + vector< vector<mint> > R;
           68  + for(; t; t>>=1, M=mMul(M,M))
           69  +  if( t&1 )
           70  +   R = (R.empty() ? M : mMul(R,M));
           71  + return R;
           72  +}
           73  +
           74  +class SplittingFoxes { public:
           75  + int sum(long long n, int S_, int L_, int R_)
           76  + {
           77  +  mint S(S_), L(L_), R(R_);
           78  +
           79  +  enum {PR, PT, PL, PB, XR, XT, XL, XB, YR, YT, YL, YB, __};
           80  +  vector< vector<mint> > M(13, vector<mint>(13));
           81  +  M[PR][PR] = S; M[PR][YR] = S; M[PR][PT] = L; M[PR][PB] = R;
           82  +  M[PT][PT] = S; M[PT][XT] = S; M[PT][PL] = L; M[PT][PR] = R;
           83  +  M[PL][PL] = S; M[PL][YL] =-S; M[PL][PB] = L; M[PL][PT] = R;
           84  +  M[PB][PB] = S; M[PB][XB] =-S; M[PB][PR] = L; M[PB][PL] = R;
           85  +  M[XR][XR] = S; M[XR][__] = S; M[XR][XT] = L; M[XR][XB] = R;
           86  +  M[XT][XT] = S; M[XT][__] = 0; M[XT][XL] = L; M[XT][XR] = R;
           87  +  M[XL][XL] = S; M[XL][__] =-S; M[XL][XB] = L; M[XL][XT] = R;
           88  +  M[XB][XB] = S; M[XB][__] = 0; M[XB][XR] = L; M[XB][XL] = R;
           89  +  M[YR][YR] = S; M[YR][__] = 0; M[YR][YT] = L; M[YR][YB] = R;
           90  +  M[YT][YT] = S; M[YT][__] = S; M[YT][YL] = L; M[YT][YR] = R;
           91  +  M[YL][YL] = S; M[YL][__] = 0; M[YL][YB] = L; M[YL][YT] = R;
           92  +  M[YB][YB] = S; M[YB][__] =-S; M[YB][YR] = L; M[YB][YL] = R;
           93  +  M[__][__] = S+L+R;
           94  +  vector<mint> V(13);
           95  +  V[__] = 1;
           96  +  return vMul(mPow(M, n), V)[PR].val;
           97  + }
           98  +};
           99  +
          100  +// BEGIN CUT HERE
          101  +#include <ctime>
          102  +double start_time; string timer()
          103  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          104  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          105  + { os << "{ ";
          106  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          107  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          108  +void verify_case(const int& Expected, const int& Received) {
          109  + bool ok = (Expected == Received);
          110  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          111  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          112  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          113  +#define END  verify_case(_, SplittingFoxes().sum(n, S, L, R));}
          114  +int main(){
          115  +
          116  +CASE(0)
          117  + long long n = 58LL;
          118  + int S = 2;
          119  + int L = 0;
          120  + int R = 0;
          121  + int _ = 0;
          122  +END
          123  +CASE(1)
          124  + long long n = 3LL;
          125  + int S = 1;
          126  + int L = 1;
          127  + int R = 0;
          128  + int _ = 1;
          129  +END
          130  +CASE(2)
          131  + long long n = 5LL;
          132  + int S = 1;
          133  + int L = 3;
          134  + int R = 2;
          135  + int _ = 34;
          136  +END
          137  +CASE(3)
          138  + long long n = 5LL;
          139  + int S = 1;
          140  + int L = 2;
          141  + int R = 3;
          142  + int _ = 999999973;
          143  +END
          144  +CASE(4)
          145  + long long n = 123456789LL;
          146  + int S = 987654321;
          147  + int L = 544;
          148  + int R = 544;
          149  + int _ = 0;
          150  +END
          151  +CASE(5)
          152  + long long n = 65536LL;
          153  + int S = 1024;
          154  + int L = 512;
          155  + int R = 4096;
          156  + int _ = 371473914;
          157  +END
          158  +/*
          159  +CASE(6)
          160  + long long n = LL;
          161  + int S = ;
          162  + int L = ;
          163  + int R = ;
          164  + int _ = ;
          165  +END
          166  +CASE(7)
          167  + long long n = LL;
          168  + int S = ;
          169  + int L = ;
          170  + int R = ;
          171  + int _ = ;
          172  +END
          173  +*/
          174  +}
          175  +// END CUT HERE