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

Added SRM/502-U/1A.cpp version [2978fcbee76e9eaf]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class TheLotteryBothDivs { public:
           23  + double find(vector <string> goodSuffixes)
           24  + {
           25  +  sort(goodSuffixes.begin(), goodSuffixes.end());
           26  +  goodSuffixes.erase(unique(goodSuffixes.begin(), goodSuffixes.end()), goodSuffixes.end());
           27  +  double p = 0.0;
           28  +  for(int i=0; i<goodSuffixes.size(); ++i) {
           29  +   const string& me = goodSuffixes[i];
           30  +   bool use = true;
           31  +   for(int k=0; k<goodSuffixes.size(); ++k)
           32  +    if( is_proper_suffix(me, goodSuffixes[k]) )
           33  +     use = false;
           34  +   if( use )
           35  +    p += pow(0.1, (double)me.size());
           36  +  }
           37  +  return p;
           38  + }
           39  + bool is_proper_suffix(const string& me, const string& suf)
           40  + {
           41  +  if( me.size() <= suf.size() )
           42  +   return false;
           43  +  return me.substr(me.size()-suf.size()) == suf;
           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 double& Expected, const double& Received) {
           56  + bool ok = (abs(Expected - Received) < 1e-9);
           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(_, TheLotteryBothDivs().find(goodSuffixes));}
           61  +int main(){
           62  +
           63  +CASE(0)
           64  + string goodSuffixes_[] = {"4"};
           65  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           66  + double _ = 0.1;
           67  +END
           68  +CASE(1)
           69  + string goodSuffixes_[] = {"4", "7"};
           70  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           71  + double _ = 0.2;
           72  +END
           73  +CASE(2)
           74  + string goodSuffixes_[] = {"47", "47"};
           75  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           76  + double _ = 0.01;
           77  +END
           78  +CASE(3)
           79  + string goodSuffixes_[] = {"47", "58", "4747", "502"};
           80  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           81  + double _ = 0.021;
           82  +END
           83  +CASE(4)
           84  + string goodSuffixes_[] = {"8542861", "1954", "6", "523", "000000000", "5426", "8"};
           85  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           86  + double _ = 0.201100101;
           87  +END
           88  +/*
           89  +CASE(5)
           90  + string goodSuffixes_[] = ;
           91  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           92  + double _ = ;
           93  +END
           94  +CASE(6)
           95  + string goodSuffixes_[] = ;
           96  +   vector <string> goodSuffixes(goodSuffixes_, goodSuffixes_+sizeof(goodSuffixes_)/sizeof(*goodSuffixes_));
           97  + double _ = ;
           98  +END
           99  +*/
          100  +}
          101  +// END CUT HERE

Added SRM/502-U/1B-U.cpp version [4ee8e1b0161a0735]

            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 <cstring>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class TheProgrammingContestDivOne { public:
           23  + struct Problem
           24  + {
           25  +  LL M;
           26  +  LL D;
           27  +  LL R;
           28  +  bool operator<(const Problem& rhs) const {
           29  +   if(R != rhs.R) return R < rhs.R;
           30  +   if(D != rhs.D) return D > rhs.D;
           31  +   return M > rhs.M;
           32  +  }
           33  + };
           34  + int find(int T, vector <int> maxPoints, vector <int> pointsPerMinute, vector <int> requiredTime)
           35  + {
           36  +  const int N = maxPoints.size();
           37  +  vector<Problem> ps;
           38  +  for(int i=0; i<N; ++i) {
           39  +   Problem p = {maxPoints[i], pointsPerMinute[i], requiredTime[i]};
           40  +   ps.push_back(p);
           41  +  }
           42  +  sort(ps.begin(), ps.end());
           43  +
           44  +  LL best = 0;
           45  +
           46  +  map<LL, LL> st;
           47  +  st[0] = 0;
           48  +  for(int i=0; i<N; ++i)
           49  +  {
           50  +   map<LL, LL> st2 = st;
           51  +   for(map<LL, LL>::iterator it=st.begin(); it!=st.end(); ++it)
           52  +   {
           53  +    LL s = it->first;
           54  +    LL t = it->second;
           55  +    LL t2 = t + ps[i].R;
           56  +    if( t2 <= T ) {
           57  +     LL s2 = s + ps[i].M - ps[i].D * t2;
           58  +     best = max(best, s2);
           59  +     if( s2 > s ) {
           60  +      LL& entry = st2[s2];
           61  +      if( entry==0 || entry>t2 )
           62  +       entry = t2;
           63  +     }
           64  +    }
           65  +   }
           66  +   st.swap(st2);
           67  +  }
           68  +  return int(best);
           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(_, TheProgrammingContestDivOne().find(T, maxPoints, pointsPerMinute, requiredTime));}
           86  +int main(){
           87  +
           88  +CASE(0)
           89  + int T = 74;
           90  + int maxPoints_[] = {502};
           91  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
           92  + int pointsPerMinute_[] = {2};
           93  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
           94  + int requiredTime_[] = {47};
           95  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
           96  + int _ = 408;
           97  +END
           98  +CASE(1)
           99  + int T = 40000;
          100  + int maxPoints_[] = {100000, 100000};
          101  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          102  + int pointsPerMinute_[] = {1, 100000};
          103  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          104  + int requiredTime_[] = {50000, 30000};
          105  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          106  + int _ = 0;
          107  +END
          108  +CASE(2)
          109  + int T = 75;
          110  + int maxPoints_[] = {250, 500, 1000};
          111  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          112  + int pointsPerMinute_[] = {2, 4, 8};
          113  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          114  + int requiredTime_[] = {25, 25, 25};
          115  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          116  + int _ = 1200;
          117  +END
          118  +CASE(3)
          119  + int T = 30;
          120  + int maxPoints_[] = {100, 100, 100000};
          121  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          122  + int pointsPerMinute_[] = {1, 1, 100};
          123  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          124  + int requiredTime_[] = {15, 15, 30};
          125  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          126  + int _ = 97000;
          127  +END
          128  +CASE(4)
          129  + int T = 100000;
          130  + int maxPoints_[] = {100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,};
          131  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          132  +   int pointsPerMinute_[] = {10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,};
          133  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          134  + int requiredTime_[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,4,4};
          135  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          136  + int _ = -1;
          137  +END
          138  +CASE(5)
          139  + int T = 100000;
          140  + int maxPoints_[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,100000,};
          141  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          142  +   int pointsPerMinute_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
          143  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          144  + int requiredTime_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
          145  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          146  + int _ = -1;
          147  +END
          148  +/*
          149  +CASE(5)
          150  + int T = ;
          151  + int maxPoints_[] = ;
          152  +   vector <int> maxPoints(maxPoints_, maxPoints_+sizeof(maxPoints_)/sizeof(*maxPoints_));
          153  + int pointsPerMinute_[] = ;
          154  +   vector <int> pointsPerMinute(pointsPerMinute_, pointsPerMinute_+sizeof(pointsPerMinute_)/sizeof(*pointsPerMinute_));
          155  + int requiredTime_[] = ;
          156  +   vector <int> requiredTime(requiredTime_, requiredTime_+sizeof(requiredTime_)/sizeof(*requiredTime_));
          157  + int _ = ;
          158  +END
          159  +*/
          160  +}
          161  +// END CUT HERE