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

Added SRM/639-U/1A-U.cpp version [fca3dc328f41b941]

            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 AliceGame { public:
           23  + long long findMinimumValue(long long x, long long y)
           24  + {
           25  +  LL c = (LL)sqrt(x+y);
           26  +  for(LL n=max(0LL, c-10); n<=c+10; ++n)
           27  +   if(n*n == x+y)
           28  +    return solve(int(n), x);
           29  +  return -1;
           30  + }
           31  +
           32  + LL solve(int n, LL x)
           33  + {
           34  +  int cnt = 0;
           35  +  for(int t=n; t>=1; --t)
           36  +  {
           37  +   int s = 2*t-1;
           38  +   if(s <= x) {
           39  +    x -= s;
           40  +    cnt ++;
           41  +   }
           42  +  }
           43  +  return cnt;
           44  + }
           45  +};
           46  +
           47  +// BEGIN CUT HERE
           48  +#include <ctime>
           49  +double start_time; string timer()
           50  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           51  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           52  + { os << "{ ";
           53  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           54  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           55  +void verify_case(const long long& Expected, const long long& Received) {
           56  + bool ok = (Expected == Received);
           57  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           58  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           59  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           60  +#define END  verify_case(_, AliceGame().findMinimumValue(x, y));}
           61  +int main(){
           62  +
           63  +CASE(0)
           64  + long long x = 8LL;
           65  + long long y = 17LL;
           66  + long long _ = 2LL;
           67  +END
           68  +CASE(1)
           69  + long long x = 17LL;
           70  + long long y = 8LL;
           71  + long long _ = 3LL;
           72  +END
           73  +CASE(2)
           74  + long long x = 0LL;
           75  + long long y = 0LL;
           76  + long long _ = 0LL;
           77  +END
           78  +CASE(3)
           79  + long long x = 9LL;
           80  + long long y = 9LL;
           81  + long long _ = -1LL;
           82  +END
           83  +CASE(4)
           84  + long long x = 500000LL;
           85  + long long y = 500000LL;
           86  + long long _ = 294LL;
           87  +END
           88  +CASE(5)
           89  + long long x = 0LL;
           90  + long long y = 4LL;
           91  + long long _ = 0LL;
           92  +END
           93  +CASE(6)
           94  + long long x = 4LL;
           95  + long long y = 0LL;
           96  + long long _ = 2LL;
           97  +END
           98  +}
           99  +// END CUT HERE

Added SRM/639-U/1B.cpp version [b6a2a6266ec7de62]

            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 BoardFolding { public:
           23  + int howMany(int N, int M, vector <string> compressedPaper)
           24  + {
           25  +  // decode
           26  +  int tonumber[128];
           27  +  for(char c='0'; c<='9'; ++c) tonumber[c] = c-'0';
           28  +  for(char c='a'; c<='z'; ++c) tonumber[c] = c-'a' + 10;
           29  +  for(char c='A'; c<='Z'; ++c) tonumber[c] = c-'A' + 36;
           30  +  tonumber['#'] = 62;
           31  +  tonumber['@'] = 63;
           32  +
           33  +  vector<vector<int>> P(N, vector<int>(M));
           34  +  for(int i=0; i<N; ++i)
           35  +  for(int j=0; j<M; ++j)
           36  +   P[i][j] = (tonumber[compressedPaper[i][j / 6]] >> (j % 6)) % 2;
           37  +
           38  +  // solve
           39  +  return solve(N, M, P);
           40  + }
           41  +
           42  + int solve(int H, int W, const vector<vector<int>>& P)
           43  + {
           44  +  // transpose
           45  +  vector<vector<int>> PT(W, vector<int>(H));
           46  +  for(int y=0; y<H; ++y)
           47  +  for(int x=0; x<W; ++x)
           48  +   PT[x][y] = P[y][x];
           49  +
           50  +  // solve_each
           51  +  return solve_one(P) * solve_one(PT);
           52  + }
           53  +
           54  + int solve_one(const vector<vector<int>>& P)
           55  + {
           56  +  // hash
           57  +  vector<int> PH;
           58  +  map<vector<int>, int> hash;
           59  +  for(const auto& Pi: P) {
           60  +   if(!hash.count(Pi)) {
           61  +    int id = hash.size();
           62  +    hash[Pi] = id;
           63  +   }
           64  +   PH.push_back(hash[Pi]);
           65  +  }
           66  +
           67  +  // solve
           68  +  return solve_one(PH);
           69  + }
           70  +
           71  + int solve_one(const vector<int>& P)
           72  + {
           73  +  const int N = P.size();
           74  +
           75  +  vector<int> ok_range(N);
           76  +  for(int m=0; m<N; ++m)
           77  +   for(int w=1; m-w>=0 && m+w<=N; ++w) {
           78  +    if(P[m-w] != P[m+w-1])
           79  +     break;
           80  +    ok_range[m] = w;
           81  +   }
           82  +
           83  +  vector<vector<bool>> vis(N, vector<bool>(N+1));
           84  +
           85  +  function<void(int,int)> rec;
           86  +  rec = [&](int s, int e) {
           87  +   if(vis[s][e])
           88  +    return;
           89  +   vis[s][e] = true;
           90  +   for(int m=s+1; m<e; ++m)
           91  +    if(ok_range[m] >= min(m-s, e-m)) {
           92  +     if(m-s <= e-m)
           93  +      rec(m, e);
           94  +     if(e-m <= m-s)
           95  +      rec(s, m);
           96  +    }
           97  +  };
           98  +  rec(0, N);
           99  +
          100  +  int cnt = 0;
          101  +  for(int s=0; s<N; ++s)
          102  +  for(int e=s+1; e<=N; ++e)
          103  +   if(vis[s][e] == 1)
          104  +    ++cnt;
          105  +  return cnt;
          106  + }
          107  +};
          108  +
          109  +// BEGIN CUT HERE
          110  +#include <ctime>
          111  +double start_time; string timer()
          112  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          113  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          114  + { os << "{ ";
          115  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          116  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          117  +void verify_case(const int& Expected, const int& Received) {
          118  + bool ok = (Expected == Received);
          119  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          120  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          121  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          122  +#define END  verify_case(_, BoardFolding().howMany(N, M, compressedPaper));}
          123  +int main(){
          124  +
          125  +CASE(1)
          126  + int N = 2;
          127  + int M = 7;
          128  + string compressedPaper_[] = {"@@", "@@"};
          129  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          130  + int _ = 84;
          131  +END
          132  +CASE(0)
          133  + int N = 2;
          134  + int M = 2;
          135  + string compressedPaper_[] = {"1", "3"};
          136  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          137  + int _ = 1;
          138  +END
          139  +CASE(2)
          140  + int N = 4;
          141  + int M = 4;
          142  + string compressedPaper_[] = {"6", "9", "9", "6"};
          143  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          144  + int _ = 9;
          145  +END
          146  +CASE(3)
          147  + int N = 6;
          148  + int M = 1;
          149  + string compressedPaper_[] = {"0", "2", "6", "@", "4", "A"};
          150  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          151  + int _ = 6;
          152  +END
          153  +CASE(4)
          154  + int N = 3;
          155  + int M = 3;
          156  + string compressedPaper_[] = {"0", "2", "0"}
          157  +;
          158  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          159  + int _ = 1;
          160  +END
          161  +/*
          162  +CASE(5)
          163  + int N = ;
          164  + int M = ;
          165  + string compressedPaper_[] = ;
          166  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          167  + int _ = ;
          168  +END
          169  +CASE(6)
          170  + int N = ;
          171  + int M = ;
          172  + string compressedPaper_[] = ;
          173  +   vector <string> compressedPaper(compressedPaper_, compressedPaper_+sizeof(compressedPaper_)/sizeof(*compressedPaper_));
          174  + int _ = ;
          175  +END
          176  +*/
          177  +}
          178  +// END CUT HERE

Added SRM/639-U/1C-U.cpp version [526b59207f22295c]

            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  +LL gcd(LL a, LL b)
           23  +{
           24  + while(a)
           25  +  swap(a, b%=a);
           26  + return b;
           27  +}
           28  +
           29  +class ElectronicPet { public:
           30  + vector<long long> minimumSec(vector <int> period1, vector <int> time1, vector <int> period2, vector <int> time2)
           31  + {
           32  +  vector<LL> Q;
           33  +  for(int i=0; i<period1.size(); ++i)
           34  +   Q.push_back(solve(period1[i], period2[i], time1[i], time2[i]));
           35  +  return Q;
           36  + }
           37  +
           38  + LL solve(LL P1, LL P2, LL T1, LL T2)
           39  + {
           40  +  LL a1 = P1*(T1-1);
           41  +  LL b1 = P2*(T2-1);
           42  +
           43  +  if(gcd(P1, P2) != 1)
           44  +   return a1==b1 ? a1+1 : max(a1,b1);
           45  +
           46  +  // (P1, T1) is dominant.
           47  +  if(a1<b1 || (a1==b1 && P1<P2)) {
           48  +   swap(P1, P2);
           49  +   swap(T1, T2);
           50  +  }
           51  +
           52  +  // -1 == P2*k mod P1?
           53  +  // TODO: xgcd
           54  +  LL k=1;
           55  +  while(P2*k%P1 != P1-1)
           56  +   ++k;
           57  +  // During (P2*k+1)/P1+1 p1, I can use k p2.
           58  +  LL v = (P2*k+1)/P1+1;
           59  +  LL consume = T1/v*k;
           60  +  return max(P1*(T1-1), P1*(max(1LL,T1/v*v)-1)+1+P2*(max(1LL,T2-consume)-1));
           61  + }
           62  +};
           63  +
           64  +// BEGIN CUT HERE
           65  +#include <ctime>
           66  +double start_time; string timer()
           67  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           68  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           69  + { os << "{ ";
           70  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           71  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           72  +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
           73  + bool ok = (Expected == Received);
           74  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           75  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           76  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           77  +#define END  verify_case(_, ElectronicPet().minimumSec(period1, time1, period2, time2));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + int period1_[] = {2};
           82  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
           83  + int time1_[] = {2};
           84  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
           85  + int period2_[] = {2};
           86  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
           87  + int time2_[] = {3};
           88  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
           89  + long long __[] = {4 };
           90  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
           91  +END
           92  +CASE(1)
           93  + int period1_[] = {1};
           94  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
           95  + int time1_[] = {10};
           96  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
           97  + int period2_[] = {2};
           98  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
           99  + int time2_[] = {4};
          100  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
          101  + long long __[] = {13 };
          102  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          103  +END
          104  +CASE(2)
          105  + int period1_[] = {7357,10,2};
          106  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
          107  + int time1_[] = {7356,50,1000000};
          108  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
          109  + int period2_[] = {7356,3,3};
          110  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
          111  + int time2_[] = {7357,167,900000};
          112  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
          113  + long long __[] = {54110737, 510, 2799998 };
          114  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          115  +END
          116  +CASE(3)
          117  + int period1_[] = {407682800,484877059,830674177,227281073,19285523,560937767,919297611,23531788,
          118  +316159340,674806519,329433665,738538481,641235893,765181213,174785202,336152284,
          119  +570921683,400867251,774285402,943390771,837295831,294507056,493790893,522227203,
          120  +497924687,598834705,475831075,475114141,905813209,170832752,641484603,289813259,
          121  +862545694,178944781,755931661,620338556,970867185,83941427,135674814,895365643,
          122  +473440918,718282949,499031452,245406771,472643639,857414603,969063773,78465926,
          123  +1,7,2,8,7,7,3,8,1,2,8,6,1,7,10,5,3,10,1,5,5,7,1,1,10,9,3,8,5,6,7,3,7,7,5,3,1,4,
          124  +9,8,1,5,9,7,4,7,9,1};
          125  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
          126  + int time1_[] = {685321887,561847762,364868210,867285301,914945601,118787805,548332607,31355359,
          127  +803650261,960301524,266477641,39110673,474718169,71340489,687134789,493401968,
          128  +653058743,55748625,509077445,269937973,742890796,52585495,726357125,68477490,
          129  +4,7,9,9,7,6,1,7,3,8,6,9,1,9,9,6,10,6,8,8,10,9,6,5,781250147,170878774,855135226,
          130  +549059143,654877349,801427166,673830906,386629440,851395517,900791233,449728383,
          131  +250397037,69109668,512878462,27237926,285837889,66688537,91054902,717783650,388278693,
          132  +228914249,989188885,502709264,663817744,6,5,7,6,8,7,8,9,8,4,4,8,8,8,6,8,5,3,6,2,7,2,6,1};
          133  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
          134  + int period2_[] = {986705763,927574445,892948254,704066415,535436162,590308252,178891220,743922325,
          135  +856566021,518519690,225440136,785919924,5,5,5,9,9,4,7,10,7,9,4,4,818956627,417135379,
          136  +248892046,146009149,739277785,109423195,440198141,605525655,728478703,626172069,
          137  +630370468,130076349,4,1,5,4,9,10,3,1,4,9,3,1,583089191,388870099,453827819,111516603,
          138  +844765437,521615016,829962743,292223139,131621553,188850119,791754731,848542169,10,8,
          139  +1,9,10,3,9,4,3,4,4,4,278700059,895269545,67783376,711864145,956734152,422403629,
          140  +81840569,351747691,160762278,343337051,756026313,407474198,3,1,2,5,6,7,8,9,7,8,1,9};
          141  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
          142  + int time2_[] = {682390001,180499376,576561187,900180870,848774944,346873906,2,8,3,10,6,5,699143960,
          143  +814962202,251766107,732807531,131595022,598147784,3,2,3,3,7,10,637954336,380997052,
          144  +636675367,968908554,354172494,436377372,1,8,7,7,8,3,419710297,126884289,571143414,
          145  +264634798,264801163,157605826,4,4,6,8,5,5,485199156,117420995,773034099,419801566,
          146  +687631343,469269453,4,6,6,7,5,9,456349996,696828998,843725003,829027352,369267156,
          147  +515309802,7,6,8,2,10,6,75700282,191511000,510072386,297737413,817129266,664602545,
          148  +8,6,10,2,6,2,325802862,171214036,503091306,72109356,917444714,754965240,1,2,10,9,5,8};
          149  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
          150  + long long __[] = {673318145613570000, 272427089959414899, 514839304362869244, 633787117288414635, 454464797881688766, 204762528524964060, 504080854729204266, 737847637120104, 254081535792428400, 648017727926028437, 87786705585750600, 28884736289769232, 304406328380804024, 54588401143851944, 120100992721807176, 165858198137142628, 372845396080502786, 22347797649912624, 394171233376672488, 254656991527256412, 622019365541775645, 15486799026245664, 358668532896871732, 35760807548933267, 522456930371628045, 158927349266767329, 158463434481538836, 141469513282351397, 261831856132968005, 47749806160520345, 1, 4238679585, 4370872218, 3757032414, 4412593276, 4962708448, 1678841184, 671531416, 2855717065, 4476828215, 4260968262, 3591414745, 3493220164, 1717847397, 4253792751, 6859316824, 4845318865, 313863704, 282914382762833605, 45661513561458406, 350824378707972262, 46814844462883695, 580887191119526454, 244777992713291232, 2489888229, 3093035512, 851395522, 1801582464, 3597827056, 6788337352, 4563499950, 5574631976, 870962928, 7461246159, 3692671550, 1545929403, 717783656, 1941393460, 1144571240, 6924322188, 502709273, 663817749, 21097672781016579, 171453964937225455, 34574428259671760, 211948588227892740, 781775474424158280, 280730526428232176, 572883983, 1758738455, 1446860502, 343337051, 3780131565, 407474198, 977408583, 171214043, 1006182610, 360546775, 5504668278, 5284756673, 45, 9, 63, 64, 45, 63 };
          151  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          152  +END
          153  +/*
          154  +CASE(4)
          155  + int period1_[] = ;
          156  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
          157  + int time1_[] = ;
          158  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
          159  + int period2_[] = ;
          160  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
          161  + int time2_[] = ;
          162  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
          163  + long long __[] = ;
          164  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          165  +END
          166  +CASE(5)
          167  + int period1_[] = ;
          168  +   vector <int> period1(period1_, period1_+sizeof(period1_)/sizeof(*period1_));
          169  + int time1_[] = ;
          170  +   vector <int> time1(time1_, time1_+sizeof(time1_)/sizeof(*time1_));
          171  + int period2_[] = ;
          172  +   vector <int> period2(period2_, period2_+sizeof(period2_)/sizeof(*period2_));
          173  + int time2_[] = ;
          174  +   vector <int> time2(time2_, time2_+sizeof(time2_)/sizeof(*time2_));
          175  + long long __[] = ;
          176  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          177  +END
          178  +*/
          179  +}
          180  +// END CUT HERE