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

Added SRM/676-U/1A.cpp version [4948478ca41a65d0]

            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 WaterTank { public:
           23  + double minOutputRate(vector <int> t, vector <int> x, int C)
           24  + {
           25  +  double L=0, R=1000000; // (L,R]
           26  +  for(int _=0; _<10000; ++_) {
           27  +   double mid = (L+R)/2;
           28  +   (can(t, x, C, mid) ? R : L) = mid;
           29  +  }
           30  +  return R;
           31  + }
           32  +
           33  + bool can(const vector<int>& t, const vector<int>& x, int C, double R)
           34  + {
           35  +  double v = 0;
           36  +  for(int i=0; i<t.size(); ++i) {
           37  +   v = max(0.0, v+(x[i]-R)*t[i]);
           38  +   if(v > C)
           39  +    return false;
           40  +  }
           41  +  return true;
           42  + }
           43  +};
           44  +
           45  +// BEGIN CUT HERE
           46  +#include <ctime>
           47  +double start_time; string timer()
           48  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           49  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           50  + { os << "{ ";
           51  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           52  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           53  +void verify_case(const double& Expected, const double& Received) {
           54  + bool ok = (abs(Expected - Received) < 1e-9);
           55  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           56  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           57  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           58  +#define END  verify_case(_, WaterTank().minOutputRate(t, x, C));}
           59  +int main(){
           60  +
           61  +CASE(0)
           62  + int t_[] = {3,3};
           63  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
           64  + int x_[] = {1,2};
           65  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           66  + int C = 3;
           67  + double _ = 0.9999999999999999;
           68  +END
           69  +CASE(1)
           70  + int t_[] = {1,2,3,4,5};
           71  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
           72  + int x_[] = {5,4,3,2,1};
           73  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           74  + int C = 10;
           75  + double _ = 1.9999999999999996;
           76  +END
           77  +CASE(2)
           78  + int t_[] = {5949,3198,376,3592,4019,3481,5609,3840,6092,4059};
           79  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
           80  + int x_[] = {29,38,96,84,10,2,39,27,76,94};
           81  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           82  + int C = 1000000000;
           83  + double _ = 0.0;
           84  +END
           85  +CASE(3)
           86  + int t_[] = {9,3,4,8,1,2,5,7,6};
           87  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
           88  + int x_[] = {123,456,789,1011,1213,1415,1617,1819,2021};
           89  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           90  + int C = 11;
           91  + double _ = 2019.1666666666665;
           92  +END
           93  +CASE(4)
           94  + int t_[] = {100};
           95  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
           96  + int x_[] = {1000};
           97  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
           98  + int C = 12345;
           99  + double _ = 876.55;
          100  +END
          101  +/*
          102  +CASE(5)
          103  + int t_[] = ;
          104  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
          105  + int x_[] = ;
          106  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          107  + int C = ;
          108  + double _ = ;
          109  +END
          110  +CASE(6)
          111  + int t_[] = ;
          112  +   vector <int> t(t_, t_+sizeof(t_)/sizeof(*t_));
          113  + int x_[] = ;
          114  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          115  + int C = ;
          116  + double _ = ;
          117  +END
          118  +*/
          119  +}
          120  +// END CUT HERE

Added SRM/676-U/1B.cpp version [5b1986066a865398]

            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  +int lsb(int x) {
           23  + for(int i=0 ;; ++i)
           24  +  if(x&(1<<i))
           25  +   return i;
           26  +}
           27  +
           28  +
           29  +class BoardEscape { public:
           30  + string findWinner(vector <string> s, int k)
           31  + {
           32  +  const int H = s.size(), W = s[0].size();
           33  +  const int dy[] = {-1,+1,0,0};
           34  +  const int dx[] = {0,0,-1,+1};
           35  +
           36  +  vector<vector<vector<int>>> G_history;
           37  +  for(int t=0; t<=256; ++t) {
           38  +   vector<vector<int>> G(H, vector<int>(W));
           39  +   for(int y=0; y<H; ++y)
           40  +   for(int x=0; x<W; ++x) if(s[y][x]!='#') {
           41  +    if(G_history.empty())
           42  +     G[y][x] = 0;
           43  +    else {
           44  +     if(s[y][x]=='E')
           45  +      G[y][x] = 0;
           46  +     else {
           47  +      int nf = 0xffffffff;
           48  +      for(int _=0; _<4; ++_) {
           49  +       int yy=y+dy[_], xx=x+dx[_];
           50  +       if(0<=yy&&yy<H&&0<=xx&&xx<W&&s[yy][xx]!='#')
           51  +        nf &= ~(1<<G_history.back()[yy][xx]);
           52  +      }
           53  +      G[y][x] = lsb(nf);
           54  +     }
           55  +    }
           56  +   }
           57  +   G_history.emplace_back(G);
           58  +  }
           59  +
           60  +  int ans = 0;
           61  +  for(int y=0; y<H; ++y)
           62  +  for(int x=0; x<W; ++x) if(s[y][x]=='T') {
           63  +   if(k < G_history.size())
           64  +    ans ^= G_history[k][y][x];
           65  +   else
           66  +    ans ^= G_history[((k-1)%64)+193][y][x];
           67  +  }
           68  +  return (ans ? "Alice" : "Bob");
           69  + }
           70  +};
           71  +
           72  +// BEGIN CUT HERE
           73  +#include <ctime>
           74  +double start_time; string timer()
           75  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           76  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           77  + { os << "{ ";
           78  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           79  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           80  +void verify_case(const string& Expected, const string& Received) {
           81  + bool ok = (Expected == Received);
           82  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           83  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           84  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           85  +#define END  verify_case(_, BoardEscape().findWinner(s, k));}
           86  +int main(){
           87  +CASE(0)
           88  + string s_[] = {"TE"};
           89  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
           90  + int k = 2;
           91  + string _ = "Alice";
           92  +END
           93  +CASE(1)
           94  + string s_[] = {"E#E",
           95  + "#T#",
           96  + "E#E"};
           97  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
           98  + int k = 1000000;
           99  + string _ = "Bob";
          100  +END
          101  +CASE(2)
          102  + string s_[] = {"T.T.T.",
          103  + ".E.E.E"};
          104  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          105  + int k = 1;
          106  + string _ = "Alice";
          107  +END
          108  +CASE(3)
          109  + string s_[] = {"TTE"};
          110  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          111  + int k = 6;
          112  + string _ = "Alice";
          113  +END
          114  +CASE(4)
          115  + string s_[] = {"..........................",
          116  + "......TTT..TTT..T...T.....",
          117  + ".....T.....T..T.TT.TT.....",
          118  + "......TTT..TTT..T.T.T.....",
          119  + ".........T.T.T..T...T.....",
          120  + "......TTT..T..T.T...T.....",
          121  + "..........................",
          122  + "...E#E#E#E#E#E#E#E#E#E#...",
          123  + "..........................",
          124  + "......TTT..TTT...TTT......",
          125  + ".....T........T.T.........",
          126  + "......TTT.....T..TTT......",
          127  + ".....T...T...T..T...T.....",
          128  + "......TTT....T...TTT......",
          129  + "..........................",
          130  + "...#E#E#E#E#E#E#E#E#E#E...",
          131  + "..........................",
          132  + "....TT...T...T..T.TTT.T...",
          133  + "...T.....T...T..T.T...T...",
          134  + "...T.TT..T...TTTT.TT..T...",
          135  + "...T..T..T...T..T.T.......",
          136  + "....TT...TTT.T..T.T...T...",
          137  + ".........................."};
          138  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          139  + int k = 987654321;
          140  + string _ = "Bob";
          141  +END
          142  +/*
          143  +CASE(5)
          144  + string s_[] = ;
          145  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          146  + int k = ;
          147  + string _ = ;
          148  +END
          149  +CASE(6)
          150  + string s_[] = ;
          151  +   vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
          152  + int k = ;
          153  + string _ = ;
          154  +END
          155  +*/
          156  +}
          157  +// END CUT HERE