Overview
| SHA1 Hash: | 9a1914336ee23a25bf9d194eaca8cef7bd0a7772 |
|---|---|
| Date: | 2011-03-08 15:09:54 |
| User: | kinaba |
| Comment: | 498 |
| 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/498-U/1A.cpp version [bc240ca099bb34e9]
> 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 FoxSequence { public: > 23 string isValid(vector <int> seq) > 24 { > 25 for(int b=2; b<seq.size(); ++b) > 26 for(int c=b; c<seq.size()-2; ++c) > 27 if( isFox(seq,b,c) ) > 28 return "YES"; > 29 return "NO"; > 30 } > 31 > 32 bool isFox( const vector<int>& seq, const int b, const int c ) > 33 { > 34 for(int i=b; i<=c; ++i) > 35 if( seq[i] != seq[b] ) > 36 return false; > 37 return isUpDown(seq, 0, b) && isUpDown(seq, c, seq.size()-1); > 38 } > 39 > 40 bool isUpDown( const vector<int>& seq, const int L, const int R ) > 41 { > 42 int i = max_element(seq.begin()+L, seq.begin()+R+1) - seq.begin( > 43 if( L<i && i<R ) > 44 { > 45 if( seq[L+1]>seq[L] && isArith(seq, L, i, seq[L+1]-seq[L > 46 && seq[R-1]>seq[R] && isArith(seq, i, R, seq[i+1]-seq[i > 47 return true; > 48 } > 49 return false; > 50 } > 51 > 52 bool isArith( const vector<int>& seq, const int L, const int R, int d ) > 53 { > 54 for(int i=L; i+1<=R; ++i) > 55 if( seq[i+1]-seq[i] != d ) > 56 return false; > 57 return true; > 58 } > 59 }; > 60 > 61 // BEGIN CUT HERE > 62 #include <ctime> > 63 double start_time; string timer() > 64 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 65 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 66 { os << "{ "; > 67 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 68 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 69 void verify_case(const string& Expected, const string& Received) { > 70 bool ok = (Expected == Received); > 71 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 72 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 73 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 74 #define END verify_case(_, FoxSequence().isValid(seq));} > 75 int main(){ > 76 > 77 CASE(0) > 78 int seq_[] = {1,3,5,7,5,3,1,1,1,3,5,7,5,3,1} > 79 ; > 80 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 81 string _ = "YES"; > 82 END > 83 CASE(1) > 84 int seq_[] = {1,2,3,4,5,4,3,2,2,2,3,4,5,6,4} > 85 ; > 86 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 87 string _ = "YES"; > 88 END > 89 CASE(2) > 90 int seq_[] = {3,6,9,1,9,5,1} > 91 ; > 92 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 93 string _ = "YES"; > 94 END > 95 CASE(3) > 96 int seq_[] = {1,2,3,2,1,2,3,2,1,2,3,2,1} > 97 ; > 98 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 99 string _ = "NO"; > 100 END > 101 CASE(4) > 102 int seq_[] = {1,3,4,3,1,1,1,1,3,4,3,1} > 103 ; > 104 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 105 string _ = "NO"; > 106 END > 107 CASE(5) > 108 int seq_[] = {6,1,6} > 109 ; > 110 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 111 string _ = "NO"; > 112 END > 113 /* > 114 CASE(6) > 115 int seq_[] = ; > 116 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 117 string _ = ; > 118 END > 119 CASE(7) > 120 int seq_[] = ; > 121 vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_)); > 122 string _ = ; > 123 END > 124 */ > 125 } > 126 // END CUT HERE
Added SRM/498-U/1B.cpp version [762d28b66486ec7d]
> 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 = 1000000009; // op/ depends on primarity of the MODVAL > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(LL x):val(x%MODVAL) {} > 29 }; > 30 > 31 mint operator+(mint x, mint y) { return x.val+y.val; } > 32 mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; } > 33 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } > 34 mint POW(mint x, int e) { > 35 mint v = 1; > 36 for(;e;x=x*x,e>>=1) > 37 if(e&1) > 38 v=v*x; > 39 return v; > 40 } > 41 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } > 42 > 43 vector<mint> FAC_(1,1); > 44 void FAC_INIT(int n) { for(int i=1; i<=n; ++i) FAC_.push_back( FAC_.back()*i ); > 45 mint FAC(mint x) { return FAC_[x.val]; } > 46 mint C(mint n, mint k) { return k.val<0 || n.val<k.val ? 0 : FAC(n) / (FAC(k) * > 47 > 48 class FoxStones { public: > 49 int getCount(int W, int H, vector <int> sx, vector <int> sy) > 50 { > 51 if(FAC_.size()==1) > 52 FAC_INIT(200*200+1); > 53 > 54 map<vector<int>,int> dd; > 55 for(int y=0; y<H; ++y) > 56 for(int x=0; x<W; ++x) > 57 { > 58 vector<int> dis; > 59 for(int i=0; i<sx.size(); ++i) > 60 { > 61 int d = max(abs(sy[i]-1-y), abs(sx[i]-1- > 62 dis.push_back(d); > 63 } > 64 dd[dis]++; > 65 } > 66 mint ans = 1; > 67 for(map<vector<int>,int>::iterator it=dd.begin(); it!=dd.end(); > 68 { > 69 int n = it->second; > 70 ans = ans * FAC(n); > 71 } > 72 return ans.val; > 73 } > 74 }; > 75 > 76 // BEGIN CUT HERE > 77 #include <ctime> > 78 double start_time; string timer() > 79 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 80 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 81 { os << "{ "; > 82 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 83 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 84 void verify_case(const int& Expected, const int& Received) { > 85 bool ok = (Expected == Received); > 86 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 87 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 88 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 89 #define END verify_case(_, FoxStones().getCount(N, M, sx, sy));} > 90 int main(){ > 91 > 92 CASE(0) > 93 int N = 6; > 94 int M = 1; > 95 int sx_[] = {3}; > 96 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 97 int sy_[] = {1}; > 98 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 99 int _ = 4; > 100 END > 101 CASE(1) > 102 int N = 2; > 103 int M = 2; > 104 int sx_[] = {2}; > 105 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 106 int sy_[] = {1}; > 107 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 108 int _ = 6; > 109 END > 110 CASE(2) > 111 int N = 3; > 112 int M = 3; > 113 int sx_[] = {1,2,3}; > 114 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 115 int sy_[] = {1,2,3}; > 116 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 117 int _ = 8; > 118 END > 119 CASE(3) > 120 int N = 12; > 121 int M = 34; > 122 int sx_[] = {5,6,7,8,9,10}; > 123 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 124 int sy_[] = {11,12,13,14,15,16}; > 125 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 126 int _ = 410850247; > 127 END > 128 /* > 129 CASE(4) > 130 int N = ; > 131 int M = ; > 132 int sx_[] = ; > 133 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 134 int sy_[] = ; > 135 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 136 int _ = ; > 137 END > 138 CASE(5) > 139 int N = ; > 140 int M = ; > 141 int sx_[] = ; > 142 vector <int> sx(sx_, sx_+sizeof(sx_)/sizeof(*sx_)); > 143 int sy_[] = ; > 144 vector <int> sy(sy_, sy_+sizeof(sy_)/sizeof(*sy_)); > 145 int _ = ; > 146 END > 147 */ > 148 } > 149 // END CUT HERE
Added SRM/498-U/2C.cpp version [12f642c106b57412]
> 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 NinePuzzle { public: > 23 int getMinimumCost(string init, string goal) > 24 { > 25 multiset<char> s; > 26 for(int i=0; i<init.size(); ++i) > 27 s.insert( init[i] ); > 28 int cnt = 0; > 29 for(int i=0; i<goal.size(); ++i) > 30 if( s.count(goal[i]) ) > 31 s.erase( s.find(goal[i]) ); > 32 else > 33 ++cnt; > 34 return cnt; > 35 } > 36 }; > 37 > 38 // BEGIN CUT HERE > 39 #include <ctime> > 40 double start_time; string timer() > 41 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 42 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 43 { os << "{ "; > 44 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 45 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 46 void verify_case(const int& Expected, const int& Received) { > 47 bool ok = (Expected == Received); > 48 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 49 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 50 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 51 #define END verify_case(_, NinePuzzle().getMinimumCost(init, goal));} > 52 int main(){ > 53 > 54 CASE(0) > 55 string init = "BG*YRGRRYR" ; > 56 string goal = "BGGY*YRRRR" ; > 57 int _ = 0; > 58 END > 59 CASE(1) > 60 string init = "GBBB*BGBBG" ; > 61 string goal = "RYYY*YRYYR"; > 62 int _ = 9; > 63 END > 64 CASE(2) > 65 string init = "RRBR*BRBBB" ; > 66 string goal = "BBRB*RBRRR" ; > 67 int _ = 1; > 68 END > 69 /* > 70 CASE(3) > 71 string init = ; > 72 string goal = ; > 73 int _ = ; > 74 END > 75 CASE(4) > 76 string init = ; > 77 string goal = ; > 78 int _ = ; > 79 END > 80 */ > 81 } > 82 // END CUT HERE