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

Added SRM/599-U/1A.cpp version [acca555346b2264d]

            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 BigFatInteger { public:
           23  + int minOperations(int A, int B)
           24  + {
           25  +  vector<int> s;
           26  +  for(int p=2; p*p<=A; ++p)
           27  +  {
           28  +   int c = 0;
           29  +   while(A%p==0) A/=p, ++c;
           30  +   if(c) s.push_back(c*B);
           31  +  }
           32  +  if(A>1)
           33  +   s.push_back(1*B);
           34  +
           35  +  int cnt = s.size();
           36  +  vector<int> cur(s.size(), 1);
           37  +  while(cur != s)
           38  +  {
           39  +   for(int i=0; i<s.size(); ++i)
           40  +    cur[i] = min(cur[i]*2, s[i]);
           41  +   ++cnt;
           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 int& Expected, const int& 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(_, BigFatInteger().minOperations(A, B));}
           61  +int main(){
           62  +
           63  +CASE(0)
           64  + int A = 6;
           65  + int B = 1;
           66  + int _ = 2;
           67  +END
           68  +CASE(1)
           69  + int A = 162;
           70  + int B = 1;
           71  + int _ = 4;
           72  +END
           73  +CASE(2)
           74  + int A = 999983;
           75  + int B = 9;
           76  + int _ = 5;
           77  +END
           78  +CASE(3)
           79  + int A = 360;
           80  + int B = 8;
           81  + int _ = 8;
           82  +END
           83  +CASE(4)
           84  + int A = 1000000;
           85  + int B = 1000000;
           86  + int _ = -1;
           87  +END
           88  +CASE(5)
           89  + int A = 2*3*5*7*11*13*17;
           90  + int B = 1000000;
           91  + int _ = -1;
           92  +END
           93  +
           94  +}
           95  +// END CUT HERE

Added SRM/599-U/1B.cpp version [18e652cfb8226cd8]

            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  +class FindPolygons { public:
           30  + double minimumPolygon(int L)
           31  + {
           32  +  if(L<=2)
           33  +   return -1;
           34  +  if(L%2==1) // euclid%2 == manhattan%2. tour is always even.
           35  +   return -1;
           36  +
           37  +  map<int, vector<pair<int,int>>> pyt;
           38  +  for(int k=1; k<=L; ++k) {
           39  +   auto& pk = pyt[k];
           40  +   pk.emplace_back(0, k);
           41  +   pk.emplace_back(k, 0);
           42  +   pk.emplace_back(0, -k);
           43  +   pk.emplace_back(-k, 0);
           44  +  }
           45  +  for(int m=1; m*m<=L/2; ++m)
           46  +   for(int n=1; n<m && m*m+n*n<=L/2; ++n)
           47  +    if(((m^n)&1) && gcd(m,n)==1) {
           48  +     int a = m*m-n*n, b = 2*m*n, c = m*m+n*n;
           49  +     for(int k=1; k*c<=L; ++k) {
           50  +      auto& pk = pyt[k*c];
           51  +      pk.emplace_back(k*a, k*b);
           52  +      pk.emplace_back(k*a, -k*b);
           53  +      pk.emplace_back(-k*a, k*b);
           54  +      pk.emplace_back(-k*a, -k*b);
           55  +      pk.emplace_back(k*b, k*a);
           56  +      pk.emplace_back(k*b, -k*a);
           57  +      pk.emplace_back(-k*b, k*a);
           58  +      pk.emplace_back(-k*b, -k*a);
           59  +     }
           60  +    }
           61  +
           62  +  // Triangle
           63  +  int best = L;
           64  +  for(int a=1; a*3<=L; ++a)
           65  +   for(int b=a; a+b*2<=L; ++b)
           66  +   {
           67  +    int c = L-a-b;
           68  +
           69  +    for(auto& av : pyt[a])
           70  +    {
           71  +     int ax=av.first;
           72  +     int ay=av.second;
           73  +     if(ax>=0 && ay>=0)
           74  +     for(auto& bv : pyt[b])
           75  +     {
           76  +      int bx=bv.first;
           77  +      int by=bv.second;
           78  +      int cx=-ax-bx;
           79  +      int cy=-ay-by;
           80  +      if(ax*by!=ay*bx && cx*cx+cy*cy == c*c) {
           81  +       best = min(best, c-a);
           82  +       break;
           83  +      }
           84  +     }
           85  +    }
           86  +   }
           87  +  if(best < L)
           88  +   return best;
           89  +  // Rectangle
           90  +  if(L%4==0)
           91  +   return 0;
           92  +  return 1;
           93  + }
           94  +};
           95  +
           96  +// BEGIN CUT HERE
           97  +#include <ctime>
           98  +double start_time; string timer()
           99  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          100  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          101  + { os << "{ ";
          102  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          103  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          104  +void verify_case(const double& Expected, const double& Received) {
          105  + bool ok = (abs(Expected - Received) < 1e-9);
          106  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          107  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          108  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          109  +#define END  verify_case(_, FindPolygons().minimumPolygon(L));}
          110  +int main(){
          111  +CASE(0)
          112  + int L = 4;
          113  + double _ = 0.0;
          114  +END
          115  +CASE(1)
          116  + int L = 5;
          117  + double _ = -1.0;
          118  +END
          119  +CASE(2)
          120  + int L = 12;
          121  + double _ = 2.0;
          122  +END
          123  +CASE(3)
          124  + int L = 4984;
          125  + double _ = 819.0;
          126  +END
          127  +CASE(4)
          128  + int L = 5000;
          129  + double _ = -999;
          130  +END
          131  +CASE(4)
          132  + int L = 20;
          133  + double _ = -999;
          134  +END
          135  +/*
          136  +CASE(5)
          137  + int L = ;
          138  + double _ = ;
          139  +END
          140  +*/
          141  +}
          142  +// END CUT HERE