Overview
| SHA1 Hash: | 1a2a57338cde6b576dfdc8926595eb0280719076 |
|---|---|
| Date: | 2012-01-20 02:01:30 |
| User: | kinaba |
| Comment: | 529 |
| 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/529-U/1A.cpp version [872512230b80af22]
> 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 static string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "I > 29 static string tens[] = {"", "X", "XX", "XXX", "XL", "L"}; > 30 > 31 class KingSort { public: > 32 vector <string> getSortedList(vector <string> kings) > 33 { > 34 vector< pair<string,int> > kk; > 35 for(int i=0; i<kings.size(); ++i) > 36 kk.push_back( parse(kings[i]) ); > 37 sort(kk.begin(), kk.end()); > 38 for(int i=0; i<kings.size(); ++i) > 39 kings[i] = encode(kk[i]); > 40 return kings; > 41 } > 42 > 43 pair<string, int> parse(const string& s) > 44 { > 45 stringstream ss(s); > 46 string name, ord; > 47 ss >> name >> ord; > 48 return make_pair(name, roman(ord)); > 49 } > 50 > 51 int roman(const string& s) > 52 { > 53 for(int i=0; i<=s.size(); ++i) > 54 { > 55 int ti = find(&tens[0], &tens[6], s.substr(0, i)) - &ten > 56 int oi = find(&ones[0], &ones[10], s.substr(i)) - &ones[ > 57 if( oi == 10 || ti == 6 ) > 58 continue; > 59 return oi + ti*10; > 60 } > 61 return -99999; > 62 } > 63 > 64 string encode(const pair<string,int>& p) > 65 { > 66 stringstream ss; > 67 ss << p.first << " " << tens[p.second/10] << ones[p.second%10]; > 68 return ss.str(); > 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) > 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 > 80 void verify_case(const vector <string>& Expected, const vector <string>& Receive > 81 bool ok = (Expected == Received); > 82 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 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(_, KingSort().getSortedList(kings));} > 86 int main(){ > 87 > 88 CASE(0) > 89 string kings_[] = {"Louis IX", "Louis VIII"}; > 90 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 91 string __[] = {"Louis VIII", "Louis IX" }; > 92 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 93 END > 94 CASE(1) > 95 string kings_[] = {"Louis IX", "Philippe II"}; > 96 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 97 string __[] = {"Louis IX", "Philippe II" }; > 98 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 99 END > 100 CASE(2) > 101 string kings_[] = {"Richard III", "Richard I", "Richard II"}; > 102 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 103 string __[] = {"Richard I", "Richard II", "Richard III" }; > 104 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 105 END > 106 CASE(3) > 107 string kings_[] = {"John X", "John I", "John L", "John V"}; > 108 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 109 string __[] = {"John I", "John V", "John X", "John L" }; > 110 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 111 END > 112 CASE(4) > 113 string kings_[] = {"Philippe VI", "Jean II", "Charles V", "Charles VI", > 114 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 115 string __[] = {"Charles V", "Charles VI", "Charles VII", "Jean II", "Lou > 116 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 117 END > 118 CASE(5) > 119 string kings_[] = {"Philippe II", "Philip II"}; > 120 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 121 string __[] = {"Philip II", "Philippe II" }; > 122 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 123 END > 124 /* > 125 CASE(6) > 126 string kings_[] = ; > 127 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 128 string __[] = ; > 129 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 130 END > 131 CASE(7) > 132 string kings_[] = ; > 133 vector <string> kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); > 134 string __[] = ; > 135 vector <string> _(__, __+sizeof(__)/sizeof(*__)); > 136 END > 137 */ > 138 } > 139 // END CUT HERE
Added SRM/529-U/1B-U.cpp version [340c6fa4252b478a]
> 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 static const int MODVAL = 1000000009; > 29 > 30 class MinskyMystery { public: > 31 int computeAnswer(long long N) > 32 { > 33 return N<2 ? -1 : theCode(N); > 34 } > 35 > 36 LL theCode(LL N) > 37 { > 38 LL counter = 1; > 39 for(LL a=2 ;; ++a) { > 40 {counter += N*4 + (N+a-1)/a + 1;} > 41 if( N%a == 0 ) > 42 return counter - N; > 43 } > 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) > 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 > 55 void verify_case(const int& Expected, const int& Received) { > 56 bool ok = (Expected == Received); > 57 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 58 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 59 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 60 #define END verify_case(_, MinskyMystery().computeAnswer(N));} > 61 int main(){ > 62 > 63 CASE(0) > 64 long long N = 2LL; > 65 int _ = 9; > 66 END > 67 CASE(1) > 68 long long N = 3LL; > 69 int _ = 27; > 70 END > 71 CASE(2) > 72 long long N = 4LL; > 73 int _ = 16; > 74 END > 75 CASE(3) > 76 long long N = 2401LL; > 77 int _ = 59058; > 78 END > 79 CASE(4) > 80 long long N = 24LL; > 81 int _ = 86; > 82 END > 83 CASE(5) > 84 long long N = 1; > 85 int _ = -1; > 86 END > 87 > 88 } > 89 // END CUT HERE
Added SRM/529-U/1C-U.cpp version [89efd56699a58e1a]
> 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 BigAndSmallAirports { public: > 29 long long solve(int Nlo, int Nhi, int Blo, int Bhi, int Slo, int Shi) > 30 { > 31 LL cnt = 0; > 32 for(int B=Blo; B<=Bhi; ++B) > 33 for(int S=Slo; S<=Shi; ++S) > 34 if( S < B ) > 35 cnt += fast(Nhi, B, S) - fast(Nlo-1, B, S); > 36 return cnt; > 37 } > 38 > 39 LL fast(LL N, LL B, LL S) > 40 { > 41 LL cnt = 0; > 42 for(LL k=0; k<=N; ++k) { > 43 LL Nmin = ((1+B+S)*k - k*k + S-1) / S; > 44 if( Nmin < 0 ) { > 45 cnt += (N-k+1)*(N-k+2)/2; > 46 break; > 47 } > 48 Nmin = max(Nmin, k); > 49 if( N >= Nmin ) > 50 cnt += (N-Nmin+1); > 51 } > 52 return cnt; > 53 } > 54 }; > 55 > 56 // BEGIN CUT HERE > 57 #include <ctime> > 58 double start_time; string timer() > 59 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 60 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 61 { os << "{ "; > 62 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 63 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 64 void verify_case(const long long& Expected, const long long& Received) { > 65 bool ok = (Expected == Received); > 66 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 67 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 68 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 69 #define END verify_case(_, BigAndSmallAirports().solve(Nlo, Nhi, Blo, Bhi, > 70 int main(){ > 71 > 72 CASE(0) > 73 int Nlo = 20; > 74 int Nhi = 20; > 75 int Blo = 3; > 76 int Bhi = 3; > 77 int Slo = 2; > 78 int Shi = 2; > 79 long long _ = 21LL; > 80 END > 81 CASE(1) > 82 int Nlo = 1; > 83 int Nhi = 1; > 84 int Blo = 10; > 85 int Bhi = 10; > 86 int Slo = 2; > 87 int Shi = 2; > 88 long long _ = 1LL; > 89 END > 90 CASE(2) > 91 int Nlo = 10; > 92 int Nhi = 10; > 93 int Blo = 8; > 94 int Bhi = 8; > 95 int Slo = 3; > 96 int Shi = 3; > 97 long long _ = 6LL; > 98 END > 99 CASE(3) > 100 int Nlo = 10; > 101 int Nhi = 100; > 102 int Blo = 13; > 103 int Bhi = 15; > 104 int Slo = 18; > 105 int Shi = 22; > 106 long long _ = 0LL; > 107 END > 108 CASE(4) > 109 int Nlo = 30; > 110 int Nhi = 32; > 111 int Blo = 8; > 112 int Bhi = 10; > 113 int Slo = 6; > 114 int Shi = 8; > 115 long long _ = 768LL; > 116 END > 117 CASE(5) > 118 int Nlo = 1; > 119 int Nhi = 10000000; > 120 int Blo = 1; > 121 int Bhi = 200; > 122 int Slo = 1; > 123 int Shi = 200; > 124 long long _ = -1LL; > 125 END > 126 /* > 127 CASE(6) > 128 int Nlo = ; > 129 int Nhi = ; > 130 int Blo = ; > 131 int Bhi = ; > 132 int Slo = ; > 133 int Shi = ; > 134 long long _ = LL; > 135 END > 136 */ > 137 } > 138 // END CUT HERE