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

Added SRM/517-U/1A.cpp version [64a4787ef91ae507]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class CompositeSmash { public:
           23  + string thePossible(int N, int target)
           24  + {
           25  +  return avoid(N, target) ? "No" : "Yes";
           26  + }
           27  +
           28  + bool avoid(LL N, LL T)
           29  + {
           30  +  if( N == T )
           31  +   return false;
           32  +  if( N < T )
           33  +   return true;
           34  +  bool composit = false;
           35  +  for(LL d=2; d*d<=N && d<N; ++d)
           36  +   if( N%d==0 ) {
           37  +    composit = true;
           38  +    if( avoid(d,T) && avoid(N/d,T) )
           39  +     return true;
           40  +   }
           41  +  return !composit;
           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 string& Expected, const string& Received) {
           54  + bool ok = (Expected == Received);
           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(_, CompositeSmash().thePossible(N, target));}
           59  +int main(){
           60  +
           61  +CASE(0)
           62  + int N = 517;
           63  + int target = 47;
           64  + string _ = "Yes";
           65  +END
           66  +CASE(1)
           67  + int N = 8;
           68  + int target = 4;
           69  + string _ = "Yes";
           70  +END
           71  +CASE(2)
           72  + int N = 12;
           73  + int target = 6;
           74  + string _ = "No";
           75  +END
           76  +CASE(3)
           77  + int N = 5;
           78  + int target = 8;
           79  + string _ = "No";
           80  +END
           81  +CASE(4)
           82  + int N = 100000;
           83  + int target = 100000;
           84  + string _ = "Yes";
           85  +END
           86  +CASE(5)
           87  + int N = 5858;
           88  + int target = 2;
           89  + string _ = "Yes";
           90  +END
           91  +CASE(6)
           92  + int N = 81461;
           93  + int target = 2809;
           94  + string _ = "No";
           95  +END
           96  +CASE(7)
           97  + int N = 65536;
           98  + int target = 256;
           99  + string _ = "No";
          100  +END
          101  +/*
          102  +CASE(8)
          103  + int N = 72;
          104  + int target = 4;
          105  + string _ = "Yes";
          106  +END
          107  +CASE(9)
          108  + int N = ;
          109  + int target = ;
          110  + string _ = ;
          111  +END
          112  +*/
          113  +}
          114  +// END CUT HERE

Added SRM/517-U/1B.cpp version [498d0330a61d76ab]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +static const LL MODVAL = 1000000007;
           23  +class AdjacentSwaps { public:
           24  + int theCount(vector <int> p)
           25  + {
           26  +  int N = p.size();
           27  +
           28  +  vector< set<int> > child(N-1);
           29  +  for(int s=0; s<N; ++s)
           30  +  {
           31  +   int e = find(p.begin(), p.end(), s) - p.begin();
           32  +   if( s < e ) {
           33  +    // s-1 <-- s --> s+1 --> ... --> e-1 <-- e
           34  +    if(s-1>=0) child[s].insert(s-1);
           35  +    for(int i=s; i+1<=e-1; ++i) child[i].insert(i+1);
           36  +    if(e<N-1) child[e].insert(e-1);
           37  +   }
           38  +   else if( s > e ) {
           39  +    // e-1 --> e <-- e+1 <-- ... <-- s-1 --> s
           40  +    if(e-1>=0) child[e-1].insert(e);
           41  +    for(int i=e; i+1<=s-1; ++i) child[i+1].insert(i);
           42  +    if(s<N-1) child[s-1].insert(s);
           43  +   }
           44  +   else // s == e
           45  +    return 0;
           46  +  }
           47  +
           48  +  // cycle
           49  +  N--;
           50  +  for(int i=0; i+1<N; ++i)
           51  +   if( child[i].count(i+1) && child[i+1].count(i) )
           52  +    return 0;
           53  +
           54  +  vector<int> q(N-1);
           55  +  for(int i=0; i+1<N; ++i) {
           56  +   if( child[i].count(i+1) )
           57  +    q[i] = +1;
           58  +   else
           59  +    q[i] = -1;
           60  +  }
           61  +
           62  +  LL sum = 0;
           63  +  for(int i=0; i<N; ++i)
           64  +   sum += rec(q, 0, i, N-i-1);
           65  +  return int(sum % MODVAL);
           66  + }
           67  +
           68  + map<pair<int,int>, LL> memo;
           69  + LL rec(const vector<int>& q, int i, int x, int y)
           70  + {
           71  +  if( i == q.size() )
           72  +   return 1;
           73  +  pair<int,int> key(i,x);
           74  +  if( memo.count(key) )
           75  +   return memo[key];
           76  +
           77  +  if( q[i] == -1 ) {
           78  +   LL sum = 0;
           79  +   for(int k=0; k<x; ++k)
           80  +    sum += rec(q, i+1, k, y+(x-k-1));
           81  +   return memo[key] = sum % MODVAL;
           82  +  } else {
           83  +   LL sum = 0;
           84  +   for(int k=0; k<y; ++k)
           85  +    sum += rec(q, i+1, x+k, y-k-1);
           86  +   return memo[key] = sum % MODVAL;
           87  +  }
           88  + }
           89  +};
           90  +
           91  +// BEGIN CUT HERE
           92  +#include <ctime>
           93  +double start_time; string timer()
           94  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           95  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           96  + { os << "{ ";
           97  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           98  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           99  +void verify_case(const int& Expected, const int& Received) {
          100  + bool ok = (Expected == Received);
          101  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          102  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          103  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          104  +#define END  verify_case(_, AdjacentSwaps().theCount(p));}
          105  +int main(){
          106  +
          107  +CASE(0)
          108  + int p_[] = {1, 2, 0};
          109  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          110  + int _ = 1;
          111  +END
          112  +CASE(1)
          113  + int p_[] = {0, 1};
          114  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          115  + int _ = 0;
          116  +END
          117  +CASE(2)
          118  + int p_[] = {2, 0, 3, 1};
          119  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          120  + int _ = 2;
          121  +END
          122  +CASE(3)
          123  + int p_[] = {1, 0, 3, 2};
          124  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          125  + int _ = 0;
          126  +END
          127  +CASE(4)
          128  + int p_[] = {1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17};
          129  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          130  + int _ = 716743312;
          131  +END
          132  +/*
          133  +CASE(5)
          134  + int p_[] = ;
          135  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          136  + int _ = ;
          137  +END
          138  +CASE(6)
          139  + int p_[] = ;
          140  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          141  + int _ = ;
          142  +END
          143  +*/
          144  +}
          145  +// END CUT HERE

Added SRM/517-U/1C-U.cpp version [e962c41de1c7ae6b]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ColorfulBoard { public:
           23  + int theMin(vector <string> board)
           24  + {
           25  +  int H = board.size();
           26  +  int W = board[0].size();
           27  +
           28  +  vector<bool> okY(H), okX(W);
           29  +  for(bool changed=true; changed; )
           30  +  {
           31  +   changed = false;
           32  +   for(int y=0; y<H; ++y) if(!okY[y])
           33  +   {
           34  +    set<char> cc(board[y].begin(), board[y].end());
           35  +    cc.erase('*');
           36  +    if( cc.size() == 1 ) {
           37  +     okY[y] = changed = true;
           38  +     for(int x=0; x<W; ++x)
           39  +      board[y][x] = '*';
           40  +    }
           41  +   }
           42  +   for(int x=0; x<W; ++x) if(!okX[x])
           43  +   {
           44  +    set<char> cc;
           45  +    for(int y=0; y<H; ++y)
           46  +     cc.insert(board[y][x]);
           47  +    cc.erase('*');
           48  +    if( cc.size() == 1 ) {
           49  +     okX[x] = changed = true;
           50  +     for(int y=0; y<H; ++y)
           51  +      board[y][x] = '*';
           52  +    }
           53  +   }
           54  +  }
           55  +
           56  +  int okys = 0;
           57  +  for(int y=0; y<H; ++y)
           58  +   if( okY[y] )
           59  +    okys++;
           60  +  int okxs = 0;
           61  +  for(int x=0; x<W; ++x)
           62  +   if( okX[x] )
           63  +    okxs++;
           64  +  if( okxs!=W && okys!=H )
           65  +   return -1;
           66  +  if( okxs!=W )
           67  +   return okys;
           68  +  if( okys!=H )
           69  +   return okxs;
           70  +  return min(okxs, okys);
           71  + }
           72  +};
           73  +
           74  +// BEGIN CUT HERE
           75  +#include <ctime>
           76  +double start_time; string timer()
           77  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           78  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           79  + { os << "{ ";
           80  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           81  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           82  +void verify_case(const int& Expected, const int& Received) {
           83  + bool ok = (Expected == Received);
           84  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           85  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           86  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           87  +#define END  verify_case(_, ColorfulBoard().theMin(board));}
           88  +int main(){
           89  +
           90  +CASE(0)
           91  + string board_[] = {"SSS",
           92  + "SRR",
           93  + "SMM"};
           94  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           95  + int _ = 4;
           96  +END
           97  +CASE(1)
           98  + string board_[] = {"BBBBBBBB",
           99  + "BBBBBBBB",
          100  + "BBBBBBBB",
          101  + "BBBBBBBB",
          102  + "BBBBBBBB"};
          103  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          104  + int _ = 5;
          105  +END
          106  +CASE(2)
          107  + string board_[] = {"Ab",
          108  + "bA"};
          109  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          110  + int _ = -1;
          111  +END
          112  +CASE(3)
          113  + string board_[] = {"iiiii",
          114  + "iwiwi"}
          115  +;
          116  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          117  + int _ = 4;
          118  +END
          119  +CASE(4)
          120  + string board_[] = {"ffffffffff",
          121  + "xfxxoofoxo",
          122  + "ffffffffff",
          123  + "xfxxoofoxo",
          124  + "ffffffffff",
          125  + "ooxxoofoxo",
          126  + "xfxxoofoxo",
          127  + "xfxxoxfxxo",
          128  + "ffxxofffxo",
          129  + "xfxxoxfxxo"};
          130  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          131  + int _ = 17;
          132  +END
          133  +/*
          134  +CASE(5)
          135  + string board_[] = ;
          136  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          137  + int _ = ;
          138  +END
          139  +CASE(6)
          140  + string board_[] = ;
          141  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          142  + int _ = ;
          143  +END
          144  +*/
          145  +}
          146  +// END CUT HERE