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

Added SRM/550-U/1A.cpp version [463196d9224d114a]

            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 RotatingBot { public:
           23  + int minArea(vector <int> moves)
           24  + {
           25  +  if( moves.size() == 1 ) {
           26  +   int w = moves[0]+1;
           27  +   return w;
           28  +  }
           29  +  if( moves.size() == 2 ) {
           30  +   int w = moves[0]+1;
           31  +   int h = moves[1]+1;
           32  +   return w*h;
           33  +  }
           34  +  if( moves.size() == 3 ) {
           35  +   int w1 = moves[0]+1;
           36  +   int h = moves[1]+1;
           37  +   int w2 = moves[2]+1;
           38  +   return max(w1,w2)*h;
           39  +  }
           40  +  if( moves.size() == 4 ) {
           41  +   int w1 = moves[0]+1;
           42  +   int h1 = moves[1]+1;
           43  +   int w2 = moves[2]+1;
           44  +   int h2 = moves[3]+1;
           45  +   if( w1 > w2 )
           46  +    return -1;
           47  +   if( w1 == w2 ) {
           48  +    if( h1 <= h2 )
           49  +     return -1;
           50  +    else
           51  +     return w1*h1;
           52  +   }
           53  +   return w2*max(h1,h2);
           54  +  }
           55  +
           56  +  int w1 = moves[0]+1;
           57  +  int h1 = moves[1]+1;
           58  +  int w2 = moves[2]+1;
           59  +  int h2 = moves[3]+1;
           60  +  if( w1 > w2 )
           61  +   return -1;
           62  +  if( w1 == w2 ) {
           63  +   vector<int> rm = simulate(w1, h1, 0, 0);
           64  +   if( match(rm, moves) )
           65  +    return w1*h1;
           66  +   else
           67  +    return -1;
           68  +  } else {
           69  +   if( h2<h1 )
           70  +    return -1;
           71  +   vector<int> rm = simulate(w2, h2, w2-w1, h2-h1);
           72  +   if( match(rm, moves) )
           73  +    return w2*h2;
           74  +   else
           75  +    return -1;
           76  +  }
           77  + }
           78  +
           79  + vector<int> simulate(int w, int h, int x, int y)
           80  + {
           81  +  vector<int> moves;
           82  +  vector< vector<bool> > vis(h, vector<bool>(w));
           83  +  int dx[]={+1,0,-1,0};
           84  +  int dy[]={0,+1,0,-1};
           85  +  int d = 0;
           86  +  vis[y][x] = true;
           87  +  for(;;) {
           88  +   int cnt = 0;
           89  +   for(;;) {
           90  +    int xx=x+dx[d];
           91  +    int yy=y+dy[d];
           92  +    if( yy<0||h<=yy||xx<0||w<=xx||vis[yy][xx] )
           93  +     break;
           94  +    y=yy, x=xx;
           95  +    vis[y][x] = true;
           96  +    ++cnt;
           97  +   }
           98  +   d = (d+1)%4;
           99  +   if( cnt == 0 )
          100  +    break;
          101  +   moves.push_back(cnt);
          102  +  }
          103  +  return moves;
          104  + }
          105  +
          106  + bool match(const vector<int>& rm, const vector<int>& m)
          107  + {
          108  +  if(rm.size() < m.size())
          109  +   return false;
          110  +  for(int i=0; i+1<m.size(); ++i)
          111  +   if(rm[i] != m[i])
          112  +    return false;
          113  +  return rm[m.size()-1] >= m[m.size()-1];
          114  + }
          115  +};
          116  +
          117  +// BEGIN CUT HERE
          118  +#include <ctime>
          119  +double start_time; string timer()
          120  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          121  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          122  + { os << "{ ";
          123  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          124  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          125  +void verify_case(const int& Expected, const int& Received) {
          126  + bool ok = (Expected == Received);
          127  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          128  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          129  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          130  +#define END  verify_case(_, RotatingBot().minArea(moves));}
          131  +int main(){
          132  +
          133  +CASE(0)
          134  + int moves_[] = {15};
          135  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          136  + int _ = 16;
          137  +END
          138  +CASE(1)
          139  + int moves_[] = {3,10};
          140  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          141  + int _ = 44;
          142  +END
          143  +CASE(2)
          144  + int moves_[] = {1,1,1,1};
          145  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          146  + int _ = -1;
          147  +END
          148  +CASE(3)
          149  + int moves_[] = {9,5,11,10,11,4,10};
          150  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          151  + int _ = 132;
          152  +END
          153  +CASE(4)
          154  + int moves_[] = {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15};
          155  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          156  + int _ = 420;
          157  +END
          158  +CASE(5)
          159  + int moves_[] = {8,6,6,1};
          160  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          161  + int _ = -1;
          162  +END
          163  +CASE(6)
          164  + int moves_[] = {8,6,6};
          165  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          166  + int _ = 63;
          167  +END
          168  +CASE(7)
          169  + int moves_[] = {5,4,5,3,3};
          170  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          171  + int _ = 30;
          172  +END
          173  +CASE(8)
          174  +int moves_[] = {2,2,2,1};
          175  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          176  + int _ = 9;
          177  +END
          178  +/*
          179  +CASE(9)
          180  + int moves_[] = ;
          181  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          182  + int _ = ;
          183  +END
          184  +*/
          185  +}
          186  +// END CUT HERE

Added SRM/550-U/1B.cpp version [5862d1075889b63d]

            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 CheckerExpansion { public:
           23  + vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h)
           24  + {
           25  +  vector<string> answer(h, string(w, '.'));
           26  +  for(int y_=0; y_<h; ++y_)
           27  +  for(int x_=0; x_<w; ++x_) {
           28  +   LL y = y0 + y_;
           29  +   LL x = x0 + x_;
           30  +   if( (y+x)%2==1 )
           31  +    continue;
           32  +   LL N = (y+x)/2;
           33  +   if( t <= N )
           34  +    continue;
           35  +   LL k = x-N;
           36  +   if( k<0 || N<k )
           37  +    continue;
           38  +   if( is_comb_odd(N,k) )
           39  +    answer[h-y_-1][x_] = (N%2==0 ? 'A' : 'B');
           40  +  }
           41  +  return answer;
           42  + }
           43  +
           44  + bool is_comb_odd(LL n, LL k)
           45  + {
           46  +  for(LL m=1; m<=n; m<<=1)
           47  +   if( (k&m) && !(n&m) )
           48  +    return false;
           49  +  return true;
           50  + }
           51  +};
           52  +
           53  +// BEGIN CUT HERE
           54  +#include <ctime>
           55  +double start_time; string timer()
           56  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           57  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           58  + { os << "{ ";
           59  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           60  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           61  +void verify_case(const vector <string>& Expected, const vector <string>& Received) {
           62  + bool ok = (Expected == Received);
           63  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           64  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           65  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           66  +#define END  verify_case(_, CheckerExpansion().resultAfter(t, x0, y0, w, h));}
           67  +int main(){
           68  +
           69  +CASE(0)
           70  + long long t = 1LL;
           71  + long long x0 = 0LL;
           72  + long long y0 = 0LL;
           73  + int w = 4;
           74  + int h = 4;
           75  + string __[] = {"....", "....", "....", "A..." };
           76  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
           77  +END
           78  +CASE(1)
           79  + long long t = 5LL;
           80  + long long x0 = 4LL;
           81  + long long y0 = 1LL;
           82  + int w = 3;
           83  + int h = 4;
           84  + string __[] = {"A..", "...", "B..", ".B." };
           85  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
           86  +END
           87  +CASE(2)
           88  + long long t = 1024LL;
           89  + long long x0 = 1525LL;
           90  + long long y0 = 512LL;
           91  + int w = 20;
           92  + int h = 2;
           93  + string __[] = {"B...B...B...........", ".B.A.B.A.B.........." };
           94  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
           95  +END
           96  +CASE(3)
           97  + long long t = 53LL;
           98  + long long x0 = 85LL;
           99  + long long y0 = 6LL;
          100  + int w = 5;
          101  + int h = 14;
          102  + string __[] = {".....", ".....", "B....", ".B.A.", ".....", ".....", ".....", ".....", ".....", ".....", "B....", ".B...", "..B..", ".A.B." };
          103  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          104  +END
          105  +CASE(4)
          106  + long long t = 1000000000000LL;
          107  + long long x0 = 1000000000000LL;
          108  + long long y0 =  123456789123LL;
          109  + int w = 50;
          110  + int h = 50;
          111  + string __[] = {"?"};
          112  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          113  +END
          114  +/*
          115  +CASE(5)
          116  + long long t = LL;
          117  + long long x0 = LL;
          118  + long long y0 = LL;
          119  + int w = ;
          120  + int h = ;
          121  + string __[] = ;
          122  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          123  +END
          124  +*/
          125  +}
          126  +// END CUT HERE