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

Added SRM/TCO17-3A-U/1A.cpp version [3bd5d04ce69009dd]

            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  +bool is_coprime(int a, int b)
           30  +{
           31  + return gcd(a, b) == 1;
           32  +}
           33  +
           34  +class CoprimeMatrix { public:
           35  + vector<bool> is_p;
           36  + vector<int> primes;
           37  +
           38  + string isPossible(vector <string> coprime)
           39  + {
           40  +  // eratos
           41  +  if (is_p.empty()) {
           42  +   is_p.assign(60, true);
           43  +   is_p[0] = is_p[1] = false;
           44  +   for (int p = 2; p < is_p.size(); ++p) if (is_p[p]) {
           45  +    primes.push_back(p);
           46  +    for (int q = p + p; q < is_p.size(); q += p)
           47  +     is_p[q] = false;
           48  +   }
           49  +  }
           50  +
           51  +  return solve(coprime) ? "Possible" : "Impossible";
           52  + }
           53  +
           54  + bool solve(const vector<string>& coprime)
           55  + {
           56  +  const int N = coprime.size();
           57  +
           58  +  // sanity
           59  +  for (int i = 0; i < N; ++i)
           60  +  for (int k = 0; k < N; ++k)
           61  +   if (coprime[i][k] != coprime[k][i])
           62  +    return false;
           63  +
           64  +  // trivial case
           65  +  for (int i = 0; i < N; ++i)
           66  +  for (int k = 0; k < N; ++k)
           67  +   if (is_coprime(1 + i, 1 + k) != (coprime[i][k] == 'Y'))
           68  +    goto nontrivial;
           69  +  return true;
           70  +
           71  + nontrivial:
           72  +  for (int i = 0; i < N; ++i)
           73  +   if(coprime[i][i]=='Y')
           74  +    return false;
           75  +
           76  +  vector<vector<bool>> cos;
           77  +  for (int off = 0; off < N; ++off) {
           78  +   vector<bool> co;
           79  +   for (int t = 0; t + off < N; ++t)
           80  +    co.push_back(coprime[off][off + t] == 'Y');
           81  +
           82  +   // x+off coprime with k in 0,1,2,,,,co.size()-1 iff co[k]
           83  +
           84  +   if (!can(co))
           85  +    return false;
           86  +   cos.push_back(co);
           87  +  }
           88  +
           89  +  for (int p = 2; p < N; ++p) if (is_p[p]) {
           90  +   int last = -1;
           91  +   for(int o=0; o<cos.size() && cos[o].size()>p; ++o)
           92  +    if (cos[o][p] == false) {
           93  +     if (last!=-1 && (o-last)!=p)
           94  +      return false;
           95  +     last = o;
           96  +    }
           97  +    else {
           98  +     if (o - last >= p)
           99  +      return false;
          100  +    }
          101  +  }
          102  +
          103  +  return true;
          104  + }
          105  +
          106  + bool can(const vector<bool>& co)
          107  + {
          108  +  // Can there be a positive n such that coprime(n,i) == co[i] ?
          109  +  vector<int> prime_factors;
          110  +  for (int p = 2; p < co.size(); ++p)
          111  +   if (is_p[p] && !co[p])
          112  +    prime_factors.push_back(p);
          113  +
          114  +  for (int k = 0; k < co.size(); ++k)
          115  +   if (is_coprimev(k, prime_factors) != co[k]) {
          116  +    prime_factors.push_back(primes.back());
          117  +    for (int k = 0; k < co.size(); ++k)
          118  +     if (is_coprimev(k, prime_factors) != co[k])
          119  +      return false;
          120  +    return true;
          121  +   }
          122  +  return true;
          123  + }
          124  +
          125  + bool is_coprimev(int k, const vector<int>& pfs)
          126  + {
          127  +  for (int p : pfs)
          128  +   if (k%p == 0)
          129  +    return false;
          130  +  return true;
          131  + }
          132  +};
          133  +
          134  +// BEGIN CUT HERE
          135  +#include <ctime>
          136  +double start_time; string timer()
          137  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          138  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          139  + { os << "{ ";
          140  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          141  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          142  +void verify_case(const string& Expected, const string& Received) {
          143  + bool ok = (Expected == Received);
          144  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          145  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          146  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          147  +#define END  verify_case(_, CoprimeMatrix().isPossible(coprime));}
          148  +int main(){
          149  +
          150  +CASE(0)
          151  + string coprime_[] = {"NYNYN",
          152  + "YNYYN",
          153  + "NYNYN",
          154  + "YYYNY",
          155  + "NNNYN"};
          156  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          157  + string _ = "Possible";
          158  +END
          159  +CASE(1)
          160  + string coprime_[] = {"NY",
          161  + "NN"};
          162  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          163  + string _ = "Impossible";
          164  +END
          165  +CASE(2)
          166  + string coprime_[] = {"NYYYYN",
          167  + "YNYNNN",
          168  + "YYNYYY",
          169  + "YNYNYN",
          170  + "YNYYNY",
          171  + "NNYNYN"};
          172  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          173  + string _ = "Possible";
          174  +END
          175  +CASE(3)
          176  + string coprime_[] = {"NN",
          177  + "NN"};
          178  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          179  + string _ = "Impossible";
          180  +END
          181  +CASE(4)
          182  +// both x and x+1 and x+2 are coprime with 2
          183  + string coprime_[] =
          184  +{
          185  + "NYYY",
          186  + "YNYY",
          187  + "YYNY",
          188  + "YYYN",
          189  +};
          190  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          191  + string _ = "Impossible";
          192  +END
          193  +CASE(5)
          194  +// x+1 == 1
          195  +string coprime_[] = { "NY", "YY" };
          196  +   vector <string> coprime(coprime_, coprime_+sizeof(coprime_)/sizeof(*coprime_));
          197  + string _ = "Impossible";
          198  +END
          199  +CASE(6)
          200  +string coprime_[] = { "Y" };
          201  +vector <string> coprime(coprime_, coprime_ + sizeof(coprime_) / sizeof(*coprime_));
          202  +string _ = "Possible";
          203  +END
          204  +}
          205  +// END CUT HERE