Overview
| SHA1 Hash: | 8bf237c40df7aad057bb800f2a7f2592593d9caf |
|---|---|
| Date: | 2011-10-04 17:29:37 |
| User: | kinaba |
| Comment: | 520 |
| 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/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[ > 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) > 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 > 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() > 64 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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() > 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( > 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], > 72 for(int p=TOTAL; p>=points[i]+1; --p) > 73 patnum(a[0],a[1],a[2],p) = patnum(a[0],a > 74 for(int p=points[i]; p>=0; --p) > 75 patnum(a[0],a[1],a[2],p) = p>0 ? patnum( > 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) > 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 > 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() > 108 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 109 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 110 #define END verify_case(_, SRMIntermissionPhase().countWays(points, descrip > 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(descript > 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(descript > 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(descript > 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(descript > 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(descript > 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(descript > 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() > 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> codersCha > 46 { > 47 string at = accumulate(codersAttempted.begin(), codersAttempted. > 48 string sc = accumulate(codersChallenged.begin(), codersChallenge > 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) > 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 > 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() > 103 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 104 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 105 #define END verify_case(_, SRMChallengePhase().countWays(codersAttempted, c > 106 int main(){ > 107 > 108 CASE(0) > 109 string codersAttempted_[] = {"YY"}; > 110 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 111 string codersChallenged_[] = {"NY"}; > 112 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 113 int _ = 1; > 114 END > 115 CASE(1) > 116 string codersAttempted_[] = {"YY", "NN"}; > 117 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 118 string codersChallenged_[] = {"N", "NYY"}; > 119 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 120 int _ = 4; > 121 END > 122 CASE(2) > 123 string codersAttempted_[] = {"YNNN"}; > 124 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 125 string codersChallenged_[] = {"NYY", "Y"}; > 126 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 127 int _ = 0; > 128 END > 129 CASE(3) > 130 string codersAttempted_[] = {"N"}; > 131 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 132 string codersChallenged_[] = {"N"}; > 133 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 134 int _ = 1; > 135 END > 136 CASE(4) > 137 string codersAttempted_[] = {"YYY"}; > 138 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 139 string codersChallenged_[] = {"NNY"}; > 140 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 141 int _ = 24; > 142 END > 143 CASE(5) > 144 string codersAttempted_[] = {"YY", "N", "YYYY", "NN", "YYYYY"}; > 145 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 146 string codersChallenged_[] = {"N", "YYYYY", "N", "Y", "N", "YYYY", "N"}; > 147 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 148 int _ = 807026001; > 149 END > 150 /* > 151 CASE(6) > 152 string codersAttempted_[] = ; > 153 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 154 string codersChallenged_[] = ; > 155 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 156 int _ = ; > 157 END > 158 CASE(7) > 159 string codersAttempted_[] = ; > 160 vector <string> codersAttempted(codersAttempted_, codersAttempted_+siz > 161 string codersChallenged_[] = ; > 162 vector <string> codersChallenged(codersChallenged_, codersChallenged_+ > 163 int _ = ; > 164 END > 165 */ > 166 } > 167 // END CUT HERE