Overview
| SHA1 Hash: | f6f3e6962a5b00acf6e7ed7b5d8653b213a3bb31 |
|---|---|
| Date: | 2011-04-09 01:37:13 |
| User: | kinaba |
| Comment: | 501 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/501-U/1A.cpp version [d3ffed894b1fce35]
> 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 FoxPlayingGame { public: > 23 double theMax(int nA, int nB, int paramA, int paramB) > 24 { > 25 double scoreA = paramA / 1000.0; > 26 double scoreB = paramB / 1000.0; > 27 > 28 double cur=scoreA*nA, best=cur; > 29 for(int i=0; i<=nB; ++i,cur*=scoreB) > 30 best = max(best, cur); > 31 return best; > 32 } > 33 }; > 34 > 35 // BEGIN CUT HERE > 36 #include <ctime> > 37 double start_time; string timer() > 38 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 39 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 40 { os << "{ "; > 41 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 42 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 43 void verify_case(const double& Expected, const double& Received) { > 44 bool ok = (abs(Expected - Received) < 1e-9); > 45 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 46 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 47 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 48 #define END verify_case(_, FoxPlayingGame().theMax(nA, nB, paramA, paramB)) > 49 int main(){ > 50 > 51 CASE(0) > 52 int nA = 5; > 53 int nB = 4; > 54 int paramA = 3000; > 55 int paramB = 2000; > 56 double _ = 240.0; > 57 END > 58 CASE(1) > 59 int nA = 3; > 60 int nB = 3; > 61 int paramA = 2000; > 62 int paramB = 100; > 63 double _ = 6.0; > 64 END > 65 CASE(2) > 66 int nA = 4; > 67 int nB = 3; > 68 int paramA = -2000; > 69 int paramB = 2000; > 70 double _ = -8.0; > 71 END > 72 CASE(3) > 73 int nA = 5; > 74 int nB = 5; > 75 int paramA = 2000; > 76 int paramB = -2000; > 77 double _ = 160.0; > 78 END > 79 CASE(4) > 80 int nA = 50; > 81 int nB = 50; > 82 int paramA = 10000; > 83 int paramB = 2000; > 84 double _ = 5.62949953421312E17; > 85 END > 86 CASE(5) > 87 int nA = 41; > 88 int nB = 34; > 89 int paramA = 9876; > 90 int paramB = -1234; > 91 double _ = 515323.9982341775; > 92 END > 93 CASE(6) > 94 int nA = 23; > 95 int nB = 34; > 96 int paramA = -9422; > 97 int paramB = -180; > 98 double _ = 39.00708; > 99 END > 100 /* > 101 CASE(7) > 102 int nA = ; > 103 int nB = ; > 104 int paramA = ; > 105 int paramB = ; > 106 double _ = ; > 107 END > 108 */ > 109 } > 110 // END CUT HERE
Added SRM/501-U/1B.cpp version [91246eeadde8d75d]
> 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 template<typename T> > 23 struct DP4 > 24 { > 25 int N1, N2, N3, N4; > 26 vector<T> data; > 27 DP4(int N1, int N2, int N3, int N4, const T& t = T()) > 28 : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert( > 29 T& operator()(int i1, int i2, int i3, int i4) > 30 { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; } > 31 }; > 32 > 33 static const int MODVAL = 1000000007; > 34 > 35 class FoxAverageSequence { public: > 36 int theCount(vector <int> seq) > 37 { > 38 const int N = seq.size(); > 39 > 40 DP4<LL> dp(N,2,41,40*N+1); > 41 for(int b=0; b<=40; ++b) > 42 if( seq[0]==-1 || seq[0]==b ) > 43 dp(0,0,b,b) += 1; > 44 > 45 for(int i=1; i<N; ++i) > 46 for(int dn=0; dn<=1; ++dn) > 47 for(int b=0; b<=40; ++b) > 48 for(int s=0; s<=40*i; ++s) > 49 if( LL v = dp(i-1,dn,b,s) ) > 50 for(int c=0; c<=min(40,s/i); ++c) > 51 if( seq[i]==-1 || seq[i]==c ) > 52 if( !dn || b<=c ) > 53 (dp(i,b>c,c,s+c) += v) % > 54 > 55 LL ans = 0; > 56 for(int dn=0; dn<=1; ++dn) > 57 for(int b=0; b<=40; ++b) > 58 for(int s=0; s<=40*N; ++s) > 59 ans += dp(N-1,dn,b,s); > 60 return ans % MODVAL; > 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) > 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 > 72 void verify_case(const int& Expected, const int& Received) { > 73 bool ok = (Expected == Received); > 74 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 75 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 76 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 77 #define END verify_case(_, FoxAverageSequence().theCount(seq));} > 78 int main(){ > 79 > 80 CASE(0) > 81 int seq_[] = {3, -1}; > 82 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 83 int _ = 4; > 84 END > 85 CASE(1) > 86 int seq_[] = {5, 3, -1}; > 87 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 88 int _ = 2; > 89 END > 90 CASE(2) > 91 int seq_[] = {-1, 0, 40}; > 92 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 93 int _ = 0; > 94 END > 95 CASE(3) > 96 int seq_[] = {-1, 40, -1, -1, -1, 10, -1, -1, -1, 21, -1}; > 97 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 98 int _ = 579347890; > 99 END > 100 CASE(4) > 101 int seq_[] = {-1, 12, 25, 0, 18, -1}; > 102 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 103 int _ = 58; > 104 END > 105 CASE(5) > 106 int seq_[] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, > 107 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 108 int _ = -1; > 109 END > 110 CASE(6) > 111 int seq_[] = {-1}; > 112 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 113 int _ = 41; > 114 END > 115 CASE(7) > 116 int seq_[] = {-1,-1}; > 117 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 118 int _ = (41+1)*41/2; > 119 END > 120 CASE(8) > 121 int seq_[] = {-1,-1,0}; > 122 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 123 int _ = 81; > 124 END > 125 } > 126 // END CUT HERE