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

Added SRM/TCO13-2B-U/1A.cpp version [2b5324448e8be251]

            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  +int gcd(int a, int b)
           23  +{
           24  + while(a)
           25  +  swap(a, b%=a);
           26  + return b;
           27  +}
           28  +
           29  +class FruitTrees { public:
           30  + int maxDist(int apple, int kiwi, int grape)
           31  + {
           32  +  int best = 0;
           33  +  for(int k0=0; k0<kiwi; ++k0) {
           34  +   int ak = calc(apple, 0, kiwi, k0);
           35  +   for(int g0=0; g0<grape; ++g0)
           36  +    best = max(best, min(ak, min(calc(apple, 0, grape, g0), calc(kiwi, k0, grape, g0))));
           37  +  }
           38  +  return best;
           39  + }
           40  +
           41  + int calc(int a, int a0, int b, int b0)
           42  + {
           43  +  //int x = abs(b0-a0);
           44  +  int x = b0-a0;
           45  +  int g = gcd(a, b);
           46  +  return min(x%g, g-x%g);
           47  + }
           48  +};
           49  +
           50  +// BEGIN CUT HERE
           51  +#include <ctime>
           52  +double start_time; string timer()
           53  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           54  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           55  + { os << "{ ";
           56  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           57  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           58  +void verify_case(const int& Expected, const int& Received) {
           59  + bool ok = (Expected == Received);
           60  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           61  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           62  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           63  +#define END  verify_case(_, FruitTrees().maxDist(apple, kiwi, grape));}
           64  +int main(){
           65  +
           66  +CASE(0)
           67  + int apple = 1;
           68  + int kiwi = 5;
           69  + int grape = 8;
           70  + int _ = 0;
           71  +END
           72  +CASE(1)
           73  + int apple = 3;
           74  + int kiwi = 3;
           75  + int grape = 6;
           76  + int _ = 1;
           77  +END
           78  +CASE(2)
           79  + int apple = 40;
           80  + int kiwi = 30;
           81  + int grape = 20;
           82  + int _ = 5;
           83  +END
           84  +CASE(3)
           85  + int apple = 899;
           86  + int kiwi = 1073;
           87  + int grape = 1147;
           88  + int _ = 14;
           89  +END
           90  +CASE(4)
           91  + int apple = 2000;
           92  + int kiwi = 2000;
           93  + int grape = 2000;
           94  + int _ = 666;
           95  +END
           96  +CASE(5)
           97  + int apple = 100;
           98  + int kiwi = 36;
           99  + int grape = 225;
          100  + int _ = -1;
          101  +END
          102  +/*
          103  +CASE(6)
          104  + int apple = ;
          105  + int kiwi = ;
          106  + int grape = ;
          107  + int _ = ;
          108  +END
          109  +*/
          110  +}
          111  +// END CUT HERE

Added SRM/TCO13-2B-U/1B-U.cpp version [357463870fd0d422]

            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 ScotlandYard { public:
           23  + int maxMoves(vector <string> taxi, vector <string> bus, vector <string> metro)
           24  + {
           25  +  const int N = taxi.size();
           26  +  vector<LL> n[3];
           27  +  for(int i=0; i<N; ++i) {
           28  +   LL n0=0, n1=0, n2=0;
           29  +   for(int k=0; k<N; ++k) {
           30  +    if(taxi[i][k]=='Y')
           31  +     n0 |= 1LL << k;
           32  +    if(bus[i][k]=='Y')
           33  +     n1 |= 1LL << k;
           34  +    if(metro[i][k]=='Y')
           35  +     n2 |= 1LL << k;
           36  +   }
           37  +   n[0].push_back(n0);
           38  +   n[1].push_back(n1);
           39  +   n[2].push_back(n2);
           40  +  }
           41  +
           42  +  set<LL> vis;
           43  +  try {
           44  +   return rec((1LL<<N)-1, n, vis);
           45  +  } catch(...) {
           46  +   return -1;
           47  +  }
           48  + }
           49  +
           50  + int rec(LL cur, const vector<LL> n_tbl[3], set<LL>& vis)
           51  + {
           52  +  if((cur & (cur-1)) == 0)
           53  +   return 0;
           54  +  if(!vis.insert(cur).second)
           55  +   throw "infinite!";
           56  +
           57  +  LL next[] = {0,0,0};
           58  +  for(int i=0; (1LL<<i)<=cur; ++i)
           59  +   if(cur & (1LL<<i)) {
           60  +    next[0] |= n_tbl[0][i];
           61  +    next[1] |= n_tbl[1][i];
           62  +    next[2] |= n_tbl[2][i];
           63  +   }
           64  +  int r0 = next[0] ? rec(next[0], n_tbl, vis)+1 : 0;
           65  +  int r1 = next[1] ? rec(next[1], n_tbl, vis)+1 : 0;
           66  +  int r2 = next[2] ? rec(next[2], n_tbl, vis)+1 : 0;
           67  +  vis.erase(cur);
           68  +  return max(r0, max(r1, r2));
           69  + }
           70  +};
           71  +
           72  +// BEGIN CUT HERE
           73  +#include <ctime>
           74  +double start_time; string timer()
           75  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           76  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           77  + { os << "{ ";
           78  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           79  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           80  +void verify_case(const int& Expected, const int& Received) {
           81  + bool ok = (Expected == Received);
           82  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           83  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           84  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           85  +#define END  verify_case(_, ScotlandYard().maxMoves(taxi, bus, metro));}
           86  +int main(){
           87  +
           88  +CASE(0)
           89  + string taxi_[] = {"NYN",
           90  + "NNY",
           91  + "NNN"};
           92  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
           93  + string bus_[] = {"NNN",
           94  + "NNN",
           95  + "NNN"};
           96  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
           97  + string metro_[] = {"NNN",
           98  + "NNN",
           99  + "NNN"};
          100  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          101  + int _ = 2;
          102  +END
          103  +CASE(1)
          104  + string taxi_[] = {"NYY",
          105  + "NNN",
          106  + "NNN"};
          107  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          108  + string bus_[] = {"NNN",
          109  + "NNN",
          110  + "NNN"};
          111  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          112  + string metro_[] = {"NNN",
          113  + "NNN",
          114  + "NNN"};
          115  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          116  + int _ = 1;
          117  +END
          118  +CASE(2)
          119  + string taxi_[] = {"NYYY",
          120  + "YNYY",
          121  + "YYNY",
          122  + "YYYN"};
          123  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          124  + string bus_[] = {"NNNN",
          125  + "NNNN",
          126  + "NNNN",
          127  + "NNNN"};
          128  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          129  + string metro_[] = {"NNNN",
          130  + "NNNN",
          131  + "NNNN",
          132  + "NNNN"};
          133  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          134  + int _ = -1;
          135  +END
          136  +CASE(3)
          137  + string taxi_[] = {"NNY",
          138  + "NNY",
          139  + "NNN"};
          140  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          141  + string bus_[] = {"NYN",
          142  + "NNY",
          143  + "NNN"};
          144  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          145  + string metro_[] = {"NNN",
          146  + "NNN",
          147  + "YNN"};
          148  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          149  + int _ = 2;
          150  +END
          151  +CASE(4)
          152  + string taxi_[] = {"NNN",
          153  + "YNY",
          154  + "NNN"};
          155  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          156  + string bus_[] = {"NNN",
          157  + "YNN",
          158  + "YNN"};
          159  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          160  + string metro_[] = {"NNN",
          161  + "NNN",
          162  + "YYN"};
          163  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          164  + int _ = -1;
          165  +END
          166  +CASE(5)
          167  + string taxi_[] = {"NNNNYNNNYY",
          168  + "NNYNNYYYYY",
          169  + "NNNNNNNNNN",
          170  + "YYNNYYNNNY",
          171  + "NNYNNNNNNN",
          172  + "YNYNYNNNYN",
          173  + "NNYNYNNNYN",
          174  + "NNNNNNYNNN",
          175  + "NNNNNNNNNN",
          176  + "NNNNNNYNNN"};
          177  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          178  + string bus_[] = {"NNYNNNYNNY",
          179  + "YNYNNYYNYY",
          180  + "NNNNNNNNNN",
          181  + "YNYNNYNYNY",
          182  + "NNYNNNNNYN",
          183  + "YNYNYNYNYN",
          184  + "NNYNNNNNNY",
          185  + "YNYNNNNNNN",
          186  + "NNNNNNNNNN",
          187  + "NNYNYNNNNN"};
          188  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          189  + string metro_[] = {"NNNNNNNYNN",
          190  + "YNYNNNNNYN",
          191  + "NNNNNNNNNN",
          192  + "NYNNYNNNYY",
          193  + "NNYNNNNNNN",
          194  + "YNYNNNNNYY",
          195  + "NNNNYNNNYN",
          196  + "NNYNNNYNNN",
          197  + "NNNNNNNNNY",
          198  + "NNYNYNNNNN"};
          199  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          200  + int _ = 21;
          201  +END
          202  +CASE(6)
          203  + string taxi_[] = {
          204  +"NYYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          205  +"YNYNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          206  +"NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN",
          207  +"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
          208  +"NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
          209  +"NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
          210  +"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
          211  +"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
          212  +"NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
          213  +"NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
          214  +"NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
          215  +"NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN",
          216  +"NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
          217  +"NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN",
          218  +"NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
          219  +"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
          220  +"NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
          221  +"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
          222  +"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN",
          223  +"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN",
          224  +"NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN",
          225  +"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN",
          226  +"NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN",
          227  +"NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
          228  +"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN",
          229  +"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
          230  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
          231  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN",
          232  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
          233  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          234  +};
          235  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          236  + string bus_[] = {
          237  +"NYNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          238  +"YNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          239  +"NNNYNNNNNNNNNNNNNNNNNNNNNNNNNN",
          240  +"NNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
          241  +"NNNNNYNNNNNNNNNNNNNNNNNNNNNNNN",
          242  +"NNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
          243  +"NNNNNNNYNNNNNNNNNNNNNNNNNNNNNN",
          244  +"NNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
          245  +"NNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
          246  +"NNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
          247  +"NNNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
          248  +"NNNNNNNNNNNNYNNNNNNNNNNNNNNNNN",
          249  +"NNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
          250  +"NNNNNNNNNNNNNNYNNNNNNNNNNNNNNN",
          251  +"NNNNNNNNNNNNNNNYNNNNNNNNNNNNNN",
          252  +"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
          253  +"NNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
          254  +"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
          255  +"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNN",
          256  +"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNN",
          257  +"NNNNNNNNNNNNNNNNNNNNNYNNNNNNNN",
          258  +"NNNNNNNNNNNNNNNNNNNNNNYNNNNNNN",
          259  +"NNNNNNNNNNNNNNNNNNNNNNNYNNNNNN",
          260  +"NNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
          261  +"NNNNNNNNNNNNNNNNNNNNNNNNNYNNNN",
          262  +"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
          263  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
          264  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNYN",
          265  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
          266  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          267  +};
          268  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          269  + string metro_[] = {
          270  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          271  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          272  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          273  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          274  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          275  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          276  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          277  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          278  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          279  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          280  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          281  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          282  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          283  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          284  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          285  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          286  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          287  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          288  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          289  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          290  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          291  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          292  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          293  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          294  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          295  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          296  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          297  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          298  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          299  +"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          300  +};
          301  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          302  + int _ = -1;
          303  +END
          304  +/*
          305  +CASE(7)
          306  + string taxi_[] = ;
          307  +   vector <string> taxi(taxi_, taxi_+sizeof(taxi_)/sizeof(*taxi_));
          308  + string bus_[] = ;
          309  +   vector <string> bus(bus_, bus_+sizeof(bus_)/sizeof(*bus_));
          310  + string metro_[] = ;
          311  +   vector <string> metro(metro_, metro_+sizeof(metro_)/sizeof(*metro_));
          312  + int _ = ;
          313  +END
          314  +*/
          315  +}
          316  +// END CUT HERE