Overview
| SHA1 Hash: | fa7992ffc586d0b5cb1420a581577c155a617d66 |
|---|---|
| Date: | 2012-08-06 15:26:11 |
| User: | kinaba |
| Comment: | 550 done |
| 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
Deleted SRM/550-U/1A.cpp version [463196d9224d114a]
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 RotatingBot { public: 23 - int minArea(vector <int> moves) 24 - { 25 - if( moves.size() == 1 ) { 26 - int w = moves[0]+1; 27 - return w; 28 - } 29 - if( moves.size() == 2 ) { 30 - int w = moves[0]+1; 31 - int h = moves[1]+1; 32 - return w*h; 33 - } 34 - if( moves.size() == 3 ) { 35 - int w1 = moves[0]+1; 36 - int h = moves[1]+1; 37 - int w2 = moves[2]+1; 38 - return max(w1,w2)*h; 39 - } 40 - if( moves.size() == 4 ) { 41 - int w1 = moves[0]+1; 42 - int h1 = moves[1]+1; 43 - int w2 = moves[2]+1; 44 - int h2 = moves[3]+1; 45 - if( w1 > w2 ) 46 - return -1; 47 - if( w1 == w2 ) { 48 - if( h1 <= h2 ) 49 - return -1; 50 - else 51 - return w1*h1; 52 - } 53 - return w2*max(h1,h2); 54 - } 55 - 56 - int w1 = moves[0]+1; 57 - int h1 = moves[1]+1; 58 - int w2 = moves[2]+1; 59 - int h2 = moves[3]+1; 60 - if( w1 > w2 ) 61 - return -1; 62 - if( w1 == w2 ) { 63 - vector<int> rm = simulate(w1, h1, 0, 0); 64 - if( match(rm, moves) ) 65 - return w1*h1; 66 - else 67 - return -1; 68 - } else { 69 - if( h2<h1 ) 70 - return -1; 71 - vector<int> rm = simulate(w2, h2, w2-w1, h2-h1); 72 - if( match(rm, moves) ) 73 - return w2*h2; 74 - else 75 - return -1; 76 - } 77 - } 78 - 79 - vector<int> simulate(int w, int h, int x, int y) 80 - { 81 - vector<int> moves; 82 - vector< vector<bool> > vis(h, vector<bool>(w)); 83 - int dx[]={+1,0,-1,0}; 84 - int dy[]={0,+1,0,-1}; 85 - int d = 0; 86 - vis[y][x] = true; 87 - for(;;) { 88 - int cnt = 0; 89 - for(;;) { 90 - int xx=x+dx[d]; 91 - int yy=y+dy[d]; 92 - if( yy<0||h<=yy||xx<0||w<=xx||vis[yy][xx] ) 93 - break; 94 - y=yy, x=xx; 95 - vis[y][x] = true; 96 - ++cnt; 97 - } 98 - d = (d+1)%4; 99 - if( cnt == 0 ) 100 - break; 101 - moves.push_back(cnt); 102 - } 103 - return moves; 104 - } 105 - 106 - bool match(const vector<int>& rm, const vector<int>& m) 107 - { 108 - if(rm.size() < m.size()) 109 - return false; 110 - for(int i=0; i+1<m.size(); ++i) 111 - if(rm[i] != m[i]) 112 - return false; 113 - return rm[m.size()-1] >= m[m.size()-1]; 114 - } 115 -}; 116 - 117 -// BEGIN CUT HERE 118 -#include <ctime> 119 -double start_time; string timer() 120 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 121 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 122 - { os << "{ "; 123 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 124 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 125 -void verify_case(const int& Expected, const int& Received) { 126 - bool ok = (Expected == Received); 127 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 128 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 129 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 130 -#define END verify_case(_, RotatingBot().minArea(moves));} 131 -int main(){ 132 - 133 -CASE(0) 134 - int moves_[] = {15}; 135 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 136 - int _ = 16; 137 -END 138 -CASE(1) 139 - int moves_[] = {3,10}; 140 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 141 - int _ = 44; 142 -END 143 -CASE(2) 144 - int moves_[] = {1,1,1,1}; 145 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 146 - int _ = -1; 147 -END 148 -CASE(3) 149 - int moves_[] = {9,5,11,10,11,4,10}; 150 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 151 - int _ = 132; 152 -END 153 -CASE(4) 154 - int moves_[] = {12,1,27,14,27,12,26,11,25,10,24,9,23,8,22,7,21,6,20,5,19,4,18,3,17,2,16,1,15}; 155 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 156 - int _ = 420; 157 -END 158 -CASE(5) 159 - int moves_[] = {8,6,6,1}; 160 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 161 - int _ = -1; 162 -END 163 -CASE(6) 164 - int moves_[] = {8,6,6}; 165 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 166 - int _ = 63; 167 -END 168 -CASE(7) 169 - int moves_[] = {5,4,5,3,3}; 170 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 171 - int _ = 30; 172 -END 173 -CASE(8) 174 -int moves_[] = {2,2,2,1}; 175 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 176 - int _ = 9; 177 -END 178 -/* 179 -CASE(9) 180 - int moves_[] = ; 181 - vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_)); 182 - int _ = ; 183 -END 184 -*/ 185 -} 186 -// END CUT HERE
Deleted SRM/550-U/1B.cpp version [5862d1075889b63d]
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 CheckerExpansion { public: 23 - vector <string> resultAfter(long long t, long long x0, long long y0, int w, int h) 24 - { 25 - vector<string> answer(h, string(w, '.')); 26 - for(int y_=0; y_<h; ++y_) 27 - for(int x_=0; x_<w; ++x_) { 28 - LL y = y0 + y_; 29 - LL x = x0 + x_; 30 - if( (y+x)%2==1 ) 31 - continue; 32 - LL N = (y+x)/2; 33 - if( t <= N ) 34 - continue; 35 - LL k = x-N; 36 - if( k<0 || N<k ) 37 - continue; 38 - if( is_comb_odd(N,k) ) 39 - answer[h-y_-1][x_] = (N%2==0 ? 'A' : 'B'); 40 - } 41 - return answer; 42 - } 43 - 44 - bool is_comb_odd(LL n, LL k) 45 - { 46 - for(LL m=1; m<=n; m<<=1) 47 - if( (k&m) && !(n&m) ) 48 - return false; 49 - return true; 50 - } 51 -}; 52 - 53 -// BEGIN CUT HERE 54 -#include <ctime> 55 -double start_time; string timer() 56 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 57 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 58 - { os << "{ "; 59 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 60 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 61 -void verify_case(const vector <string>& Expected, const vector <string>& Received) { 62 - bool ok = (Expected == Received); 63 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 64 - cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 65 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 66 -#define END verify_case(_, CheckerExpansion().resultAfter(t, x0, y0, w, h));} 67 -int main(){ 68 - 69 -CASE(0) 70 - long long t = 1LL; 71 - long long x0 = 0LL; 72 - long long y0 = 0LL; 73 - int w = 4; 74 - int h = 4; 75 - string __[] = {"....", "....", "....", "A..." }; 76 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 77 -END 78 -CASE(1) 79 - long long t = 5LL; 80 - long long x0 = 4LL; 81 - long long y0 = 1LL; 82 - int w = 3; 83 - int h = 4; 84 - string __[] = {"A..", "...", "B..", ".B." }; 85 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 86 -END 87 -CASE(2) 88 - long long t = 1024LL; 89 - long long x0 = 1525LL; 90 - long long y0 = 512LL; 91 - int w = 20; 92 - int h = 2; 93 - string __[] = {"B...B...B...........", ".B.A.B.A.B.........." }; 94 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 95 -END 96 -CASE(3) 97 - long long t = 53LL; 98 - long long x0 = 85LL; 99 - long long y0 = 6LL; 100 - int w = 5; 101 - int h = 14; 102 - string __[] = {".....", ".....", "B....", ".B.A.", ".....", ".....", ".....", ".....", ".....", ".....", "B....", ".B...", "..B..", ".A.B." }; 103 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 104 -END 105 -CASE(4) 106 - long long t = 1000000000000LL; 107 - long long x0 = 1000000000000LL; 108 - long long y0 = 123456789123LL; 109 - int w = 50; 110 - int h = 50; 111 - string __[] = {"?"}; 112 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 113 -END 114 -/* 115 -CASE(5) 116 - long long t = LL; 117 - long long x0 = LL; 118 - long long y0 = LL; 119 - int w = ; 120 - int h = ; 121 - string __[] = ; 122 - vector <string> _(__, __+sizeof(__)/sizeof(*__)); 123 -END 124 -*/ 125 -} 126 -// END CUT HERE
Deleted SRM/550-U/1C.cpp version [b366e6f6edd62cdd]
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 -static const int MODVAL = 1000000007; 23 -struct mint 24 -{ 25 - int val; 26 - mint():val(0){} 27 - mint(int x):val(x%MODVAL) {} 28 - mint(size_t x):val(x%MODVAL) {} 29 - mint(LL x):val(x%MODVAL) {} 30 -}; 31 -mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } 32 -mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } 33 -mint operator+(mint x, mint y) { return x+=y; } 34 -mint operator*(mint x, mint y) { return x*=y; } 35 - 36 -template<typename T> 37 -vector<T> MATMUL(const vector< vector<T> >& a, const vector<T>& v) 38 -{ 39 - int N = a.size(); 40 - vector<T> u(N); 41 - for(int i=0; i<N; ++i) 42 - for(int j=0; j<N; ++j) 43 - u[i] += a[i][j]*v[j]; 44 - return u; 45 -} 46 - 47 -template<typename T> 48 -vector< vector<T> > MATMUL(const vector< vector<T> >& a, const vector< vector<T> >& b) 49 -{ 50 - int N = a.size(); 51 - vector< vector<T> > c(N, vector<T>(N)); 52 - for(int i=0; i<N; ++i) 53 - for(int j=0; j<N; ++j) 54 - for(int k=0; k<N; ++k) 55 - c[i][j] += a[i][k]*b[k][j]; 56 - return c; 57 -} 58 - 59 -template<typename T> 60 -vector< vector<T> > MATPOW(vector< vector<T> > a, LL e) 61 -{ 62 - int N = a.size(); 63 - vector< vector<T> > c(N, vector<T>(N)); 64 - for(int i=0; i<N; ++i) c[i][i] = 1; 65 - for(; e; e>>=1) { 66 - if(e&1) 67 - c = MATMUL(c, a); 68 - a = MATMUL(a, a); 69 - } 70 - return c; 71 -} 72 - 73 -class ConversionMachine { public: 74 - int countAll(string word1, string word2, vector <int> costs, int maxCost) 75 - { 76 - int d[3] = {}; 77 - LL minCost = 0; 78 - for(int i=0; i<word1.size(); ++i) { 79 - int dd=0; 80 - while( word1[i] != word2[i] ) { 81 - dd += 1; 82 - minCost += costs[word1[i]-'a']; 83 - word1[i] = (word1[i]+1-'a')%3 + 'a'; 84 - } 85 - d[dd] += 1; 86 - } 87 - 88 - if( minCost > maxCost ) 89 - return 0; 90 - LL c3 = accumulate(costs.begin(), costs.end(), 0LL); 91 - return solve(d, (maxCost-minCost)/c3*3+d[1]*1+d[2]*2).val; 92 - } 93 - 94 - mint solve(int d[3], int rem) 95 - { 96 - int n = d[0]+d[1]+d[2]; 97 - 98 - map<pair<int,int>, int> enc; 99 - for(int b=0,id=0; b<=n; ++b) 100 - for(int c=0; b+c<=n; ++c,++id) 101 - enc[make_pair(b,c)] = id; 102 - int D = enc.size(); 103 - 104 - vector< vector<mint> > M(D+1, vector<mint>(D+1)); 105 - for(int b=0; b<=n; ++b) 106 - for(int c=0; b+c<=n; ++c) 107 - { 108 - int a = n-b-c; 109 - if(a) { 110 - M[enc[make_pair(b,c+1)]][enc[make_pair(b,c)]] = a; 111 - } 112 - if(b) { 113 - M[enc[make_pair(b-1,c)]][enc[make_pair(b,c)]] = b; 114 - if(b-1==0 && c==0) 115 - M.back()[enc[make_pair(b,c)]] = b; 116 - } 117 - if(c) { 118 - M[enc[make_pair(b+1,c-1)]][enc[make_pair(b,c)]] = c; 119 - } 120 - } 121 - M.back().back() = 1; 122 - 123 - vector<mint> V(D+1); 124 - V[enc[make_pair(d[1],d[2])]] = 1; 125 - V.back() = V[0]; 126 - 127 - return MATMUL(MATPOW(M, rem), V).back(); 128 - } 129 -}; 130 - 131 -// BEGIN CUT HERE 132 -#include <ctime> 133 -double start_time; string timer() 134 - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 135 -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 136 - { os << "{ "; 137 - for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 138 - os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 139 -void verify_case(const int& Expected, const int& Received) { 140 - bool ok = (Expected == Received); 141 - if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 142 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 143 -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 144 -#define END verify_case(_, ConversionMachine().countAll(word1, word2, costs, maxCost));} 145 -int main(){ 146 - 147 -CASE(0) 148 - string word1 = "a"; 149 - string word2 = "b"; 150 - int costs_[] = {100,2,3}; 151 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 152 - int maxCost = 205; 153 - int _ = 2; 154 -END 155 -CASE(1) 156 - string word1 = "abcba"; 157 - string word2 = "abcba"; 158 - int costs_[] = {67,23,43}; 159 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 160 - int maxCost = 0; 161 - int _ = 1; 162 -END 163 -CASE(2) 164 - string word1 = "cccccccc"; 165 - string word2 = "aaaaaaaa"; 166 - int costs_[] = {10000000,1,1}; 167 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 168 - int maxCost = 100; 169 - int _ = 40320; 170 -END 171 -CASE(3) 172 - string word1 = "aa"; 173 - string word2 = "cc"; 174 - int costs_[] = {1,10,100}; 175 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 176 - int maxCost = 1787; 177 - int _ = 123611681; 178 -END 179 -/* 180 -CASE(4) 181 - string word1 = ; 182 - string word2 = ; 183 - int costs_[] = ; 184 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 185 - int maxCost = ; 186 - int _ = ; 187 -END 188 -CASE(5) 189 - string word1 = ; 190 - string word2 = ; 191 - int costs_[] = ; 192 - vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); 193 - int maxCost = ; 194 - int _ = ; 195 -END 196 -*/ 197 -} 198 -// END CUT HERE
Name change from from SRM/550-U/1A.cpp to SRM/550/1A.cpp.
Name change from from SRM/550-U/1B.cpp to SRM/550/1B.cpp.
Name change from from SRM/550-U/1C.cpp to SRM/550/1C.cpp.