Overview
| SHA1 Hash: | 3de32bb725c8a4bf2c16c02f7bb86d93ec9e97b6 |
|---|---|
| Date: | 2011-11-12 23:35:53 |
| User: | kinaba |
| Comment: | 523 |
| 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/523/1A.cpp version [e904c748ecdc6b47]
> 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 CountingSeries { public: > 23 long long countThem(long long a, long long b, long long c, long long d, > 24 { > 25 LL cnt = a<=upperBound ? (upperBound-a)/b+1 : 0; > 26 for(; c<=upperBound; c*=d) { > 27 if( !in_arith(a, b, c) ) > 28 ++cnt; > 29 if( d == 1 ) > 30 break; > 31 } > 32 return cnt; > 33 } > 34 > 35 bool in_arith(LL a, LL b, LL v) const > 36 { > 37 return v-a>=0 && (v-a)%b==0; > 38 } > 39 }; > 40 > 41 // BEGIN CUT HERE > 42 #include <ctime> > 43 double start_time; string timer() > 44 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 45 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 46 { os << "{ "; > 47 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 48 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 49 void verify_case(const long long& Expected, const long long& Received) { > 50 bool ok = (Expected == Received); > 51 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 52 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 53 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 54 #define END verify_case(_, CountingSeries().countThem(a, b, c, d, upperBoun > 55 int main(){ > 56 > 57 CASE(0) > 58 long long a = 1LL; > 59 long long b = 1LL; > 60 long long c = 1LL; > 61 long long d = 2LL; > 62 long long upperBound = 1000LL; > 63 long long _ = 1000LL; > 64 END > 65 CASE(1) > 66 long long a = 3LL; > 67 long long b = 3LL; > 68 long long c = 1LL; > 69 long long d = 2LL; > 70 long long upperBound = 1000LL; > 71 long long _ = 343LL; > 72 END > 73 CASE(2) > 74 long long a = 40LL; > 75 long long b = 77LL; > 76 long long c = 40LL; > 77 long long d = 100000LL; > 78 long long upperBound = 40LL; > 79 long long _ = 1LL; > 80 END > 81 CASE(3) > 82 long long a = 452LL; > 83 long long b = 24LL; > 84 long long c = 4LL; > 85 long long d = 5LL; > 86 long long upperBound = 600LL; > 87 long long _ = 10LL; > 88 END > 89 CASE(4) > 90 long long a = 234LL; > 91 long long b = 24LL; > 92 long long c = 377LL; > 93 long long d = 1LL; > 94 long long upperBound = 10000LL; > 95 long long _ = 408LL; > 96 END > 97 CASE(5) > 98 long long a = 8LL; > 99 long long b = 8LL; > 100 long long c = 2LL; > 101 long long d = 2LL; > 102 long long upperBound = 80LL; > 103 long long _ = 12LL; > 104 END > 105 CASE(6) > 106 long long a = 1LL; > 107 long long b = 12345LL; > 108 long long c = 1LL; > 109 long long d = 100000LL; > 110 long long upperBound = 1000000000000LL; > 111 long long _ = -1LL; > 112 END > 113 } > 114 // END CUT HERE
Added SRM/523/1B.cpp version [2ad7ecc836973d8a]
> 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 = 1000000007; > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} // x>=0 > 28 mint(size_t x):val(x%MODVAL) {} // x>=0 > 29 mint(LL x):val(x%MODVAL) {} // x>=0 > 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 class BricksN { public: > 37 int countStructures(int w, int h, int k) > 38 { > 39 memo1.clear(); > 40 memo2.clear(); > 41 return rec(w, h, k).val; > 42 } > 43 > 44 map<int,mint> memo1; > 45 mint rec(int w, int h, int k) > 46 { > 47 if( h == 0 ) return 1; > 48 if( w <= 0 ) return 1; > 49 > 50 const int key = w*51+h; > 51 if( memo1.count(key) ) > 52 return memo1[key]; > 53 > 54 mint sum = 1; > 55 for(int s=0; s<w; ++s) > 56 for(int ww=1; s+ww<=w; ++ww) > 57 sum += full(ww, k) * rec(ww, h-1, k) * rec(w-(s+ > 58 return memo1[key] = sum; > 59 } > 60 > 61 map<int,mint> memo2; > 62 mint full(int w, int k) > 63 { > 64 if( w <= 0 ) return 1; > 65 > 66 const int key = w; > 67 if( memo2.count(key) ) > 68 return memo2[key]; > 69 > 70 mint sum = 0; > 71 for(int ww=1; ww<=min(w,k); ++ww) > 72 sum += full(w-ww, k); > 73 return memo2[key] = sum; > 74 } > 75 }; > 76 > 77 // BEGIN CUT HERE > 78 #include <ctime> > 79 double start_time; string timer() > 80 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 81 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 82 { os << "{ "; > 83 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 84 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 85 void verify_case(const int& Expected, const int& Received) { > 86 bool ok = (Expected == Received); > 87 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 88 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 89 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 90 #define END verify_case(_, BricksN().countStructures(w, h, k));} > 91 int main(){ > 92 > 93 CASE(0) > 94 int w = 3; > 95 int h = 1; > 96 int k = 3; > 97 int _ = 13; > 98 END > 99 CASE(1) > 100 int w = 3; > 101 int h = 2; > 102 int k = 3; > 103 int _ = 83; > 104 END > 105 CASE(2) > 106 int w = 1; > 107 int h = 5; > 108 int k = 1; > 109 int _ = 6; > 110 END > 111 CASE(3) > 112 int w = 10; > 113 int h = 10; > 114 int k = 3; > 115 int _ = 288535435; > 116 END > 117 CASE(4) > 118 int w = 50; > 119 int h = 50; > 120 int k = 50; > 121 int _ = -1; > 122 END > 123 CASE(5) > 124 int w = 1; > 125 int h = 1; > 126 int k = 1; > 127 int _ = 1; > 128 END > 129 > 130 } > 131 // END CUT HERE
Added SRM/523/1C.cpp version [ac1374745693c058]
> 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 AlphabetPaths { public: > 29 int H, W; > 30 long long count(vector <string> maze) > 31 { > 32 H = maze.size(); > 33 W = maze[0].size(); > 34 for(int y=0; y<H; ++y) > 35 for(int x=0; x<W; ++x) > 36 if( maze[y][x] != '.' ) > 37 maze[y][x] = char(string("ABCDEFZHIKLMNOPQRSTVX" > 38 > 39 LL total = 0; > 40 for(int y=0; y<H; ++y) > 41 for(int x=0; x<W; ++x) > 42 if( maze[y][x] != '.' ) { > 43 int mid = maze[y][x]; > 44 > 45 unordered_map<int, int> reachable; > 46 travel(1, 1<<mid, y, x, maze, reachable); > 47 > 48 for(unordered_map<int,int>::iterator it=reachabl > 49 { > 50 unordered_map<int,int>::iterator kt = re > 51 if( kt != reachable.end() ) > 52 total += LL(it->second) * kt->se > 53 } > 54 } > 55 return total; > 56 } > 57 > 58 void travel(int n, int mask, int y, int x, const vector<string>& maze, > 59 unordered_map<int,int>& reachable) > 60 { > 61 if( n == 11 ) { > 62 reachable[mask]++; > 63 return; > 64 } > 65 > 66 static const int dy[] = {-1,+1,0,0}; > 67 static const int dx[] = {0,0,-1,+1}; > 68 for(int i=0; i<4; ++i) { > 69 int yy = y+dy[i]; > 70 int xx = x+dx[i]; > 71 if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='.' > 72 int v = maze[yy][xx]; > 73 if( !(mask & (1<<v)) ) > 74 travel(n+1, mask|(1<<v), yy, xx, maze, r > 75 } > 76 } > 77 } > 78 }; > 79 > 80 // BEGIN CUT HERE > 81 #include <ctime> > 82 double start_time; string timer() > 83 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 84 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 85 { os << "{ "; > 86 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 87 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 88 void verify_case(const long long& Expected, const long long& Received) { > 89 bool ok = (Expected == Received); > 90 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 91 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 92 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 93 #define END verify_case(_, AlphabetPaths().count(maze));} > 94 int main(){ > 95 > 96 CASE(0) > 97 string maze_[] = {"ABCDEFZHIXKLMNOPQRST", > 98 "...................V"}; > 99 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 100 long long _ = 2LL; > 101 END > 102 CASE(1) > 103 string maze_[] = {".................VT.", > 104 "....................", > 105 "ABCDEFZHIXKLMNOPQRS.", > 106 "..................S.", > 107 ".................VT."}; > 108 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 109 long long _ = 0LL; > 110 END > 111 CASE(2) > 112 string maze_[] = {"TBCDE.PQRSA", > 113 "FZHIXKLMNOV"}; > 114 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 115 long long _ = 50LL; > 116 END > 117 CASE(3) > 118 string maze_[] = {"ABCDEF.", > 119 "V....Z.", > 120 "T....H.", > 121 "S....I.", > 122 "R....X.", > 123 "KLMNOPQ"}; > 124 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 125 long long _ = 4LL; > 126 END > 127 CASE(4) > 128 string maze_[] = { > 129 "ABCDEFZHIXKLMNOPQRSTV", > 130 "HIXKLMNOPQRSTVABCDEFZ", > 131 "OPQRSTVABCDEFZHIXKLMN", > 132 "ABCDEFZHIXKLMNOPQRSTV", > 133 "HIXKLMNOPQRSTVABCDEFZ", > 134 "OPQRSTVABCDEFZHIXKLMN", > 135 "ABCDEFZHIXKLMNOPQRSTV", > 136 "HIXKLMNOPQRSTVABCDEFZ", > 137 "OPQRSTVABCDEFZHIXKLMN", > 138 "ABCDEFZHIXKLMNOPQRSTV", > 139 "HIXKLMNOPQRSTVABCDEFZ", > 140 "OPQRSTVABCDEFZHIXKLMN", > 141 "ABCDEFZHIXKLMNOPQRSTV", > 142 "HIXKLMNOPQRSTVABCDEFZ", > 143 "OPQRSTVABCDEFZHIXKLMN", > 144 "ABCDEFZHIXKLMNOPQRSTV", > 145 "HIXKLMNOPQRSTVABCDEFZ", > 146 "OPQRSTVABCDEFZHIXKLMN", > 147 "ABCDEFZHIXKLMNOPQRSTV", > 148 "HIXKLMNOPQRSTVABCDEFZ", > 149 "OPQRSTVABCDEFZHIXKLMN", > 150 }; > 151 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 152 long long _ = 6119782LL; > 153 END > 154 CASE(5) > 155 string maze_[] = {"ABCDEFZHIKLMNOPQRSTVX", "FZHIKLMNOPQRSTVXABCDE", "LMN > 156 vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); > 157 long long _ = 10530238LL; > 158 END > 159 } > 160 // END CUT HERE
Modified TZTesterSp/template.cpp from [0155d37d08046666] to [56e8b77f261a915b].
11 #include <functional> 11 #include <functional> 12 #include <complex> 12 #include <complex> 13 #include <queue> 13 #include <queue> 14 #include <stack> 14 #include <stack> 15 #include <cmath> 15 #include <cmath> 16 #include <cassert> 16 #include <cassert> 17 #include <cstring> 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 18 using namespace std; 24 using namespace std; 19 typedef long long LL; 25 typedef long long LL; 20 typedef complex<double> CMP; 26 typedef complex<double> CMP; 21 27 22 class $CLASSNAME$ { public: 28 class $CLASSNAME$ { public: 23 $RC$ $METHODNAME$($METHODPARMS$) 29 $RC$ $METHODNAME$($METHODPARMS$) 24 { 30 { 25 } 31 } 26 }; 32 }; 27 33 28 $TESTCODE$ 34 $TESTCODE$