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

Added SRM/TCO17-2A-U/1A.cpp version [d18b982672b1ce1e]

            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 gcd(int a, int b)
           23  +{
           24  + while (a)
           25  +  swap(a, b %= a);
           26  + return b;
           27  +}
           28  +
           29  +
           30  +class FoxAndCake2 { public:
           31  + string isPossible(int c, int s)
           32  + {
           33  +  return solve(c, s) ? "Possible" : "Impossible";
           34  + }
           35  +
           36  + bool solve(int a, int b)
           37  + {
           38  +  if (gcd(a, b) != 1)
           39  +   return true;
           40  +
           41  +  for (int x = 2; x <= 100 && x < a; ++x)
           42  +   for (int y = 2; y <= 100 && y < b; ++y)
           43  +    if (gcd(x, y) != 1 && gcd(a - x, b - y) != 1)
           44  +     return true;
           45  +  return false;
           46  + }
           47  +};
           48  +
           49  +// BEGIN CUT HERE
           50  +#include <ctime>
           51  +double start_time; string timer()
           52  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           53  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           54  + { os << "{ ";
           55  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           56  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           57  +void verify_case(const string& Expected, const string& Received) {
           58  + bool ok = (Expected == Received);
           59  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           60  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           61  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           62  +#define END  verify_case(_, FoxAndCake2().isPossible(c, s));}
           63  +int main(){
           64  +
           65  +CASE(0)
           66  + int c = 74;
           67  + int s = 109;
           68  + string _ = "Possible";
           69  +END
           70  +CASE(1)
           71  + int c = 1000000000;
           72  + int s = 1000000000;
           73  + string _ = "Possible";
           74  +END
           75  +CASE(2)
           76  + int c = 1;
           77  + int s = 58;
           78  + string _ = "Impossible";
           79  +END
           80  +CASE(3)
           81  + int c = 223092871;
           82  + int s = 446185741;
           83  + string _ = "Possible";
           84  +END
           85  +/*
           86  +CASE(4)
           87  + int c = ;
           88  + int s = ;
           89  + string _ = ;
           90  +END
           91  +*/
           92  +}
           93  +// END CUT HERE

Added SRM/TCO17-2A-U/1B-C.cpp version [5207bb27f05cf282]

            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 DistanceZeroAndOne { public:
           23  + vector <string> construct(vector <int> dist0, vector <int> dist1)
           24  + {
           25  +  const vector<string> IMPOSSIBLE;
           26  +  const int N = dist0.size();
           27  +  const int d01 = dist0[1];
           28  +  if (dist0[0] != 0) return IMPOSSIBLE;
           29  +  if (dist1[1] != 0) return IMPOSSIBLE;
           30  +  if (dist0[1] != dist1[0]) return IMPOSSIBLE;
           31  +
           32  +  map<pair<int, int>, int> repr;
           33  +  for (int x = 0; x < N; ++x)
           34  +   repr[make_pair(dist0[x], dist1[x])] = x;
           35  +
           36  +  vector<string> ans(N, string(N, 'N'));
           37  +  ans[0][1] = ans[1][0] = d01 == 1 ? 'Y' : 'N';
           38  +  for (int x = 2; x < N; ++x) {
           39  +   const int d0 = dist0[x];
           40  +   const int d1 = dist1[x];
           41  +   if (d0==0 || d1==0 || d0+d1<d01)
           42  +    return IMPOSSIBLE;
           43  +   if (d0 == 1) ans[0][x] = ans[x][0] = 'Y';
           44  +   if (d1 == 1) ans[1][x] = ans[x][1] = 'Y';
           45  +
           46  +   if (d0 + d1 == d01) { // bone
           47  +    if (repr.count(make_pair(d0 - 1, d1 + 1))) {
           48  +     int p = repr[make_pair(d0 - 1, d1 + 1)];
           49  +     ans[p][x] = ans[x][p] = 'Y';
           50  +    }
           51  +    else {
           52  +     return IMPOSSIBLE;
           53  +    }
           54  +
           55  +    if (repr.count(make_pair(d0 + 1, d1 - 1))) {
           56  +     int p = repr[make_pair(d0 + 1, d1 - 1)];
           57  +     ans[p][x] = ans[x][p] = 'Y';
           58  +    }
           59  +    else {
           60  +     return IMPOSSIBLE;
           61  +    }
           62  +   }
           63  +   else if(abs(d0 - d1) == d01) { // d0/d1 children
           64  +    if (repr.count(make_pair(d0 - 1, d1 - 1))) {
           65  +     int p = repr[make_pair(d0 - 1, d1 - 1)];
           66  +     ans[p][x] = ans[x][p] = 'Y';
           67  +    }
           68  +    else {
           69  +     return IMPOSSIBLE;
           70  +    }
           71  +   }
           72  +   else {
           73  +    // mid
           74  +    if (repr.count(make_pair(d0 - 1, d1 - 1))) {
           75  +     int p = repr[make_pair(d0 - 1, d1 - 1)];
           76  +     ans[p][x] = ans[x][p] = 'Y';
           77  +    }
           78  +    else {
           79  +     if (repr.count(make_pair(d0 - 1, d1 + 1))) {
           80  +      int p = repr[make_pair(d0 - 1, d1 + 1)];
           81  +      ans[p][x] = ans[x][p] = 'Y';
           82  +     }
           83  +     else if (repr.count(make_pair(d0 - 1, d1))) {
           84  +      int p = repr[make_pair(d0 - 1, d1)];
           85  +      ans[p][x] = ans[x][p] = 'Y';
           86  +     } else {
           87  +      return IMPOSSIBLE;
           88  +     }
           89  +
           90  +     if (repr.count(make_pair(d0 + 1, d1 - 1))) {
           91  +      int p = repr[make_pair(d0 + 1, d1 - 1)];
           92  +      ans[p][x] = ans[x][p] = 'Y';
           93  +     }
           94  +     else if (repr.count(make_pair(d0, d1 - 1))) {
           95  +      int p = repr[make_pair(d0, d1 - 1)];
           96  +      ans[p][x] = ans[x][p] = 'Y';
           97  +     } else {
           98  +      return IMPOSSIBLE;
           99  +     }
          100  +    }
          101  +   }
          102  +  }
          103  +  return ans;
          104  + }
          105  +};
          106  +
          107  +// BEGIN CUT HERE
          108  +#include <ctime>
          109  +double start_time; string timer()
          110  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          111  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          112  + { os << "{ ";
          113  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          114  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          115  +void verify_case(const vector <string>& Expected, const vector <string>& Received) {
          116  + bool ok = (Expected == Received);
          117  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          118  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          119  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          120  +#define END  verify_case(_, DistanceZeroAndOne().construct(dist0, dist1));}
          121  +int main(){
          122  +
          123  +CASE(0)
          124  + int dist0_[] = {0,2,1};
          125  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          126  + int dist1_[] = {2,0,1};
          127  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          128  + string __[] = {"NNY", "NNY", "YYN" };
          129  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          130  +END
          131  +CASE(1)
          132  + int dist0_[] = {0,2,1};
          133  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          134  + int dist1_[] = {1,0,2};
          135  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          136  + vector <string> _;
          137  +END
          138  +CASE(2)
          139  + int dist0_[] = {3,1,1,1};
          140  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          141  + int dist1_[] = {1,0,1,1};
          142  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          143  + vector <string> _;
          144  +END
          145  +CASE(3)
          146  + int dist0_[] = {0,1,1,1};
          147  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          148  + int dist1_[] = {1,0,1,1};
          149  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          150  + string __[] = {"NYYY", "YNYY", "YYNN", "YYNN" };
          151  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          152  +END
          153  +CASE(4)
          154  + int dist0_[] = {0,3,1,2,2,3,4,4};
          155  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          156  + int dist1_[] = {3,0,2,1,2,3,4,4};
          157  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          158  + string __[] = {"NNYNNNNN", "NNNYNNNN", "YNNYYNNN", "NYYNYNNN", "NNYYNYNN", "NNNNYNYY", "NNNNNYNN", "NNNNNYNN" };
          159  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          160  +END
          161  +CASE(5)
          162  + int dist0_[] = {0,1};
          163  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          164  + int dist1_[] = {1,0};
          165  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          166  + string __[] = {"NY", "YN" };
          167  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          168  +END
          169  +/*
          170  +CASE(6)
          171  + int dist0_[] = ;
          172  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          173  + int dist1_[] = ;
          174  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          175  + string __[] = ;
          176  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          177  +END
          178  +CASE(7)
          179  + int dist0_[] = ;
          180  +   vector <int> dist0(dist0_, dist0_+sizeof(dist0_)/sizeof(*dist0_));
          181  + int dist1_[] = ;
          182  +   vector <int> dist1(dist1_, dist1_+sizeof(dist1_)/sizeof(*dist1_));
          183  + string __[] = ;
          184  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          185  +END
          186  +*/
          187  +}
          188  +// END CUT HERE