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

Added SRM/TCO14-3B-U/1A.cpp version [0c0f6895050a398a]

            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  +LL C(LL n, LL k)
           23  +{
           24  + LL v = 1;
           25  + for(LL i=1; i<=k; ++i)
           26  +  v = v*(n-i+1)/i;
           27  + return v;
           28  +}
           29  +
           30  +class IntoTheMatrix { public:
           31  + int takePills(int turns, int N)
           32  + {
           33  +  for(int F=0 ;; ++F)
           34  +   if(best(F,turns)>=N)
           35  +    return F;
           36  + }
           37  +
           38  + map<pair<int,int>,LL> memo;
           39  + LL best(int F, int T)
           40  + {
           41  +  if(T==0)
           42  +   return 1;
           43  +
           44  +  pair<int,int> key(F,T);
           45  +  if(memo.count(key))
           46  +   return memo[key];
           47  +
           48  +  LL sum = 0;
           49  +  for(int f=0; f<=F; ++f)
           50  +   sum += best(f, T-1)*C(F,f);
           51  +  return memo[key] = sum;
           52  + }
           53  +};
           54  +
           55  +// BEGIN CUT HERE
           56  +#include <ctime>
           57  +double start_time; string timer()
           58  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           59  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           60  + { os << "{ ";
           61  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           62  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           63  +void verify_case(const int& Expected, const int& Received) {
           64  + bool ok = (Expected == Received);
           65  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           66  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           67  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           68  +#define END  verify_case(_, IntoTheMatrix().takePills(turns, N));}
           69  +int main(){
           70  +
           71  +CASE(0)
           72  + int turns = 1;
           73  + int N = 1;
           74  + int _ = 0;
           75  +END
           76  +CASE(1)
           77  + int turns = 2;
           78  + int N = 10;
           79  + int _ = 3;
           80  +END
           81  +CASE(2)
           82  + int turns = 2;
           83  + int N = 1000;
           84  + int _ = 7;
           85  +END
           86  +CASE(3)
           87  + int turns = 10;
           88  + int N = 2;
           89  + int _ = 1;
           90  +END
           91  +CASE(4)
           92  + int turns = 4;
           93  + int N = 50;
           94  + int _ = 3;
           95  +END
           96  +CASE(5)
           97  + int turns = 1;
           98  + int N = 1000000;
           99  + int _ = -1;
          100  +END
          101  +CASE(6)
          102  + int turns = 10;
          103  + int N = 1000000;
          104  + int _ = -1;
          105  +END
          106  +}
          107  +// END CUT HERE