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

Added SRM/575-U/1A.cpp version [f9f0a181bc884140]

            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 TheNumberGameDivOne { public:
           23  + string find(long long n)
           24  + {
           25  +  return solve(n) ? "John" : "Brus";
           26  + }
           27  +
           28  + bool solve(LL n)
           29  + {
           30  +  if(n==1)
           31  +   return false;
           32  +  if( (n & (n-1)) == 0 )
           33  +  {
           34  +   int k=0;
           35  +   for(; (1LL<<k)!=n; ++k) {}
           36  +   return k%2==0;
           37  +  }
           38  +  return n%2==0;
           39  + }
           40  +};
           41  +
           42  +// BEGIN CUT HERE
           43  +#include <ctime>
           44  +double start_time; string timer()
           45  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           46  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           47  + { os << "{ ";
           48  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           49  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           50  +void verify_case(const string& Expected, const string& Received) {
           51  + bool ok = (Expected == Received);
           52  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           53  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           54  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           55  +#define END  verify_case(_, TheNumberGameDivOne().find(n));}
           56  +int main(){
           57  +
           58  +CASE(0)
           59  + long long n = 6LL;
           60  + string _ = "John";
           61  +END
           62  +CASE(1)
           63  + long long n = 2LL;
           64  + string _ = "Brus";
           65  +END
           66  +CASE(2)
           67  + long long n = 747LL;
           68  + string _ = "Brus";
           69  +END
           70  +CASE(3)
           71  + long long n = 128LL;
           72  + string _ = "Brus";
           73  +END
           74  +CASE(4)
           75  + long long n = 288230376151711744LL;
           76  + string _ = "John";
           77  +END
           78  +CASE(5)
           79  + long long n = 1LL;
           80  + string _ = "Brus";
           81  +END
           82  +
           83  +}
           84  +// END CUT HERE

Added SRM/575-U/1B.cpp version [90d250afa9bcb948]

            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  +template<typename T>
           23  +vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v)
           24  +{
           25  + int N = a.size();
           26  + vector<T> u(N);
           27  + for(int i=0; i<N; ++i)
           28  + for(int j=0; j<N; ++j)
           29  +  u[i] += a[i][j]*v[j];
           30  + return u;
           31  +}
           32  +
           33  +template<typename T>
           34  +vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b)
           35  +{
           36  + int N = a.size();
           37  + vector< vector<T> > c(N, vector<T>(N));
           38  + for(int i=0; i<N; ++i)
           39  + for(int j=0; j<N; ++j)
           40  + for(int k=0; k<N; ++k)
           41  +  c[i][j] += a[i][k]*b[k][j];
           42  + return c;
           43  +}
           44  +
           45  +template<typename T>
           46  +vector<T> MATPOWMUL(vector< vector<T> > a, LL e, vector<T> v)
           47  +{
           48  + for(; e; e>>=1, a=MATMUL(a,a))
           49  +  if(e&1)
           50  +   v = MATMUL(a, v);
           51  + return v;
           52  +}
           53  +
           54  +class TheSwapsDivOne { public:
           55  + double find(vector <string> sequence, int k)
           56  + {
           57  +  const string S = accumulate(sequence.begin(), sequence.end(), string());
           58  +  const int N = S.size();
           59  +
           60  +  // pos[p] = prob that position p is chosen.
           61  +  vector<double> pos(N);
           62  +  const double tot_range = (1+N)*N/2;
           63  +  for(int p=0; p<N; ++p)
           64  +   pos[p] = (p+1)*(N-p) / tot_range;
           65  +  double totpos = accumulate(pos.begin(), pos.end(), 0.0);
           66  +
           67  +  double e = 0.0;
           68  +
           69  +  double pStay = calc_stay(N, k);
           70  +  cerr<<pStay<<endl;
           71  +  for(int p=0; p<N; ++p)
           72  +   e += (S[p]-'0') * (pStay*pos[p] + (1-pStay)*(totpos-pos[p])/(N-1));
           73  +  return e;
           74  + }
           75  +
           76  + double calc_stay(int N, int k)
           77  + {
           78  +  vector<double> v(2);
           79  +  v[0]=1, v[1]=0;
           80  +
           81  +  vector<vector<double> > m(2, vector<double>(2));
           82  +  double tot = N*(N-1)/2;
           83  +  m[0][0] = 1 - (N-1)/tot;
           84  +  m[0][1] = 1 - m[0][0];
           85  +  m[1][0] = 1 / tot;
           86  +  m[1][1] = 1 - m[1][0];
           87  +
           88  +  v = MATPOWMUL(m, k, v);
           89  +  return v[0];
           90  + }
           91  +};
           92  +
           93  +// BEGIN CUT HERE
           94  +#include <ctime>
           95  +double start_time; string timer()
           96  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           97  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           98  + { os << "{ ";
           99  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          100  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          101  +void verify_case(const double& Expected, const double& Received) {
          102  + bool ok = (abs(Expected - Received) < 1e-9);
          103  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          104  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          105  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          106  +#define END  verify_case(_, TheSwapsDivOne().find(sequence, k));}
          107  +int main(){
          108  +
          109  +CASE(0)
          110  + string sequence_[] = {"4", "77"};
          111  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          112  + int k = 1;
          113  + double _ = 10.0;
          114  +END
          115  +CASE(1)
          116  + string sequence_[] = {"4", "77"};
          117  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          118  + int k = 47;
          119  + double _ = 10.0;
          120  +END
          121  +CASE(2)
          122  + string sequence_[] = {"1", "1", "1", "1", "1", "1", "1"};
          123  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          124  + int k = 1000000;
          125  + double _ = 3.0;
          126  +END
          127  +CASE(3)
          128  + string sequence_[] = {"572685085149095989026478064633266980348504469", "19720257361", "9", "69"};
          129  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          130  + int k = 7;
          131  + double _ = 98.3238536775161;
          132  +END
          133  +CASE(4)
          134  + string sequence_[] = {"99119031434359106923816542810422135284590023481","18592326554385368171814861100277565528949239971","40347349899810715843953168648000263567310239924","38545780837311608418115423439501497402166989198","17285424781630234102349525011866340121513596937","99906102414517713148119423844384448210489647741","35143608617481431646437962753059300256206057014","32908347198481001587230423329525311296062283449","30955119911124654515507927745137969614038628659","05701821365741853514177287867868710603678841591","02951150544773501047638874470324652244274992240","66282387551352683966197052118658947485438694285","20252536028765020128833989964714452226508085010","80811331214834847334896900780427326512035360569","64027316291431464504713820313500109516764149897","48129573886929653773255932612216530466998301529","61692290484824339963810865408046132323155270926","20734322892232348414644895848499866768508454499","73977753818895603473393877456222096050605590631","75488083687667238723185124957724344916122502718","49308072322388038375901976579828643039912008068","49852892852425127382418689330961253679008410178","83755665062925303754162008026780205838121715045","71099919823637402309900038552838815087602284423","31494518631250555726432280524959027009811573208","94732518702631054441238939970137000403860659619","10438030120829399294297675572336596166498575107","95527243526745917048414629189698324008548561395","15132318439173982784310911106626381351036355555","05188145876757583124059940284920599124018514160","27896629348785393154614917085869574420611784052","88948023776542624752651009036945985038145092379","77491411686241001644232460531296311373251479662","70651631378830281367796703432742410612411377119","81356659097328268106177924003156451351223361290","57824086176360950782192786893941656905433490072","46805400665194951531366038022986309479083989964","66221676730070159290160046394594552489155178118","43413084875075661605155886091832959565937975007","16576558699206159813455421805523400639947166856","86296226099954462872106169149247652374572253816","20491754476476154924134977170527318962516951048","48015624509000271533893818471120349856582210629","39124424833845839884810813169030467125026545695","06179865905679773500000446518009139186221751475","50299762028484386451798250206098404849305241667","17612303343616139783490972262772438676524824068"};
          135  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          136  + int k = 1000000;
          137  + double _ = -1.0;
          138  +END
          139  +CASE(5)
          140  + string sequence_[] = {"71976811258237929702845263495922601783919868641","02251802204323958045597357456923113495221557803","90095020220279834521539403624903937967725913407","50053460399206979462458264772306292666423647685","02572846359464506709668041986008820985078749456","63651195290257557859053784453335417054877378801","88071504446176013413511927775188191764379674623","29974854837574431313734534729345259190024602997","55014957157257843589686675744902604078720333508","01131988958096366504666993633754134352692269267","51752858242869007758022337290690356607077821800","21095486538572029728876557551700273163478568908","26768584712609422632927787476248052685871245841","30476162031128267909969986318200112332997060127","67147231545693336082449853378272619777539526890","77325751151483739979126189680785999306688546541","60696196844453533885255920392566069304416588788","40448439503868890128193004467326572316344483756","38794956784623535641434020544271114018904283039","04259378746619199033735315818389500832702792548","14749921924200367925539596250117026415125437361","27571950348568199963970732499050942346365404137","20426040040465751262062508541139520659336559386","55174667536504554080965535926587381147358222766","91929788953883088854601418426423178327841570217","59380787526604353267171849869050674394208302221","26674907125183934287726716511384835000891155717","62239098887645197764145691025786798119751608655","92218110071216479433249224067456563435001106633","54941333895778833504791076934725843041038752979","44933730489344462698957437896769769665685685859","71451690730171207333637871178287883931766109666","01233816901291564380352253472638207947970645289","12022772227294854058522895631361139206099215743","14277758640213194050151726109721453213417484968","66733582405484779688190261796445525047628795445","28448651340492606982737723760081282553763549534","21540709018694807057292761057907753900925612265","07308657638866103434359099058610811770204658380","32455397123941974928264127618703584263392274381","55395352504201503474443238244337603595878619533","00381935524390094046906802274067171473367145593","86620399556019143023852411146726967997538868505","30161314840498627367845419554474800263207588594","67504258995889458279205655740089172159291177169","38484488894772590350380196849005813762369148153","90833154310182723669587328317813416374891018446"};
          141  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          142  + int k = 1000000;
          143  + double _ = -1.0;
          144  +END
          145  +CASE(0)
          146  + string sequence_[] = {"1", "2"};
          147  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          148  + int k = 1;
          149  + double _ = 2.0;
          150  +END
          151  +CASE(0)
          152  + string sequence_[] = {"1", "2"};
          153  +   vector <string> sequence(sequence_, sequence_+sizeof(sequence_)/sizeof(*sequence_));
          154  + int k = 2;
          155  + double _ = 2.0;
          156  +END
          157  +
          158  +}
          159  +// END CUT HERE