Overview
| SHA1 Hash: | 76db68d6341a07dcfd40826b81e032c0069fddd3 |
|---|---|
| Date: | 2018-07-28 17:47:09 |
| User: | kinaba |
| Comment: | TCO18R3B & 4 |
| 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/TCO18-3B-U/1A.cpp version [51d9cbf8cbd55630]
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 <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class SquareCutout { public: 23 + int verify(vector <string> cutout) 24 + { 25 + const int Y = cutout.size(), X = cutout[0].size(); 26 + 27 + bool has_black = false; 28 + for (int y = 0; y < Y; ++y) 29 + for (int x = 0; x < X; ++x) 30 + if (cutout[y][x] == '#') 31 + has_black = true; 32 + if (!has_black) 33 + return 1; 34 + 35 + int ym = Y, xm = X, yM = 0, xM = 0; 36 + for (int y = 0; y < Y; ++y) 37 + for (int x = 0; x < X; ++x) 38 + if (cutout[y][x] == '#') 39 + ym = min(ym, y), yM = max(yM, y), xm = min(xm, x), xM = max(xM, x); 40 + 41 + for (int y = ym; y <= yM; ++y) 42 + for (int x = xm; x <= xM; ++x) 43 + if (cutout[y][x] != '#') 44 + return 0; 45 + 46 + bool x_extendable = (xm == 0 || xM == X - 1); 47 + bool y_extendable = (ym == 0 || yM == Y - 1); 48 + int yy = yM - ym + 1; 49 + int xx = xM - xm + 1; 50 + if (yy == xx) 51 + return yy; 52 + if (yy < xx) 53 + return y_extendable ? xx : 0; 54 + return x_extendable ? yy : 0; 55 + } 56 +}; 57 + 58 +// BEGIN CUT HERE 59 +#include <ctime> 60 +double start_time; string timer() 61 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 62 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 63 + { os << "{ "; 64 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 65 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 66 +void verify_case(const int& Expected, const int& Received) { 67 + bool ok = (Expected == Received); 68 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 69 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 70 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 71 +#define END verify_case(_, SquareCutout().verify(cutout));} 72 +int main(){ 73 + 74 +CASE(0) 75 + string cutout_[] = {".....", 76 + "..##.", 77 + "..##.", 78 + ".....", 79 + "....."}; 80 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 81 + int _ = 2; 82 +END 83 +CASE(1) 84 + string cutout_[] = {"...", 85 + "..."}; 86 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 87 + int _ = 1; 88 +END 89 +CASE(2) 90 + string cutout_[] = {".....", 91 + ".###.", 92 + ".#.#.", 93 + ".###.", 94 + "....."}; 95 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 96 + int _ = 0; 97 +END 98 +CASE(3) 99 + string cutout_[] = {"..####", 100 + "..####", 101 + "......"}; 102 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 103 + int _ = 4; 104 +END 105 +CASE(4) 106 + string cutout_[] = {"..#..", 107 + ".###.", 108 + "#####", 109 + ".###.", 110 + "..#.."}; 111 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 112 + int _ = 0; 113 +END 114 +CASE(5) 115 +string cutout_[] = { "...", "...", "..." }; 116 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 117 + int _ = 1; 118 +END 119 +/* 120 +CASE(6) 121 + string cutout_[] = ; 122 + vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_)); 123 + int _ = ; 124 +END 125 +*/ 126 +} 127 +// END CUT HERE
Added SRM/TCO18-3B-U/1B.cpp version [48b50023e1108913]
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 <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class TestProctoring { public: 23 + double expectedTime(vector <int> p, vector <int> q) 24 + { 25 + const int N = p.size(); 26 + vector<double> dp(1<<N), dp2((N+1)*(1<<N)); 27 + for (int mask = 1; mask < (1<<N); ++mask) { 28 + for (int i = N; i >= 0; --i) 29 + if (i == N) 30 + dp2[(i << N) | mask] = dp[mask]; 31 + else if ((mask&(1 << i)) == 0) 32 + dp2[(i << N) | mask] = dp2[((i + 1) << N) | mask]; 33 + else { 34 + double e1 = dp2[((i + 1) << N) | mask &~(1 << i)]; 35 + double e2 = dp2[((i + 1) << N) | mask]; 36 + dp2[(i << N) | mask] = (p[i] * e1 + (q[i] - p[i])*e2) / q[i]; 37 + } 38 + 39 + double pp = 1.0; 40 + for (int i = 0; i<N; ++i) if (mask&(1 << i)) 41 + pp = pp * (q[i] - p[i]) / q[i]; 42 + dp[mask] = (dp2[mask]+1) / (1 - pp); 43 + 44 + // Rerun 45 + for (int i = N; i >= 0; --i) 46 + if (i == N) 47 + dp2[(i << N) | mask] = dp[mask]; 48 + else if ((mask&(1 << i)) == 0) 49 + dp2[(i << N) | mask] = dp2[((i + 1) << N) | mask]; 50 + else { 51 + double e1 = dp2[((i + 1) << N) | mask &~(1 << i)]; 52 + double e2 = dp2[((i + 1) << N) | mask]; 53 + dp2[(i << N) | mask] = (p[i] * e1 + (q[i] - p[i])*e2) / q[i]; 54 + } 55 + } 56 + 57 + return dp[(1<<N) - 1]; 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) << " msec)"; return os.str(); } 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 os; } 69 +void verify_case(const double& Expected, const double& Received) { 70 + bool ok = (abs(Expected - Received)/abs(Expected) < 1e-6); 71 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 72 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 73 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 74 +#define END verify_case(_, TestProctoring().expectedTime(p, q));} 75 +int main(){ 76 +CASE(0) 77 + int p_[] = {2}; 78 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 79 + int q_[] = {4}; 80 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 81 + double _ = 2.0; 82 +END 83 +CASE(1) 84 + int p_[] = {1,2}; 85 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 86 + int q_[] = {2,4}; 87 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 88 + double _ = 2.6666666666666665; 89 +END 90 +CASE(2) 91 + int p_[] = {3,1,2,4,2,5}; 92 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 93 + int q_[] = {3,1,2,4,2,5}; 94 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 95 + double _ = 1.0; 96 +END 97 +CASE(3) 98 + int p_[] = {1,1,1,1,1,1,1,1}; 99 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 100 + int q_[] = {1,2,3,4,5,6,7,8}; 101 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 102 + double _ = 13.604834665120991; 103 +END 104 +CASE(4) 105 + int p_[] = {2,3,5,7,11,13,17}; 106 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 107 + int q_[] = {3,5,7,11,13,17,19}; 108 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 109 + double _ = 2.6299445065924276; 110 +END 111 +CASE(5) 112 + int p_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; 113 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 114 + int q_[] = {1000000000,1000000000,1000000000,1000000000,1000000000, 115 +1000000000,1000000000,1000000000,1000000000,1000000000, 116 +1000000000,1000000000,1000000000,1000000000,1000000000, 117 +1000000000,1000000000,1000000000,1000000000,1000000000}; 118 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 119 + double _ = 3.597740924491638E9; 120 +END 121 +/* 122 +CASE(6) 123 + int p_[] = ; 124 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 125 + int q_[] = ; 126 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 127 + double _ = ; 128 +END 129 +CASE(7) 130 + int p_[] = ; 131 + vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_)); 132 + int q_[] = ; 133 + vector <int> q(q_, q_+sizeof(q_)/sizeof(*q_)); 134 + double _ = ; 135 +END 136 +*/ 137 +} 138 +// END CUT HERE
Added SRM/TCO18-4-U/1A.cpp version [80f635d2b3ec8a20]
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 <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +static const unsigned MODVAL = 1000000007; 23 + 24 +template<typename T> 25 +struct DP2 26 +{ 27 + const int N1, N2; 28 + vector<T> data; 29 + DP2(int N1, int N2, const T& t = T()) 30 + : N1(N1), N2(N2), data(N1*N2, t) { 31 + assert(data.size() * sizeof(T)<(1 << 28)); 32 + } 33 + T& operator()(int i1, int i2) 34 + { 35 + return data[(i1*N2) + i2]; 36 + } 37 + void swap(DP2& rhs) 38 + { 39 + data.swap(rhs.data); 40 + } 41 +}; 42 + 43 +class SumPyramid { public: 44 + int countPyramids(int levels, int top) 45 + { 46 + vector<int> C(1, 1); 47 + for (int _ = 1; _ < levels; ++_) { 48 + vector<int> CC(C.size() + 1); 49 + for (size_t i = 0; i < CC.size(); ++i) 50 + CC[i] = min(top + 1, (i ? C[i - 1] : 0) + (i<C.size() ? C[i] : 0)); 51 + C = CC; 52 + } 53 + 54 + DP2<int> memo(levels, top+1, -1); 55 + return rec(levels - 1, 0, top, C, memo); 56 + } 57 + 58 + int rec(int n, int k, int sum, const vector<int>& C, DP2<int>& memo) 59 + { 60 + // #{x,y,..,z} where nCk x + nC{k+1} y + ... + nCn z == sum 61 + if (memo(k, sum) != -1) 62 + return memo(k, sum); 63 + 64 + if (k == n) 65 + return memo(k, sum) = 1; 66 + int ans = 0; 67 + for (int v = 0; v*C[k] <= sum; ++v) 68 + ans = (ans + rec(n, k+1, sum - v*C[k], C, memo)) % MODVAL; 69 + return memo(k, sum) = ans; 70 + } 71 +}; 72 + 73 +// BEGIN CUT HERE 74 +#include <ctime> 75 +double start_time; string timer() 76 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 77 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 78 + { os << "{ "; 79 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 80 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 81 +void verify_case(const int& Expected, const int& Received) { 82 + bool ok = (Expected == Received); 83 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 84 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 85 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 86 +#define END verify_case(_, SumPyramid().countPyramids(levels, top));} 87 +int main(){ 88 + 89 +CASE(0) 90 + int levels = 1; 91 + int top = 47; 92 + int _ = 1; 93 +END 94 +CASE(1) 95 + int levels = 2; 96 + int top = 10; 97 + int _ = 11; 98 +END 99 +CASE(2) 100 + int levels = 3; 101 + int top = 2; 102 + int _ = 4; 103 +END 104 +CASE(3) 105 + int levels = 5; 106 + int top = 7; 107 + int _ = 18; 108 +END 109 +CASE(4) 110 + int levels = 1000; 111 + int top = 1000; 112 + int _ = -1; 113 +END 114 +/* 115 +CASE(5) 116 + int levels = ; 117 + int top = ; 118 + int _ = ; 119 +END 120 +*/ 121 +} 122 +// END CUT HERE
Added SRM/TCO18-4-U/1B-U.cpp version [86534a42ab0996e3]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <unordered_map> 8 +#include <set> 9 +#include <algorithm> 10 +#include <numeric> 11 +#include <iterator> 12 +#include <functional> 13 +#include <complex> 14 +#include <queue> 15 +#include <stack> 16 +#include <cmath> 17 +#include <cassert> 18 +#include <tuple> 19 +using namespace std; 20 +typedef long long LL; 21 +typedef complex<double> CMP; 22 + 23 +class PolylineAreas { public: 24 + vector<long long> findAreas(string polyline) 25 + { 26 + string cmd; 27 + { 28 + const char* p = polyline.c_str(); 29 + while (*p) 30 + parse_one(p, cmd); 31 + } 32 + 33 + #define enc(x,y) ((LL(x+1000000)<<32)|(y+1000000)) 34 + const int dx[] = { 1, 0, -1, 0 }; 35 + const int dy[] = { 0, 1, 0, -1 }; 36 + 37 + unordered_map<LL, int> edge; 38 + { 39 + int x = 0, y = 0, d = 0; 40 + for (int ch : cmd) { 41 + switch (ch) { 42 + case 'F': { 43 + LL p = enc(x, y); 44 + x += dx[d]; 45 + y += dy[d]; 46 + LL c = enc(x, y); 47 + edge[p] |= 1 << d; 48 + edge[c] |= 1 << ((d + 2) % 4); 49 + 50 + break; 51 + } 52 + case 'L': d = (d + 1) % 4; break; 53 + case 'R': d = (d + 3) % 4; break; 54 + } 55 + } 56 + } 57 + 58 + vector<LL> ans; 59 + { 60 + for (auto pd : edge) { 61 + const int s_x = int(pd.first >> 32) - 1000000; 62 + const int s_y = int(pd.first & 0xffffffff) - 1000000; 63 + int& ds = pd.second; 64 + for (int d = 0; d < 4; ++d) if (ds&(1 << d)) { 65 + // go clockwise from (x,y) -> d 66 + 67 + LL area = 0; 68 + int x = s_x, y = s_y; 69 + do { 70 + //cerr << "(" << x << "," << y << "): " << d << endl; 71 + 72 + // move 73 + int px = x, py = y; 74 + x += dx[d]; 75 + y += dy[d]; 76 + edge[enc(px, py)] &= ~(1 << d); 77 + 78 + // turn 79 + int& dd = edge[enc(x, y)]; 80 + if (dd & (1 << ((d + 3) % 4))) 81 + d = (d + 3) % 4; 82 + else if (dd & (1 << d)) 83 + ; 84 + else if (dd & (1 << ((d + 1) % 4))) 85 + d = (d + 1) % 4; 86 + else if (dd & (1 << ((d + 2)%4))) 87 + d = (d + 2) % 4; 88 + else 89 + break; 90 + 91 + // calc area 92 + area += LL(x - s_x)*(py - s_y) - LL(px-s_x)*(y-s_y); 93 + //cerr << LL(x - s_x)*(py - s_y) - LL(px - s_x)*(y - s_y) << endl; 94 + } while (x != s_x || y != s_y); 95 + 96 + if(x==s_x && y==s_y && area > 0) 97 + ans.push_back(area/2); 98 + } 99 + } 100 + } 101 + 102 + sort(ans.begin(), ans.end()); 103 + if (ans.size() > 200) { 104 + vector<LL> a2(ans.begin(), ans.begin() + 100); 105 + a2.insert(a2.end(), ans.end() - 100, ans.end()); 106 + return a2; 107 + } 108 + return ans; 109 + } 110 + 111 + void parse_one(const char*& p, string& buf) { 112 + if ('0' <= *p && *p <= '9') { 113 + int rep = (*p++ - '0'); 114 + while('0' <= *p && *p <= '9') 115 + rep = rep*10 + (*p++ - '0'); 116 + 117 + string sub; 118 + parse_one(p, sub); 119 + while (rep-- > 0) 120 + buf += sub; 121 + } 122 + else if (*p == '[') { 123 + for (++p; *p != ']'; ) 124 + parse_one(p, buf); 125 + ++p; 126 + } 127 + else { 128 + buf += *p++; 129 + } 130 + } 131 +}; 132 + 133 +// BEGIN CUT HERE 134 +#include <ctime> 135 +double start_time; string timer() 136 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 137 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 138 + { os << "{ "; 139 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 140 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 141 +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) { 142 + bool ok = (Expected == Received); 143 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 144 + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } 145 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 146 +#define END verify_case(_, PolylineAreas().findAreas(polyline));} 147 +int main(){ 148 +CASE(0) 149 + string polyline = "FRFLF"; 150 + vector<long long> _; 151 +END 152 +CASE(1) 153 + string polyline = "4[100FR]"; 154 + long long __[] = {10000 }; 155 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 156 +END 157 +CASE(2) 158 + string polyline = "2[2[100FR]]"; 159 + long long __[] = {10000 }; 160 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 161 +END 162 +CASE(3) 163 + string polyline = "47[100FR]"; 164 + long long __[] = {10000 }; 165 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 166 +END 167 +CASE(4) 168 + string polyline = "1000000[]"; 169 + vector<long long> _; 170 +END 171 +CASE(5) 172 + string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL6F"; 173 + long long __[] = {1, 2, 2, 3, 3, 4, 6, 6, 9 }; 174 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 175 +END 176 +CASE(6) 177 + string polyline = "4[6FR]FR6FL2FL6FR3FRFR6FL2FL4F"; 178 + long long __[] = {1, 2, 2, 3, 3, 4, 6, 15 }; 179 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 180 +END 181 +CASE(7) 182 + string polyline = "3FRFRFLFLFRFR3FRFRFLFLFRF"; 183 + long long __[] = {7 }; 184 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 185 +END 186 +CASE(8) 187 + string polyline = "250000F"; 188 + long long __[] = {-1}; 189 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 190 +END 191 +/* 192 +CASE(9) 193 + string polyline = ; 194 + long long __[] = ; 195 + vector<long long> _(__, __+sizeof(__)/sizeof(*__)); 196 +END 197 +*/ 198 +} 199 +// END CUT HERE