Overview
| SHA1 Hash: | b98fbebb355cbe68e1692d4b70c21989415c92cc |
|---|---|
| Date: | 2011-09-14 10:57:36 |
| User: | kinaba |
| Comment: | 517 |
| 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/517-U/1A.cpp version [64a4787ef91ae507]
> 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 CompositeSmash { public: > 23 string thePossible(int N, int target) > 24 { > 25 return avoid(N, target) ? "No" : "Yes"; > 26 } > 27 > 28 bool avoid(LL N, LL T) > 29 { > 30 if( N == T ) > 31 return false; > 32 if( N < T ) > 33 return true; > 34 bool composit = false; > 35 for(LL d=2; d*d<=N && d<N; ++d) > 36 if( N%d==0 ) { > 37 composit = true; > 38 if( avoid(d,T) && avoid(N/d,T) ) > 39 return true; > 40 } > 41 return !composit; > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const string& Expected, const string& Received) { > 54 bool ok = (Expected == Received); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, CompositeSmash().thePossible(N, target));} > 59 int main(){ > 60 > 61 CASE(0) > 62 int N = 517; > 63 int target = 47; > 64 string _ = "Yes"; > 65 END > 66 CASE(1) > 67 int N = 8; > 68 int target = 4; > 69 string _ = "Yes"; > 70 END > 71 CASE(2) > 72 int N = 12; > 73 int target = 6; > 74 string _ = "No"; > 75 END > 76 CASE(3) > 77 int N = 5; > 78 int target = 8; > 79 string _ = "No"; > 80 END > 81 CASE(4) > 82 int N = 100000; > 83 int target = 100000; > 84 string _ = "Yes"; > 85 END > 86 CASE(5) > 87 int N = 5858; > 88 int target = 2; > 89 string _ = "Yes"; > 90 END > 91 CASE(6) > 92 int N = 81461; > 93 int target = 2809; > 94 string _ = "No"; > 95 END > 96 CASE(7) > 97 int N = 65536; > 98 int target = 256; > 99 string _ = "No"; > 100 END > 101 /* > 102 CASE(8) > 103 int N = 72; > 104 int target = 4; > 105 string _ = "Yes"; > 106 END > 107 CASE(9) > 108 int N = ; > 109 int target = ; > 110 string _ = ; > 111 END > 112 */ > 113 } > 114 // END CUT HERE
Added SRM/517-U/1B.cpp version [498d0330a61d76ab]
> 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 LL MODVAL = 1000000007; > 23 class AdjacentSwaps { public: > 24 int theCount(vector <int> p) > 25 { > 26 int N = p.size(); > 27 > 28 vector< set<int> > child(N-1); > 29 for(int s=0; s<N; ++s) > 30 { > 31 int e = find(p.begin(), p.end(), s) - p.begin(); > 32 if( s < e ) { > 33 // s-1 <-- s --> s+1 --> ... --> e-1 <-- e > 34 if(s-1>=0) child[s].insert(s-1); > 35 for(int i=s; i+1<=e-1; ++i) child[i].insert(i+1) > 36 if(e<N-1) child[e].insert(e-1); > 37 } > 38 else if( s > e ) { > 39 // e-1 --> e <-- e+1 <-- ... <-- s-1 --> s > 40 if(e-1>=0) child[e-1].insert(e); > 41 for(int i=e; i+1<=s-1; ++i) child[i+1].insert(i) > 42 if(s<N-1) child[s-1].insert(s); > 43 } > 44 else // s == e > 45 return 0; > 46 } > 47 > 48 // cycle > 49 N--; > 50 for(int i=0; i+1<N; ++i) > 51 if( child[i].count(i+1) && child[i+1].count(i) ) > 52 return 0; > 53 > 54 vector<int> q(N-1); > 55 for(int i=0; i+1<N; ++i) { > 56 if( child[i].count(i+1) ) > 57 q[i] = +1; > 58 else > 59 q[i] = -1; > 60 } > 61 > 62 LL sum = 0; > 63 for(int i=0; i<N; ++i) > 64 sum += rec(q, 0, i, N-i-1); > 65 return int(sum % MODVAL); > 66 } > 67 > 68 map<pair<int,int>, LL> memo; > 69 LL rec(const vector<int>& q, int i, int x, int y) > 70 { > 71 if( i == q.size() ) > 72 return 1; > 73 pair<int,int> key(i,x); > 74 if( memo.count(key) ) > 75 return memo[key]; > 76 > 77 if( q[i] == -1 ) { > 78 LL sum = 0; > 79 for(int k=0; k<x; ++k) > 80 sum += rec(q, i+1, k, y+(x-k-1)); > 81 return memo[key] = sum % MODVAL; > 82 } else { > 83 LL sum = 0; > 84 for(int k=0; k<y; ++k) > 85 sum += rec(q, i+1, x+k, y-k-1); > 86 return memo[key] = sum % MODVAL; > 87 } > 88 } > 89 }; > 90 > 91 // BEGIN CUT HERE > 92 #include <ctime> > 93 double start_time; string timer() > 94 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 95 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 96 { os << "{ "; > 97 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 98 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 99 void verify_case(const int& Expected, const int& Received) { > 100 bool ok = (Expected == Received); > 101 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 102 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 103 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 104 #define END verify_case(_, AdjacentSwaps().theCount(p));} > 105 int main(){ > 106 > 107 CASE(0) > 108 int p_[] = {1, 2, 0}; > 109 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 110 int _ = 1; > 111 END > 112 CASE(1) > 113 int p_[] = {0, 1}; > 114 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 115 int _ = 0; > 116 END > 117 CASE(2) > 118 int p_[] = {2, 0, 3, 1}; > 119 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 120 int _ = 2; > 121 END > 122 CASE(3) > 123 int p_[] = {1, 0, 3, 2}; > 124 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 125 int _ = 0; > 126 END > 127 CASE(4) > 128 int p_[] = {1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15 > 129 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 130 int _ = 716743312; > 131 END > 132 /* > 133 CASE(5) > 134 int p_[] = ; > 135 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 136 int _ = ; > 137 END > 138 CASE(6) > 139 int p_[] = ; > 140 vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); > 141 int _ = ; > 142 END > 143 */ > 144 } > 145 // END CUT HERE
Added SRM/517-U/1C-U.cpp version [e962c41de1c7ae6b]
> 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 ColorfulBoard { public: > 23 int theMin(vector <string> board) > 24 { > 25 int H = board.size(); > 26 int W = board[0].size(); > 27 > 28 vector<bool> okY(H), okX(W); > 29 for(bool changed=true; changed; ) > 30 { > 31 changed = false; > 32 for(int y=0; y<H; ++y) if(!okY[y]) > 33 { > 34 set<char> cc(board[y].begin(), board[y].end()); > 35 cc.erase('*'); > 36 if( cc.size() == 1 ) { > 37 okY[y] = changed = true; > 38 for(int x=0; x<W; ++x) > 39 board[y][x] = '*'; > 40 } > 41 } > 42 for(int x=0; x<W; ++x) if(!okX[x]) > 43 { > 44 set<char> cc; > 45 for(int y=0; y<H; ++y) > 46 cc.insert(board[y][x]); > 47 cc.erase('*'); > 48 if( cc.size() == 1 ) { > 49 okX[x] = changed = true; > 50 for(int y=0; y<H; ++y) > 51 board[y][x] = '*'; > 52 } > 53 } > 54 } > 55 > 56 int okys = 0; > 57 for(int y=0; y<H; ++y) > 58 if( okY[y] ) > 59 okys++; > 60 int okxs = 0; > 61 for(int x=0; x<W; ++x) > 62 if( okX[x] ) > 63 okxs++; > 64 if( okxs!=W && okys!=H ) > 65 return -1; > 66 if( okxs!=W ) > 67 return okys; > 68 if( okys!=H ) > 69 return okxs; > 70 return min(okxs, okys); > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const int& Expected, const int& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, ColorfulBoard().theMin(board));} > 88 int main(){ > 89 > 90 CASE(0) > 91 string board_[] = {"SSS", > 92 "SRR", > 93 "SMM"}; > 94 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 95 int _ = 4; > 96 END > 97 CASE(1) > 98 string board_[] = {"BBBBBBBB", > 99 "BBBBBBBB", > 100 "BBBBBBBB", > 101 "BBBBBBBB", > 102 "BBBBBBBB"}; > 103 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 104 int _ = 5; > 105 END > 106 CASE(2) > 107 string board_[] = {"Ab", > 108 "bA"}; > 109 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 110 int _ = -1; > 111 END > 112 CASE(3) > 113 string board_[] = {"iiiii", > 114 "iwiwi"} > 115 ; > 116 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 117 int _ = 4; > 118 END > 119 CASE(4) > 120 string board_[] = {"ffffffffff", > 121 "xfxxoofoxo", > 122 "ffffffffff", > 123 "xfxxoofoxo", > 124 "ffffffffff", > 125 "ooxxoofoxo", > 126 "xfxxoofoxo", > 127 "xfxxoxfxxo", > 128 "ffxxofffxo", > 129 "xfxxoxfxxo"}; > 130 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 131 int _ = 17; > 132 END > 133 /* > 134 CASE(5) > 135 string board_[] = ; > 136 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 137 int _ = ; > 138 END > 139 CASE(6) > 140 string board_[] = ; > 141 vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_)); > 142 int _ = ; > 143 END > 144 */ > 145 } > 146 // END CUT HERE