Overview
| SHA1 Hash: | e16cea6bfeb18a19d0a73d843b5b19a985759dae |
|---|---|
| Date: | 2012-02-19 04:20:04 |
| User: | kinaba |
| Comment: | 2 |
| 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/533-U/2A.cpp version [127824245ae6e183]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 class PikachuEasy { public: > 29 string check(string word) > 30 { > 31 string zz[] = {"pi", "ka", "chu"}; > 32 while(!word.empty()) > 33 { > 34 for(int i=0; i<3; ++i) > 35 if( word.size()>=zz[i].size() && word.substr(0,z > 36 word = word.substr(zz[i].size()); > 37 goto next; > 38 } > 39 return "NO"; > 40 next:; > 41 } > 42 return "YES"; > 43 } > 44 }; > 45 > 46 // BEGIN CUT HERE > 47 #include <ctime> > 48 double start_time; string timer() > 49 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 50 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 51 { os << "{ "; > 52 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 53 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 54 void verify_case(const string& Expected, const string& Received) { > 55 bool ok = (Expected == Received); > 56 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 57 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 58 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 59 #define END verify_case(_, PikachuEasy().check(word));} > 60 int main(){ > 61 > 62 CASE(0) > 63 string word = "pikapi"; > 64 string _ = "YES"; > 65 END > 66 CASE(1) > 67 string word = "pipikachu"; > 68 string _ = "YES"; > 69 END > 70 CASE(2) > 71 string word = "pikaqiu"; > 72 string _ = "NO"; > 73 END > 74 CASE(3) > 75 string word = "topcoder"; > 76 string _ = "NO"; > 77 END > 78 CASE(4) > 79 string word = "piika"; > 80 string _ = "NO"; > 81 END > 82 CASE(5) > 83 string word = "chupikachupipichu"; > 84 string _ = "YES"; > 85 END > 86 CASE(6) > 87 string word = "pikapipachu"; > 88 string _ = "NO"; > 89 END > 90 /* > 91 CASE(7) > 92 string word = ; > 93 string _ = ; > 94 END > 95 CASE(8) > 96 string word = ; > 97 string _ = ; > 98 END > 99 */ > 100 } > 101 // END CUT HERE
Added SRM/533-U/2C.cpp version [3b1dbfbdda0d2254]
> 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 #ifdef __GNUC__ > 19 #include <ext/hash_map> > 20 #define unordered_map __gnu_cxx::hash_map > 21 #else > 22 #include <unordered_map> > 23 #endif > 24 using namespace std; > 25 typedef long long LL; > 26 typedef complex<double> CMP; > 27 > 28 template<typename T> > 29 struct DP2 > 30 { > 31 const int N1, N2; > 32 vector<T> data; > 33 DP2(int N1, int N2, const T& t = T()) > 34 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 35 T& operator()(int i1, int i2) > 36 { return data[ (i1*N2)+i2 ]; } > 37 void swap(DP2& rhs) > 38 { data.swap(rhs.data); } > 39 }; > 40 > 41 class MagicalGirl { public: > 42 double maxExpectation(int M, vector <int> day, vector <int> win, vector > 43 { > 44 vector< pair< int, pair<double, int> > > majos; > 45 for(int i=0; i<day.size(); ++i) > 46 majos.push_back( make_pair(day[i], make_pair(win[i]/100. > 47 sort(majos.begin(), majos.end()); > 48 > 49 DP2<double> dp(day.size()+1, M+1); > 50 for(int i=majos.size(); i>=0; --i) > 51 for(int hp=0; hp<=M; ++hp) > 52 { > 53 // Days passed from the last Witch's attack. > 54 const int days = i==majos.size() ? INT_MAX > 55 : majos[i].first - (i== > 56 if( hp <= days ) > 57 dp(i, hp) = hp; // no way to gain power any more > 58 else { > 59 const double pWin = majos[i].second.first; > 60 const int gain = majos[i].second.second; > 61 dp(i, hp) = days + max(pWin*dp(i+1, min(M, hp-da > 62 dp(i+1, min(M, hp-days))) > 63 } > 64 } > 65 return dp(0, M); > 66 } > 67 }; > 68 > 69 // BEGIN CUT HERE > 70 #include <ctime> > 71 double start_time; string timer() > 72 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 73 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 74 { os << "{ "; > 75 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 76 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 77 void verify_case(const double& Expected, const double& Received) { > 78 bool ok = (abs(Expected - Received) < 1e-9); > 79 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 80 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 81 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 82 #define END verify_case(_, MagicalGirl().maxExpectation(M, day, win, gain)) > 83 int main(){ > 84 > 85 CASE(0) > 86 int M = 2; > 87 int day_[] = {1}; > 88 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 89 int win_[] = {75}; > 90 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 91 int gain_[] = {1}; > 92 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 93 double _ = 2.5; > 94 END > 95 CASE(1) > 96 int M = 10; > 97 int day_[] = {5,5,5,5}; > 98 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 99 int win_[] = {100,100,100,100}; > 100 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 101 int gain_[] = {1,1,1,1}; > 102 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 103 double _ = 14.0; > 104 END > 105 CASE(2) > 106 int M = 10; > 107 int day_[] = {5,5,5,5,5}; > 108 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 109 int win_[] = {40,80,60,20,0}; > 110 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 111 int gain_[] = {10,10,10,10,10}; > 112 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 113 double _ = 13.0; > 114 END > 115 CASE(3) > 116 int M = 2; > 117 int day_[] = {2}; > 118 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 119 int win_[] = {100}; > 120 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 121 int gain_[] = {2}; > 122 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 123 double _ = 2.0; > 124 END > 125 CASE(4) > 126 int M = 20; > 127 int day_[] = {2,13,8,7,9,4,6,21}; > 128 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 129 int win_[] = {18,83,75,23,45,23,10,98}; > 130 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 131 int gain_[] = {10,9,8,10,7,16,13,20}; > 132 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 133 double _ = 35.908; > 134 END > 135 CASE(5) > 136 int M = 11; > 137 int day_[] = {10,20,30,40,50,60,70,80,90}; > 138 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 139 int win_[] = {100,100,100,100,100,100,100,100,100}; > 140 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 141 int gain_[] = {10,10,10,10,10,10,10,10,10}; > 142 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 143 double _ = 101.0; > 144 END > 145 CASE(6) > 146 int M = 100000; > 147 int day_[] = {1000000}; > 148 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 149 int win_[] = {100}; > 150 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 151 int gain_[] = {100000}; > 152 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 153 double _ = 100000.0; > 154 END > 155 /* > 156 CASE(7) > 157 int M = ; > 158 int day_[] = ; > 159 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 160 int win_[] = ; > 161 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 162 int gain_[] = ; > 163 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 164 double _ = ; > 165 END > 166 CASE(8) > 167 int M = ; > 168 int day_[] = ; > 169 vector <int> day(day_, day_+sizeof(day_)/sizeof(*day_)); > 170 int win_[] = ; > 171 vector <int> win(win_, win_+sizeof(win_)/sizeof(*win_)); > 172 int gain_[] = ; > 173 vector <int> gain(gain_, gain_+sizeof(gain_)/sizeof(*gain_)); > 174 double _ = ; > 175 END > 176 */ > 177 } > 178 // END CUT HERE