Overview
| SHA1 Hash: | 4cc63e9faa159cf38070af912853497d2c42497c |
|---|---|
| Date: | 2012-10-11 12:09:13 |
| User: | kinaba |
| Comment: | 557 |
| 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
Modified CheckList.pptx from [e9052e045d34dbe0] to [80509898d6857d5c].
cannot compute difference between binary files
Added SRM/557-U/1A.cpp version [51b78e2d0929a6eb]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class FoxAndMountainEasy { public: > 23 string possible(int n, int h0, int hn, string history) > 24 { > 25 int z = 0; > 26 int min_z = 0; > 27 for(int i=0; i<history.size(); ++i) { > 28 z += (history[i]=='U' ? +1 : -1); > 29 min_z = min(z, min_z); > 30 } > 31 > 32 for(int x=0; x+history.size()<=n; ++x) > 33 { > 34 int hx = h0 + x; > 35 if(hx+min_z < 0) > 36 continue; > 37 int hy = hx + z; > 38 if( possible(hn-hy, n-(x+history.size())) ) > 39 return "YES"; > 40 } > 41 return "NO"; > 42 } > 43 > 44 bool possible(int dh, int k) > 45 { > 46 if((k+dh)%2 != 0) > 47 return false; > 48 int u = (k+dh)/2; > 49 int d = k - u; > 50 return 0<=u && u<=k && u+d==k && u-d==dh; > 51 } > 52 }; > 53 > 54 // BEGIN CUT HERE > 55 #include <ctime> > 56 double start_time; string timer() > 57 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 58 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 59 { os << "{ "; > 60 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 61 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 62 void verify_case(const string& Expected, const string& Received) { > 63 bool ok = (Expected == Received); > 64 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 65 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 66 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 67 #define END verify_case(_, FoxAndMountainEasy().possible(n, h0, hn, history > 68 int main(){ > 69 > 70 CASE(0) > 71 int n = 4; > 72 int h0 = 0; > 73 int hn = 4; > 74 string history = "UU"; > 75 string _ = "YES"; > 76 END > 77 CASE(1) > 78 int n = 4; > 79 int h0 = 0; > 80 int hn = 4; > 81 string history = "D"; > 82 string _ = "NO"; > 83 END > 84 CASE(2) > 85 int n = 4; > 86 int h0 = 100000; > 87 int hn = 100000; > 88 string history = "DDU"; > 89 string _ = "YES"; > 90 END > 91 CASE(3) > 92 int n = 4; > 93 int h0 = 0; > 94 int hn = 0; > 95 string history = "DDU"; > 96 string _ = "NO"; > 97 END > 98 CASE(4) > 99 int n = 20; > 100 int h0 = 20; > 101 int hn = 20; > 102 string history = "UDUDUDUDUD"; > 103 string _ = "YES"; > 104 END > 105 CASE(5) > 106 int n = 20; > 107 int h0 = 0; > 108 int hn = 0; > 109 string history = "UUUUUUUUUU"; > 110 string _ = "YES"; > 111 END > 112 CASE(6) > 113 int n = 20; > 114 int h0 = 0; > 115 int hn = 0; > 116 string history = "UUUUUUUUUUU"; > 117 string _ = "NO"; > 118 END > 119 CASE(7) > 120 int n = 4; > 121 int h0 = 3; > 122 int hn = 1; > 123 string history = "U"; > 124 string _ = "YES"; > 125 END > 126 CASE(8) > 127 int n = 1; > 128 int h0 = 0; > 129 int hn = 1; > 130 string history = "U"; > 131 string _ = "YES"; > 132 END > 133 CASE(8) > 134 int n = 2; > 135 int h0 = 0; > 136 int hn = 0; > 137 string history = "DU"; > 138 string _ = "NO"; > 139 END > 140 } > 141 // END CUT HERE
Added SRM/557-U/1B.cpp version [4ecece454e78d448]
> 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 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 typedef int vert; > 23 typedef vert edge; > 24 typedef vector<edge> edges; > 25 typedef vector<edges> graph; > 26 > 27 bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] ) > 28 { > 29 for(int i=0; i<G[v].size(); ++i) { > 30 vert u = G[v][i]; > 31 if( visited[u] ) continue; > 32 visited[u] = true; > 33 > 34 if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) ) > 35 { matchTo[v]=u, matchTo[u]=v; return true; } > 36 } > 37 return false; > 38 } > 39 > 40 template<int NV> > 41 int biMatch( graph& G, int L ) // [0,L):left, [L,?):right > 42 // only left->right edges are used during computation > 43 { > 44 vector<vert> matchTo(G.size(), -1); > 45 int ans = 0; > 46 for(vert v=0; v<L; ++v) { > 47 bool visited[NV] = {}; > 48 if( augment(G, v, matchTo, visited) ) > 49 ++ans; > 50 } > 51 return ans; > 52 } > 53 > 54 class Incubator { public: > 55 int maxMagicalGirls(vector <string> love) > 56 { > 57 const int N = love.size(); > 58 vector< vector<int> > protects(N, vector<int>(N, false)); > 59 for(int i=0; i<N; ++i) > 60 for(int j=0; j<N; ++j) > 61 protects[i][j] = (love[i][j] == 'Y'); > 62 for(int k=0; k<N; ++k) > 63 for(int i=0; i<N; ++i) > 64 for(int j=0; j<N; ++j) > 65 protects[i][j] |= protects[i][k] & protects[k][j]; > 66 > 67 int cand = N; > 68 > 69 graph G(N*2); > 70 for(int i=0; i<N; ++i) > 71 if(protects[i][i]) { > 72 --cand; > 73 } else { > 74 for(int j=0; j<N; ++j) > 75 if(protects[i][j] && !protects[j][j]) > 76 G[i].push_back(N+j); > 77 } > 78 > 79 return cand - biMatch<512>(G, N); > 80 } > 81 }; > 82 > 83 // BEGIN CUT HERE > 84 #include <ctime> > 85 double start_time; string timer() > 86 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 87 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 88 { os << "{ "; > 89 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 90 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 91 void verify_case(const int& Expected, const int& Received) { > 92 bool ok = (Expected == Received); > 93 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 94 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 95 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 96 #define END verify_case(_, Incubator().maxMagicalGirls(love));} > 97 int main(){ > 98 > 99 CASE(0) > 100 string love_[] = {"NY","NN"}; > 101 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 102 int _ = 1; > 103 END > 104 CASE(1) > 105 string love_[] = {"NYN", "NNY", "NNN"}; > 106 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 107 int _ = 1; > 108 END > 109 CASE(2) > 110 string love_[] = {"NNYNN","NNYNN","NNNYY","NNNNN","NNNNN"}; > 111 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 112 int _ = 2; > 113 END > 114 CASE(3) > 115 string love_[] = {"NNNNN","NYNNN","NYNYN","YNYNN","NNNNN"}; > 116 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 117 int _ = 2; > 118 END > 119 CASE(4) > 120 string love_[] = {"NNNNN","NNNNN","NNNNN","NNNNN","NNNNN"}; > 121 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 122 int _ = 5; > 123 END > 124 CASE(5) > 125 string love_[] = {"NNYNNNNN","NNNYNNNN","NNNNYNNN","NNYNNNNN","NNNNNYYN" > 126 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 127 int _ = 2; > 128 END > 129 CASE(6) > 130 string love_[] = {"Y"}; > 131 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 132 int _ = 0; > 133 END > 134 CASE(7) > 135 string love_[] = {"NYNNN", "NNYNN", "NNYYY", "NNYYY", "NNYYY"}; > 136 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 137 int _ = 1; > 138 END > 139 CASE(8) > 140 string love_[] = {"NNYYYYY", "NNYYYYY", "NNNNNNN", "NNNYYYY", "NNNYYYY", "NNNYYY > 141 vector <string> love(love_, love_+sizeof(love_)/sizeof(*love_)); > 142 int _ = 2; > 143 END > 144 } > 145 // END CUT HERE