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

Added SRM/623-U/1A.cpp version [5a7a82e56d0038ed]

            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 UniformBoard { public:
           23  + int getBoard(vector <string> board, int K)
           24  + {
           25  +  const int N = board.size();
           26  +
           27  +  int A=0, P=0;
           28  +  for(int y=0; y<N; ++y)
           29  +  for(int x=0; x<N; ++x) {
           30  +   if(board[y][x]=='P')++P;
           31  +   if(board[y][x]=='A')++A;
           32  +  }
           33  +
           34  +  int best = 0;
           35  +  for(int y=0; y<N; ++y)
           36  +  for(int x=0; x<N; ++x)
           37  +  for(int yy=y+1; yy<=N; ++yy)
           38  +  for(int xx=x+1; xx<=N; ++xx)
           39  +  {
           40  +   int a=0, p=0;
           41  +   for(int i=y; i<yy; ++i)
           42  +   for(int k=x; k<xx; ++k) {
           43  +    if(board[i][k]=='P')++p;
           44  +    if(board[i][k]=='A')++a;
           45  +   }
           46  +   int move = calc(A,P,N*N-A-P,a,p,(yy-y)*(xx-x)-a-p);
           47  +   if(move<=K)
           48  +    best = max(best, (yy-y)*(xx-x));
           49  +  }
           50  +  return best;
           51  + }
           52  +
           53  + int calc(int A, int P, int E, int a, int p, int e)
           54  + {
           55  +  const int INF = 0x7ffffff;
           56  +  A -= a;
           57  +  P -= p;
           58  +  E -= e;
           59  +
           60  +  if(e+p > A)
           61  +   return INF;
           62  +
           63  +  int move = 0;
           64  +  if(e) {
           65  +   move += e;
           66  +   E += e;
           67  +   A -= e;
           68  +   a += e;
           69  +   e = 0;
           70  +  }
           71  +  if(p) {
           72  +   if(E == 0)
           73  +    return INF;
           74  +   move += 2*p;
           75  +  }
           76  +  return move;
           77  + }
           78  +};
           79  +
           80  +// BEGIN CUT HERE
           81  +#include <ctime>
           82  +double start_time; string timer()
           83  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           84  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           85  + { os << "{ ";
           86  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           87  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           88  +void verify_case(const int& Expected, const int& Received) {
           89  + bool ok = (Expected == Received);
           90  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           91  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           92  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           93  +#define END  verify_case(_, UniformBoard().getBoard(board, K));}
           94  +int main(){
           95  +
           96  +CASE(0)
           97  + string board_[] = {"AP",
           98  + ".A"};
           99  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          100  + int K = 0;
          101  + int _ = 1;
          102  +END
          103  +CASE(1)
          104  + string board_[] = {"AP",
          105  + ".A"};
          106  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          107  + int K = 1;
          108  + int _ = 2;
          109  +END
          110  +CASE(2)
          111  + string board_[] = {"PPP",
          112  + "APA",
          113  + "A.P"};
          114  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          115  + int K = 2;
          116  + int _ = 3;
          117  +END
          118  +CASE(3)
          119  + string board_[] = {"AAA",
          120  + "PPP",
          121  + "AAA"};
          122  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          123  + int K = 10;
          124  + int _ = 3;
          125  +END
          126  +CASE(4)
          127  + string board_[] = {"."};
          128  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          129  + int K = 1000;
          130  + int _ = 0;
          131  +END
          132  +CASE(5)
          133  + string board_[] = {"PPAAPA..AP",
          134  + "PPA.APAP..",
          135  + "..P.AA.PPP",
          136  + "P.P..APAA.",
          137  + "P.P..P.APA",
          138  + "PPA..AP.AA",
          139  + "APP..AAPAA",
          140  + "P.P.AP...P",
          141  + ".P.A.PAPPA",
          142  + "..PAPAP..P"};
          143  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          144  + int K = 10;
          145  + int _ = 15;
          146  +END
          147  +/*
          148  +CASE(6)
          149  + string board_[] = ;
          150  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          151  + int K = ;
          152  + int _ = ;
          153  +END
          154  +CASE(7)
          155  + string board_[] = ;
          156  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          157  + int K = ;
          158  + int _ = ;
          159  +END
          160  +*/
          161  +}
          162  +// END CUT HERE

Added SRM/623-U/1B-U.cpp version [328f1d8dd94187c9]

            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 CatchTheBeat { public:
           23  + int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset)
           24  + {
           25  +  vector<int> x(n), y(n);
           26  +  x[0] = x0;
           27  +  for(int i=1; i<n; ++i)
           28  +   x[i] = int((LL(x[i-1]) * a + b) % mod1);
           29  +  for(int i=0; i<n; ++i)
           30  +   x[i] = x[i] - offset;
           31  +
           32  +  y[0] = y0;
           33  +  for(int i=1; i<n; ++i)
           34  +      y[i] = int((LL(y[i-1]) * c + d) % mod2);
           35  +
           36  +  return solve(n, x, y);
           37  + }
           38  +
           39  + int solve(int N, const vector<int>& x, const vector<int>& y)
           40  + {
           41  +  vector<pair<int,int>> tx;
           42  +  for(int i=0; i<N; ++i)
           43  +   tx.emplace_back(y[i], x[i]);
           44  +  tx.emplace_back(0, 0);
           45  +  sort(tx.begin(), tx.end());
           46  +
           47  +  vector<vector<int>> score_table(tx.size());
           48  +  score_table[0].push_back(0);
           49  +  int best_score = 0;
           50  +  for(int c=1; c<tx.size(); ++c)
           51  +  {
           52  +   int pre = -1;
           53  +   for(int bs=best_score; bs>=0; --bs) {
           54  +    for(int p: score_table[bs])
           55  +     if(tx[c].first - tx[p].first >=  abs(tx[c].second - tx[p].second))
           56  +      {pre = bs; goto found_pre;}
           57  +   }
           58  +  found_pre:
           59  +   if(pre>=0) {
           60  +    score_table[pre+1].push_back(c);
           61  +    best_score = max(best_score, pre+1);
           62  +   }
           63  +  }
           64  +  return best_score;
           65  + }
           66  +};
           67  +
           68  +// BEGIN CUT HERE
           69  +#include <ctime>
           70  +double start_time; string timer()
           71  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           72  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           73  + { os << "{ ";
           74  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           75  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           76  +void verify_case(const int& Expected, const int& Received) {
           77  + bool ok = (Expected == Received);
           78  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           79  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           80  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           81  +#define END  verify_case(_, CatchTheBeat().maxCatched(n, x0, y0, a, b, c, d, mod1, mod2, offset));}
           82  +int main(){
           83  +
           84  +CASE(0)
           85  + int n = 3;
           86  + int x0 = 0;
           87  + int y0 = 0;
           88  + int a = 1;
           89  + int b = 1;
           90  + int c = 1;
           91  + int d = 1;
           92  + int mod1 = 100;
           93  + int mod2 = 100;
           94  + int offset = 1;
           95  + int _ = 2;
           96  +END
           97  +CASE(1)
           98  + int n = 1;
           99  + int x0 = 0;
          100  + int y0 = 1234;
          101  + int a = 0;
          102  + int b = 0;
          103  + int c = 0;
          104  + int d = 0;
          105  + int mod1 = 1000000000;
          106  + int mod2 = 1000000000;
          107  + int offset = 1000;
          108  + int _ = 1;
          109  +END
          110  +CASE(2)
          111  + int n = 1;
          112  + int x0 = 0;
          113  + int y0 = 999;
          114  + int a = 0;
          115  + int b = 0;
          116  + int c = 0;
          117  + int d = 0;
          118  + int mod1 = 1000000000;
          119  + int mod2 = 1000000000;
          120  + int offset = 1000;
          121  + int _ = 0;
          122  +END
          123  +CASE(3)
          124  + int n = 100;
          125  + int x0 = 0;
          126  + int y0 = 0;
          127  + int a = 1;
          128  + int b = 1;
          129  + int c = 1;
          130  + int d = 1;
          131  + int mod1 = 3;
          132  + int mod2 = 58585858;
          133  + int offset = 1;
          134  + int _ = 66;
          135  +END
          136  +CASE(4)
          137  + int n = 500000;
          138  + int x0 = 123456;
          139  + int y0 = 0;
          140  + int a = 1;
          141  + int b = 0;
          142  + int c = 1;
          143  + int d = 1;
          144  + int mod1 = 1000000000;
          145  + int mod2 = 1000000000;
          146  + int offset = 0;
          147  + int _ = 376544;
          148  +END
          149  +CASE(5)
          150  + int n = 500000;
          151  + int x0 = 0;
          152  + int y0 = 0;
          153  + int a = 0;
          154  + int b = 0;
          155  + int c = 0;
          156  + int d = 0;
          157  + int mod1 = 1;
          158  + int mod2 = 1;
          159  + int offset = 0;
          160  + int _ = 500000;
          161  +END
          162  +CASE(6)
          163  + int n = 10;
          164  + int x0 = 999999957;
          165  + int y0 = 79;
          166  + int a = 993948167;
          167  + int b = 24597383;
          168  + int c = 212151897;
          169  + int d = 999940854;
          170  + int mod1 = 999999986;
          171  + int mod2 = 999940855;
          172  + int offset = 3404;
          173  + int _ = 3;
          174  +END
          175  +/*
          176  +CASE(7)
          177  + int n = ;
          178  + int x0 = ;
          179  + int y0 = ;
          180  + int a = ;
          181  + int b = ;
          182  + int c = ;
          183  + int d = ;
          184  + int mod1 = ;
          185  + int mod2 = ;
          186  + int offset = ;
          187  + int _ = ;
          188  +END
          189  +CASE(8)
          190  + int n = ;
          191  + int x0 = ;
          192  + int y0 = ;
          193  + int a = ;
          194  + int b = ;
          195  + int c = ;
          196  + int d = ;
          197  + int mod1 = ;
          198  + int mod2 = ;
          199  + int offset = ;
          200  + int _ = ;
          201  +END
          202  +*/
          203  +}
          204  +// END CUT HERE

Added SRM/623-U/1C-U.cpp version [2ec89edcc9c2afbe]

            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 AliceAndFriends { public:
           23  + double getMoney(vector <int> cards)
           24  + {
           25  +  int N = cards.size();
           26  +  double ex = 0.0;
           27  +  for(int alice=0; alice<N; ++alice)
           28  +  {
           29  +   double best = -1e+300;
           30  +
           31  +   int R = cards[alice];
           32  +   for(int B=0; B<=R; ++B)
           33  +   {
           34  +    double total_gain = 0.0;
           35  +    for(int i=0; i<N; ++i) if(i!=alice)
           36  +    {
           37  +     int r = cards[i];
           38  +     double best_you = 1e+300;
           39  +     int b;
           40  +     if(R==r)
           41  +      b = B;
           42  +     else if(R < r)
           43  +      b = 0;
           44  +     else {
           45  +     }
           46  +
           47  +     // r-b > R-B
           48  +     // r-b > R+B
           49  +     // r+b > R-B
           50  +     // r+b > R+B
           51  +     // ができるだけ成り立ちたい
           52  +     for(int b=0; b<=r; ++b)
           53  +     {
           54  +      // Alice: [R-B or R+B]
           55  +      // You: [r-b or r+b]
           56  +      double s = 0.0;
           57  +      s += (r-b<R-B ? +0.25 : r-b>R-B ? -0.25 : 0);
           58  +      s += (r-b<R+B ? +0.25 : r-b>R+B ? -0.25 : 0);
           59  +      s += (r+b<R-B ? +0.25 : r+b>R-B ? -0.25 : 0);
           60  +      s += (r+b<R+B ? +0.25 : r+b>R+B ? -0.25 : 0);
           61  +      best_you = min(best_you, s);
           62  +     }
           63  +     total_gain += best_you;
           64  +    }
           65  +    best = max(best, total_gain);
           66  +   }
           67  +   ex += best;
           68  +  }
           69  +  return ex / N;
           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 double& Expected, const double& Received) {
           82  + bool ok = (abs(Expected - Received) < 1e-9);
           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(_, AliceAndFriends().getMoney(cards));}
           87  +int main(){
           88  +
           89  +CASE(0)
           90  + int cards_[] = {10, 1};
           91  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
           92  + double _ = 0.0;
           93  +END
           94  +CASE(1)
           95  + int cards_[] = {10, 9};
           96  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
           97  + double _ = -0.25;
           98  +END
           99  +CASE(2)
          100  + int cards_[] = {1, 3};
          101  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          102  + double _ = 0.0;
          103  +END
          104  +CASE(3)
          105  + int cards_[] = {1000000000, 1000000000};
          106  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          107  + double _ = 0.0;
          108  +END
          109  +CASE(4)
          110  + int cards_[] = {42, 468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996,
          111  + 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539,
          112  + 870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674, 665, 142, 712, 254, 869};
          113  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          114  + double _ = -9.095;
          115  +END
          116  +/*
          117  +CASE(5)
          118  + int cards_[] = ;
          119  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          120  + double _ = ;
          121  +END
          122  +CASE(6)
          123  + int cards_[] = ;
          124  +   vector <int> cards(cards_, cards_+sizeof(cards_)/sizeof(*cards_));
          125  + double _ = ;
          126  +END
          127  +*/
          128  +}
          129  +// END CUT HERE