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

Added SRM/628-U/1A.cpp version [e7ca75c1d92e9797]

            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 DivisorsPower { public:
           23  + long long findArgument(long long n)
           24  + {
           25  +  LL cand = 1LL<<62;
           26  +  for(int p=2; p<=63; ++p) {
           27  +   LL xc = LL(pow(double(n), 1.0/p));
           28  +   for(LL x=max(2LL,xc-100); x<=min(xc+100,n); ++x)
           29  +    if(ok(x,n))
           30  +     cand = min(cand, x);
           31  +  }
           32  +  return (cand==(1LL<<62) ? -1 : cand);
           33  + }
           34  +
           35  + int d(LL x)
           36  + {
           37  +  int cnt = 1;
           38  +  for(int p=2; p*p<=x; ++p)
           39  +   if(x%p==0) {
           40  +    int k = 0;
           41  +    while(x%p==0) x/=p, ++k;
           42  +    cnt *= 1+k;
           43  +   }
           44  +  if(x>1)
           45  +   cnt *= 2;
           46  +  return cnt;
           47  + }
           48  +
           49  + int ilog(LL x, LL n)
           50  + {
           51  +  int cnt = 0;
           52  +  while(n%x==0)
           53  +   n/=x, ++cnt;
           54  +  return n>1 ? -1 : cnt;
           55  + }
           56  +
           57  +
           58  + bool ok(LL x, LL n)
           59  + {
           60  +  return ilog(x, n) == d(x);
           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 long long& Expected, const 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(_, DivisorsPower().findArgument(n));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + long long n = 4LL;
           82  + long long _ = 2LL;
           83  +END
           84  +CASE(1)
           85  + long long n = 10LL;
           86  + long long _ = -1LL;
           87  +END
           88  +CASE(2)
           89  + long long n = 64LL;
           90  + long long _ = 4LL;
           91  +END
           92  +CASE(3)
           93  + long long n = 10000LL;
           94  + long long _ = 10LL;
           95  +END
           96  +CASE(4)
           97  + long long n = 2498388559757689LL;
           98  + long long _ = 49983883LL;
           99  +END
          100  +/*
          101  +CASE(5)
          102  + long long n = LL;
          103  + long long _ = LL;
          104  +END
          105  +CASE(6)
          106  + long long n = LL;
          107  + long long _ = LL;
          108  +END
          109  +*/
          110  +}
          111  +// END CUT HERE

Added SRM/628-U/1B.cpp version [832763487ee7bc8f]

            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  +enum Type {X, SUM, MAX};
           23  +struct Tree {
           24  + Type type;
           25  + Tree* left;
           26  + Tree* right;
           27  + int size;
           28  + ~Tree() { delete left; delete right; }
           29  +};
           30  +
           31  +class CircuitsConstruction { public:
           32  + int maximizeResistance(string circuit, vector <int> conductors)
           33  + {
           34  +  sort(conductors.rbegin(), conductors.rend());
           35  +  const char* p = circuit.c_str();
           36  +  Tree* t = parse(p);
           37  +  int ans = solve(t, conductors);
           38  +  delete t;
           39  +  return ans;
           40  + }
           41  +
           42  + Tree* parse(const char*& p)
           43  + {
           44  +  char tc = *p++;
           45  +  Tree* t = new Tree;
           46  +  t->type = (tc=='X' ? X : tc=='A' ? SUM : MAX);
           47  +  if(tc=='X') {
           48  +   t->left = t->right = 0;
           49  +   t->size = 1;
           50  +  } else {
           51  +   t->left = parse(p);
           52  +   t->right = parse(p);
           53  +   t->size = t->left->size + t->right->size;
           54  +  }
           55  +  return t;
           56  + }
           57  +
           58  + int plusdepth(Tree* t)
           59  + {
           60  +  switch(t->type)
           61  +  {
           62  +  case X:
           63  +   return 0;
           64  +  case SUM:
           65  +   return plusdepth(t->left) + plusdepth(t->right) + 1;
           66  +  case MAX:
           67  +   return max(plusdepth(t->left), plusdepth(t->right));
           68  +  }
           69  + }
           70  +
           71  + int solve(Tree* t, const vector<int>& c)
           72  + {
           73  +  int n = plusdepth(t)+1;
           74  +  return accumulate(c.begin(), c.begin()+n, 0);
           75  + }
           76  +};
           77  +
           78  +// BEGIN CUT HERE
           79  +#include <ctime>
           80  +double start_time; string timer()
           81  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           82  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           83  + { os << "{ ";
           84  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           85  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           86  +void verify_case(const int& Expected, const int& Received) {
           87  + bool ok = (Expected == Received);
           88  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           89  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           90  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           91  +#define END  verify_case(_, CircuitsConstruction().maximizeResistance(circuit, conductors));}
           92  +int main(){
           93  +
           94  +CASE(0)
           95  + string circuit = "BXBXX";
           96  + int conductors_[] = {8, 2, 3};
           97  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
           98  + int _ = 8;
           99  +END
          100  +CASE(1)
          101  + string circuit = "AAXXAXAXX";
          102  + int conductors_[] = {1, 1, 2, 8, 10};
          103  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
          104  + int _ = 22;
          105  +END
          106  +CASE(2)
          107  + string circuit = "AXBXX";
          108  + int conductors_[] = {8, 2, 3};
          109  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
          110  + int _ = 11;
          111  +END
          112  +CASE(3)
          113  + string circuit = "BAAXBXXBXAXXBBAXXBXXAAXXX";
          114  + int conductors_[] = {17, 7, 21, 102, 56, 72, 88, 15, 9, 192, 16, 8, 30};
          115  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
          116  + int _ = 454;
          117  +END
          118  +/*
          119  +CASE(4)
          120  + string circuit = ;
          121  + int conductors_[] = ;
          122  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
          123  + int _ = ;
          124  +END
          125  +CASE(5)
          126  + string circuit = ;
          127  + int conductors_[] = ;
          128  +   vector <int> conductors(conductors_, conductors_+sizeof(conductors_)/sizeof(*conductors_));
          129  + int _ = ;
          130  +END
          131  +*/
          132  +}
          133  +// END CUT HERE

Added SRM/628-U/1C-U.cpp version [5d7fde43f099f38d]

            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 DoraemonPuzzleGame { public:
           23  + double solve(vector <int> X, vector <int> Y, int m)
           24  + {
           25  +  int N = X.size(), M = m;
           26  +  vector<tuple<double,double,double>> P;
           27  +  for(int i=0; i<N; ++i)
           28  +   P.emplace_back(
           29  +    (1000-X[i]-Y[i])*0.001,
           30  +    X[i]*0.001,
           31  +    Y[i]*0.001
           32  +   );
           33  +  sort(P.begin(), P.end(), [&](const tuple<double,double,double>& lhs, const tuple<double,double,double>& rhs){
           34  +   if(get<2>(lhs) != get<2>(rhs)) return get<2>(lhs) > get<2>(rhs);
           35  +   if(get<1>(lhs) != get<1>(rhs)) return get<1>(lhs) > get<1>(rhs);
           36  +   return get<0>(lhs) > get<0>(rhs);
           37  +  });
           38  +  return solve(M-N, P);
           39  + }
           40  +
           41  + double solve(int Extra, const vector<tuple<double,double,double>>& P)
           42  + {
           43  +  double eee = 0.0;
           44  +  for(int eff=0; eff<=P.size(); ++eff)
           45  +  {
           46  +   double e_clear = 0.0;
           47  +   vector<double> adv(1, 1.0);  // adv[0] = 1.0;
           48  +   for(int i=0; i<P.size(); ++i) {
           49  +    double p1 = get<1>(P[i]);
           50  +    double p2 = get<2>(P[i]);
           51  +    if(i<eff) {
           52  +     e_clear += 1/p2;
           53  +    } else {
           54  +     double p = p1 + p2;
           55  +     e_clear += 1/p;
           56  +
           57  +     vector<double> a2(adv.size()+1);
           58  +     for(int i=0; i<adv.size(); ++i) {
           59  +      a2[i] += adv[i] * p1/p;
           60  +      a2[i+1] += adv[i] * p2/p;
           61  +     }
           62  +     adv = a2;
           63  +    }
           64  +   }
           65  +
           66  +   if(Extra <= eff) {
           67  +    best = min(best, e_clear);
           68  +   } else {
           69  +    best = min(best,
           70  +   }
           71  +  }
           72  +  return eee;
           73  + }
           74  +};
           75  +
           76  +// BEGIN CUT HERE
           77  +#include <ctime>
           78  +double start_time; string timer()
           79  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           80  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           81  + { os << "{ ";
           82  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           83  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           84  +void verify_case(const double& Expected, const double& Received) {
           85  + bool ok = (abs(Expected - Received) < 1e-9);
           86  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           87  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           88  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           89  +#define END  verify_case(_, DoraemonPuzzleGame().solve(X, Y, m));}
           90  +int main(){
           91  +
           92  +CASE(0)
           93  + int X_[] = {800};
           94  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
           95  + int Y_[] = {200};
           96  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
           97  + int m = 2;
           98  + double _ = 5.0;
           99  +END
          100  +CASE(1)
          101  + int X_[] = {1,999,999};
          102  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          103  + int Y_[] = {999,1,1};
          104  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          105  + int m = 3;
          106  + double _ = 3.0;
          107  +END
          108  +CASE(2)
          109  + int X_[] = {500,500};
          110  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          111  + int Y_[] = {500,500};
          112  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          113  + int m = 3;
          114  + double _ = 2.5;
          115  +END
          116  +CASE(3)
          117  + int X_[] = {250,250,250,250};
          118  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          119  + int Y_[] = {250,250,250,250};
          120  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          121  + int m = 5;
          122  + double _ = 8.25;
          123  +END
          124  +CASE(4)
          125  + int X_[] = {250,500,250};
          126  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          127  + int Y_[] = {500,250,500};
          128  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          129  + int m = 5;
          130  + double _ = 4.962962962962963;
          131  +END
          132  +CASE(5)
          133  + int X_[] = {600,900,800,500,900,200,400,100,800,300,900,300,800,700,800,600,800,900,400,100,100,700,600,100,500,
          134  +800,700,600,900,600,300,100,300,100,700,500,900,200,800,400,300,700,300,400,700,300,400,800,300,200};
          135  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          136  + int Y_[] = {400,100,200,500,100,800,600,900,200,700,100,700,200,300,200,400,200,100,600,900,900,300,400,900,500,
          137  +200,300,400,100,400,700,900,700,900,300,500,100,800,200,600,700,300,700,600,300,700,600,200,700,800};
          138  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          139  + int m = 95;
          140  + double _ = 119.33578280666175;
          141  +END
          142  +/*
          143  +CASE(6)
          144  + int X_[] = ;
          145  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          146  + int Y_[] = ;
          147  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          148  + int m = ;
          149  + double _ = ;
          150  +END
          151  +CASE(7)
          152  + int X_[] = ;
          153  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          154  + int Y_[] = ;
          155  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          156  + int m = ;
          157  + double _ = ;
          158  +END
          159  +*/
          160  +}
          161  +// END CUT HERE