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

Added SRM/520-U/1A.cpp version [ba2c28c303f93cee]

            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 SRMCodingPhase { public:
           23  + int countScore(vector <int> points, vector <int> skills, int luck)
           24  + {
           25  +  const int dec[] = {2,4,8};
           26  +
           27  +  int pBest = 0;
           28  +
           29  +  int i[3];
           30  +  for(i[0]=0; i[0]<skills[0] && i[0]<=luck; ++i[0])
           31  +  for(i[1]=0; i[1]<skills[1] && i[0]+i[1]<=luck; ++i[1])
           32  +  for(i[2]=0; i[2]<skills[2] && i[0]+i[1]+i[2]<=luck; ++i[2])
           33  +  {
           34  +   int a[3];
           35  +   for(a[0]=0; a[0]<2; ++a[0])
           36  +   for(a[1]=0; a[1]<2; ++a[1])
           37  +   for(a[2]=0; a[2]<2; ++a[2])
           38  +   {
           39  +    int p = 0, t = 0;
           40  +    for(int x=0; x<3; ++x)
           41  +     if( a[x] ) {
           42  +      p += points[x] - dec[x]*(skills[x]-i[x]);
           43  +      t += skills[x]-i[x];
           44  +     }
           45  +    if( t <= 75 )
           46  +     pBest = max(pBest, p);
           47  +   }
           48  +  }
           49  +  return pBest;
           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(_, SRMCodingPhase().countScore(points, skills, luck));}
           67  +int main(){
           68  +
           69  +CASE(0)
           70  + int points_[] = {250, 500, 1000};
           71  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           72  + int skills_[] = {10, 25, 40};
           73  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
           74  + int luck = 0;
           75  + int _ = 1310;
           76  +END
           77  +CASE(1)
           78  + int points_[] = {300, 600, 900};
           79  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           80  + int skills_[] = {30, 65, 90};
           81  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
           82  + int luck = 25;
           83  + int _ = 680;
           84  +END
           85  +CASE(2)
           86  + int points_[] = {250, 550, 950};
           87  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           88  + int skills_[] = {10, 25, 40};
           89  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
           90  + int luck = 75;
           91  + int _ = 1736;
           92  +END
           93  +CASE(3)
           94  + int points_[] = {256, 512, 1024};
           95  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           96  + int skills_[] = {35, 30, 25};
           97  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
           98  + int luck = 0;
           99  + int _ = 1216;
          100  +END
          101  +CASE(4)
          102  + int points_[] = {300, 600, 1100};
          103  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          104  + int skills_[] = {80, 90, 100};
          105  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
          106  + int luck = 4;
          107  + int _ = 0;
          108  +END
          109  +CASE(5)
          110  +int points_[] = {300,600,1100};
          111  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          112  +   int skills_[] = {30,30,30};
          113  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
          114  + int luck = 100;
          115  + int _ = -1;
          116  +END
          117  +/*
          118  +CASE(6)
          119  + int points_[] = ;
          120  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          121  + int skills_[] = ;
          122  +   vector <int> skills(skills_, skills_+sizeof(skills_)/sizeof(*skills_));
          123  + int luck = ;
          124  + int _ = ;
          125  +END
          126  +*/
          127  +}
          128  +// END CUT HERE

Added SRM/520-U/1B.cpp version [3680215ae4f12899]

            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  +static const int MODVAL = 1000000007; // must be prime for op/
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {}
           28  + mint(size_t x):val(x%MODVAL) {}
           29  + mint(LL     x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           35  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           36  +mint operator+(mint x, mint y) { return x+=y; }
           37  +mint operator-(mint x, mint y) { return x-=y; }
           38  +mint operator*(mint x, mint y) { return x*=y; }
           39  +mint operator/(mint x, mint y) { return x/=y; }
           40  +vector<mint> FAC_(1,1);
           41  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           42  +mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
           43  +
           44  +template<typename T>
           45  +struct DP4
           46  +{
           47  + int N1, N2, N3, N4;
           48  + vector<T> data;
           49  + DP4(int N1, int N2, int N3, int N4, const T& t = T())
           50  +  : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           51  + T& operator()(int i1, int i2, int i3, int i4)
           52  +  { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
           53  + void swap(DP4& rhs)
           54  +  { data.swap(rhs.data); }
           55  +};
           56  +
           57  +class SRMIntermissionPhase { public:
           58  + int countWays(vector <int> points, vector <string> description)
           59  + {
           60  +  const int TOTAL = accumulate(points.begin(), points.end(), 0);
           61  +
           62  +  DP4<mint> patnum(2,2,2,TOTAL+1);
           63  +  int a[3];
           64  +  for(a[0]=0; a[0]<2; ++a[0])
           65  +  for(a[1]=0; a[1]<2; ++a[1])
           66  +  for(a[2]=0; a[2]<2; ++a[2])
           67  +  {
           68  +   patnum(a[0],a[1],a[2],0) = 1;
           69  +   for(int i=0; i<3; ++i) if(a[i]) {
           70  +    for(int p=1; p<=TOTAL; ++p)
           71  +     patnum(a[0],a[1],a[2],p) += patnum(a[0],a[1],a[2],p-1);
           72  +    for(int p=TOTAL; p>=points[i]+1; --p)
           73  +     patnum(a[0],a[1],a[2],p) = patnum(a[0],a[1],a[2],p-1) - patnum(a[0],a[1],a[2],p-points[i]-1);
           74  +    for(int p=points[i]; p>=0; --p)
           75  +     patnum(a[0],a[1],a[2],p) = p>0 ? patnum(a[0],a[1],a[2],p-1) : 0;
           76  +   }
           77  +  }
           78  +
           79  +  vector<mint> dp(TOTAL+2);
           80  +  dp[0] = 1; // -1
           81  +  for(int i=description.size()-1; i>=0; --i)
           82  +  {
           83  +   partial_sum(dp.begin(), dp.end(), dp.begin());
           84  +   for(int s=TOTAL; s>=0; --s)
           85  +    dp[s+1] = dp[s] * patnum(
           86  +     description[i][0]=='Y',
           87  +     description[i][1]=='Y',
           88  +     description[i][2]=='Y',
           89  +     s
           90  +    );
           91  +   dp[0] = 0;
           92  +  }
           93  +  return accumulate(dp.begin()+1, dp.end(), mint(0)).val;
           94  + }
           95  +};
           96  +
           97  +// BEGIN CUT HERE
           98  +#include <ctime>
           99  +double start_time; string timer()
          100  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          101  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          102  + { os << "{ ";
          103  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          104  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          105  +void verify_case(const int& Expected, const int& Received) {
          106  + bool ok = (Expected == Received);
          107  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          108  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          109  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          110  +#define END  verify_case(_, SRMIntermissionPhase().countWays(points, description));}
          111  +int main(){
          112  +
          113  +CASE(4)
          114  +int points_[] = {1,2,3};
          115  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          116  +   string description_[] = {"YNN","NNN"};
          117  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          118  + int _ = 1;
          119  +END
          120  +CASE(0)
          121  + int points_[] = {25000, 50000, 100000};
          122  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          123  + string description_[] = {"YNN",
          124  + "NNN"};
          125  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          126  + int _ = 25000;
          127  +END
          128  +CASE(1)
          129  + int points_[] = {30000, 60000, 90000};
          130  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          131  + string description_[] = {"NYN",
          132  + "NYN"};
          133  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          134  + int _ = 799969993;
          135  +END
          136  +CASE(2)
          137  + int points_[] = {25000, 45000, 110000};
          138  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          139  + string description_[] = {"NNN",
          140  + "YYY"};
          141  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          142  + int _ = 0;
          143  +END
          144  +CASE(3)
          145  + int points_[] = {25600, 51200, 102400};
          146  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          147  + string description_[] = {"NYY",
          148  + "YNY",
          149  + "YYY",
          150  + "YNN",
          151  + "YYN",
          152  + "NNY",
          153  + "NYN",
          154  + "NNN"};
          155  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          156  + int _ = 867560805;
          157  +END
          158  +CASE(5)
          159  +int points_[] = {30000,60000,110000};
          160  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          161  + string description_[] = {
          162  +  "YYY",
          163  +  "YYY",
          164  +  "YYY",
          165  +  "YYY",
          166  +  "YYY",
          167  +  "YYY",
          168  +  "YYY",
          169  +  "YYY",
          170  +  "YYY",
          171  +  "YYY",
          172  +  "YYY",
          173  +  "YYY",
          174  +  "YYY",
          175  +  "YYY",
          176  +  "YYY",
          177  +  "YYY",
          178  +  "YYY",
          179  +  "YYY",
          180  +  "YYY",
          181  +  "YYY",
          182  + };
          183  +   vector <string> description(description_, description_+sizeof(description_)/sizeof(*description_));
          184  + int _ = -1;
          185  +END
          186  +}
          187  +// END CUT HERE

Added SRM/520-U/1C-U.cpp version [7ea625a8bdca1eb3]

            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  +static const int MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {}
           28  + mint(size_t x):val(x%MODVAL) {}
           29  + mint(LL     x):val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           35  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           36  +mint operator+(mint x, mint y) { return x+=y; }
           37  +mint operator-(mint x, mint y) { return x-=y; }
           38  +mint operator*(mint x, mint y) { return x*=y; }
           39  +mint operator/(mint x, mint y) { return x/=y; }
           40  +vector<mint> FAC_(1,1);
           41  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           42  +mint C(LL n, LL k) { return k<0 || n<k ? 0 : FAC(n) / (FAC(k) * FAC(n-k)); }
           43  +
           44  +class SRMChallengePhase { public:
           45  + int countWays(vector <string> codersAttempted, vector <string> codersChallenged)
           46  + {
           47  +  string at = accumulate(codersAttempted.begin(), codersAttempted.end(), string(""));
           48  +  string sc = accumulate(codersChallenged.begin(), codersChallenged.end(), string(""));
           49  +  const int N = at.size();
           50  +  int NN=0, NY=0, YN=0, YY=0;
           51  +  for(int i=0; i<N; ++i)
           52  +   if( at[i]=='N' )
           53  +    (sc[i]=='N' ? NN : NY) ++;
           54  +   else
           55  +    (sc[i]=='N' ? YN : YY) ++;
           56  +  return solve(NN, NY, YN, YY);
           57  + }
           58  +
           59  + int solve(int NN, int NY, int YN, int YY)
           60  + {
           61  +  memo.clear();
           62  +  TOTAL = NN+NY+YN+YY;
           63  +  return rec(YN, NY, YY).val;
           64  + }
           65  +
           66  + map<pair<pair<int,int>,int>, mint> memo;
           67  + int TOTAL;
           68  + mint rec(int YN, int NY, int YY)
           69  + {
           70  +  if(YN+YY < YY+NY)
           71  +   return 0;
           72  +  if(YN==0 && YY==0)
           73  +   return 1;
           74  +
           75  +  pair<pair<int,int>,int> key(make_pair(YN,NY),YY);
           76  +  if( memo.count(key) )
           77  +   return memo[key];
           78  +  mint ans = 0;
           79  +
           80  +  // YN, unsuc
           81  +  if(YN) ans += rec(YN-1, NY, YY) * YN * (TOTAL-1);
           82  +  // YN, suc
           83  +  if(YN&&NY) ans += rec(YN-1, NY-1, YY) * YN * NY;
           84  +  // YY, unsuc
           85  +  if(YY) ans += rec(YN, NY+1, YY-1) * YY * (TOTAL-1);
           86  +  // YY, suc
           87  +  if(YY&&NY) ans += rec(YN, NY, YY-1) * YY * NY;
           88  +  return memo[key] = ans;
           89  + }
           90  +};
           91  +
           92  +// BEGIN CUT HERE
           93  +#include <ctime>
           94  +double start_time; string timer()
           95  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           96  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           97  + { os << "{ ";
           98  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           99  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          100  +void verify_case(const int& Expected, const int& Received) {
          101  + bool ok = (Expected == Received);
          102  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          103  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          104  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          105  +#define END  verify_case(_, SRMChallengePhase().countWays(codersAttempted, codersChallenged));}
          106  +int main(){
          107  +
          108  +CASE(0)
          109  + string codersAttempted_[] = {"YY"};
          110  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          111  + string codersChallenged_[] = {"NY"};
          112  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          113  + int _ = 1;
          114  +END
          115  +CASE(1)
          116  + string codersAttempted_[] = {"YY", "NN"};
          117  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          118  + string codersChallenged_[] = {"N", "NYY"};
          119  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          120  + int _ = 4;
          121  +END
          122  +CASE(2)
          123  + string codersAttempted_[] = {"YNNN"};
          124  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          125  + string codersChallenged_[] = {"NYY", "Y"};
          126  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          127  + int _ = 0;
          128  +END
          129  +CASE(3)
          130  + string codersAttempted_[] = {"N"};
          131  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          132  + string codersChallenged_[] = {"N"};
          133  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          134  + int _ = 1;
          135  +END
          136  +CASE(4)
          137  + string codersAttempted_[] = {"YYY"};
          138  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          139  + string codersChallenged_[] = {"NNY"};
          140  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          141  + int _ = 24;
          142  +END
          143  +CASE(5)
          144  + string codersAttempted_[] = {"YY", "N", "YYYY", "NN", "YYYYY"};
          145  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          146  + string codersChallenged_[] = {"N", "YYYYY", "N", "Y", "N", "YYYY", "N"};
          147  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          148  + int _ = 807026001;
          149  +END
          150  +/*
          151  +CASE(6)
          152  + string codersAttempted_[] = ;
          153  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          154  + string codersChallenged_[] = ;
          155  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          156  + int _ = ;
          157  +END
          158  +CASE(7)
          159  + string codersAttempted_[] = ;
          160  +   vector <string> codersAttempted(codersAttempted_, codersAttempted_+sizeof(codersAttempted_)/sizeof(*codersAttempted_));
          161  + string codersChallenged_[] = ;
          162  +   vector <string> codersChallenged(codersChallenged_, codersChallenged_+sizeof(codersChallenged_)/sizeof(*codersChallenged_));
          163  + int _ = ;
          164  +END
          165  +*/
          166  +}
          167  +// END CUT HERE