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

Added SRM/633-U/1A.cpp version [7bd18a955be38dea]

            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 PeriodicJumping { public:
           23  + int minimalTime(int x, vector <int> jumpLengths)
           24  + {
           25  +  if(x==0)
           26  +   return 0;
           27  +  if(x<0)
           28  +   x=-x;
           29  +
           30  +  vector<int> js;
           31  +  js.insert(js.end(), jumpLengths.begin(), jumpLengths.end());
           32  +  js.insert(js.end(), jumpLengths.begin(), jumpLengths.end());
           33  +  const LL all_sum = accumulate(js.begin(), js.end(), 0LL);
           34  +
           35  +  LL best = 1LL<<62;
           36  +  for(int i=0; i<js.size(); ++i)
           37  +  {
           38  +   LL sum = accumulate(js.begin(), js.begin()+i+1, 0LL);
           39  +   LL M = *max_element(js.begin(), js.begin()+i+1);
           40  +   LL min_repr = max(0LL, M*2-sum);
           41  +
           42  +   // [min_repr, sum] in the first round.
           43  +   if(min_repr<=x && x<=sum)
           44  +    best = min<LL>(best, i+1);
           45  +   // [0, sum+K*all_sum] in the Kth round.
           46  +   LL K = max(1LL, (x-sum+all_sum-1)/all_sum);
           47  +   best = min<LL>(best, K*js.size()+i+1);
           48  +  }
           49  +  return int(best);
           50  + }
           51  +};
           52  +
           53  +// BEGIN CUT HERE
           54  +#include <ctime>
           55  +double start_time; string timer()
           56  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           57  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           58  + { os << "{ ";
           59  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           60  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           61  +void verify_case(const int& Expected, const int& Received) {
           62  + bool ok = (Expected == Received);
           63  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           64  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           65  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           66  +#define END  verify_case(_, PeriodicJumping().minimalTime(x, jumpLengths));}
           67  +int main(){
           68  +
           69  +CASE(0)
           70  + int x = 15;
           71  + int jumpLengths_[] = {1,2,3,4,5,6,7,8,9,10};
           72  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
           73  + int _ = 5;
           74  +END
           75  +CASE(1)
           76  + int x = 5;
           77  + int jumpLengths_[] = {5};
           78  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
           79  + int _ = 1;
           80  +END
           81  +CASE(2)
           82  + int x = 1;
           83  + int jumpLengths_[] = {10};
           84  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
           85  + int _ = 2;
           86  +END
           87  +CASE(3)
           88  + int x = -10;
           89  + int jumpLengths_[] = {2,3,4,500,6,7,8};
           90  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
           91  + int _ = 11;
           92  +END
           93  +CASE(4)
           94  + int x = -1000000000;
           95  + int jumpLengths_[] = {1};
           96  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
           97  + int _ = 1000000000;
           98  +END
           99  +CASE(5)
          100  + int x = 0;
          101  + int jumpLengths_[] = {19911120};
          102  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
          103  + int _ = 0;
          104  +END
          105  +/*
          106  +CASE(6)
          107  + int x = ;
          108  + int jumpLengths_[] = ;
          109  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
          110  + int _ = ;
          111  +END
          112  +CASE(7)
          113  + int x = ;
          114  + int jumpLengths_[] = ;
          115  +   vector <int> jumpLengths(jumpLengths_, jumpLengths_+sizeof(jumpLengths_)/sizeof(*jumpLengths_));
          116  + int _ = ;
          117  +END
          118  +*/
          119  +}
          120  +// END CUT HERE

Added SRM/633-U/1B-U.cpp version [cfb3baca4827166b]

            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 DoubleTree { public:
           23  + int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> score)
           24  + {
           25  +  const int N = a.size() + 1;
           26  +
           27  +  vector<vector<LL>> dep(N, vector<LL>(N));
           28  +  add_dep(a, b, dep);
           29  +  add_dep(c, d, dep);
           30  +  closure(N, dep);
           31  +
           32  +  int best = 0;
           33  +  for(int root=0; root<N; ++root)
           34  +  {
           35  +   int base_score = score[root];
           36  +
           37  +   set<LL> cs;
           38  +   for(int v=0; v<N; ++v) if(v!=root)
           39  +    cs.insert(dep[min(root,v)][max(root,v)] &~ (1LL<<root));
           40  +
           41  +   LL theSet = 0;
           42  +   for(LL c: cs) {
           43  +    int ss = 0;
           44  +    for(int i=0; (1LL<<i)<=c; ++i)
           45  +     if((1LL<<i)&c)
           46  +      ss += score[i];
           47  +    if(ss>0)
           48  +     theSet |= c;
           49  +   }
           50  +
           51  +   int ss = 0;
           52  +   for(int i=0; (1LL<<i)<=theSet; ++i)
           53  +    if((1LL<<i)&theSet)
           54  +     ss += score[i];
           55  +   best = max(best, base_score+ss);
           56  +  }
           57  +  return best;
           58  + }
           59  +
           60  + void closure(int N, vector<vector<LL>>& dep)
           61  + {
           62  +  for(bool upd=true; upd; ) {
           63  +   upd = false;
           64  +   for(int a=0; a<N; ++a)
           65  +   for(int b=a; b<N; ++b)
           66  +   for(int c=0; c<N; ++c) if((1LL<<c)&dep[a][b]) {
           67  +    LL neo = dep[a][b] | dep[min(a,c)][max(a,c)] | dep[min(b,c)][max(b,c)];
           68  +    if(neo != dep[a][b]) {
           69  +     upd = true;
           70  +     dep[a][b] = neo;
           71  +    }
           72  +   }
           73  +  }
           74  + }
           75  +
           76  + void add_dep(const vector<int>& a, const vector<int>& b, vector<vector<LL>>& dep)
           77  + {
           78  +  int N = a.size() + 1;
           79  +  vector<vector<int>> G(N);
           80  +  for(int i=0; i<N-1; ++i) {
           81  +   G[a[i]].push_back(b[i]);
           82  +   G[b[i]].push_back(a[i]);
           83  +  }
           84  +
           85  +  for(int root=0; root<N; ++root) {
           86  +   vector<int> stk;
           87  +   function<void(int,int)> rec;
           88  +   rec = [&](int pre, int v) {
           89  +    stk.push_back(v);
           90  +    for(int mid: stk)
           91  +     dep[min(root,v)][max(root,v)] |= 1LL<<mid;
           92  +    for(int u: G[v]) if(u!=pre)
           93  +     rec(v, u);
           94  +    stk.pop_back();
           95  +   };
           96  +   rec(-1, root);
           97  +  }
           98  + }
           99  +};
          100  +
          101  +// BEGIN CUT HERE
          102  +#include <ctime>
          103  +double start_time; string timer()
          104  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          105  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          106  + { os << "{ ";
          107  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          108  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          109  +void verify_case(const int& Expected, const int& Received) {
          110  + bool ok = (Expected == Received);
          111  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          112  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          113  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          114  +#define END  verify_case(_, DoubleTree().maximalScore(a, b, c, d, score));}
          115  +int main(){
          116  +
          117  +CASE(0)
          118  + int a_[] = {0,0,1};
          119  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          120  + int b_[] = {1,3,2};
          121  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          122  + int c_[] = {0,0,3};
          123  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          124  + int d_[] = {1,3,2};
          125  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          126  + int score_[] = {1000,24,100,-200};
          127  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          128  + int _ = 1024;
          129  +END
          130  +CASE(1)
          131  + int a_[] = {0,0,1};
          132  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          133  + int b_[] = {1,3,2};
          134  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          135  + int c_[] = {0,0,3};
          136  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          137  + int d_[] = {1,3,2};
          138  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          139  + int score_[] = {1000,24,100,200};
          140  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          141  + int _ = 1324;
          142  +END
          143  +CASE(2)
          144  + int a_[] = {0,0,1};
          145  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          146  + int b_[] = {1,3,2};
          147  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          148  + int c_[] = {0,0,3};
          149  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          150  + int d_[] = {1,3,2};
          151  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          152  + int score_[] = {-1000,-24,-100,-200};
          153  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          154  + int _ = 0;
          155  +END
          156  +CASE(3)
          157  + int a_[] = {0,0,1};
          158  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          159  + int b_[] = {1,3,2};
          160  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          161  + int c_[] = {0,0,3};
          162  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          163  + int d_[] = {1,3,2};
          164  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          165  + int score_[] = {-1000,24,100,200};
          166  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          167  + int _ = 200;
          168  +END
          169  +CASE(4)
          170  + int a_[] = {0,0,1,1,2,2};
          171  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          172  + int b_[] = {1,2,3,4,5,6};
          173  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          174  + int c_[] = {0,0,1,1,2,2};
          175  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          176  + int d_[] = {1,2,3,4,5,6};
          177  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          178  + int score_[] = {-3,2,2,-1,2,2,-1};
          179  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          180  + int _ = 5;
          181  +END
          182  +CASE(5)
          183  + int a_[] = {0,0,1,1,2,2};
          184  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          185  + int b_[] = {1,2,3,4,5,6};
          186  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          187  + int c_[] = {0,0,0,0,0,0};
          188  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          189  + int d_[] = {1,2,3,4,5,6};
          190  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          191  + int score_[] = {-3,2,2,-1,2,2,-1};
          192  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          193  + int _ = 5;
          194  +END
          195  +/*
          196  +CASE(6)
          197  + int a_[] = ;
          198  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          199  + int b_[] = ;
          200  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          201  + int c_[] = ;
          202  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          203  + int d_[] = ;
          204  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          205  + int score_[] = ;
          206  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          207  + int _ = ;
          208  +END
          209  +CASE(7)
          210  + int a_[] = ;
          211  +   vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_));
          212  + int b_[] = ;
          213  +   vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_));
          214  + int c_[] = ;
          215  +   vector <int> c(c_, c_+sizeof(c_)/sizeof(*c_));
          216  + int d_[] = ;
          217  +   vector <int> d(d_, d_+sizeof(d_)/sizeof(*d_));
          218  + int score_[] = ;
          219  +   vector <int> score(score_, score_+sizeof(score_)/sizeof(*score_));
          220  + int _ = ;
          221  +END
          222  +*/
          223  +}
          224  +// END CUT HERE