Overview
| SHA1 Hash: | d796dcebe4dfb26255084a4a7d677f0040b94c16 |
|---|---|
| Date: | 2019-08-11 14:13:04 |
| User: | kinaba |
| Comment: | R4 |
| 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/TCO19-4-U/1A-U.cpp version [ed3910ded0d2a517]
> 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 ReProduct { public: > 23 long long minimize(vector <int> base, int goal) > 24 { > 25 vector<tuple<LL,int,int,int,int>> cand(1, make_tuple(0LL,-1,-1,- > 26 for (LL a = 1,ai=0; a <= 1000000000000000000LL; a *= 2,++ai) > 27 for (LL b = a,bi=0; b <= 1000000000000000000LL; b *= 3,+ > 28 for (LL c = b,ci=0; c <= 1000000000000000000LL; > 29 for (LL d = c,di=0; d <= 100000000000000 > 30 cand.emplace_back(d, ai,bi,ci,di > 31 > 32 vector<LL> vs; > 33 for (auto cc : cand) { > 34 LL c = get<0>(cc); > 35 LL v = value(c, base); > 36 if (v == goal) > 37 vs.push_back(c); > 38 if (v + 1 == goal) > 39 if (c == 0) > 40 vs.push_back(10); > 41 else if (c==1) > 42 vs.push_back(11); > 43 else { > 44 int p2 = get<1>(cc); > 45 int p3 = get<2>(cc); > 46 int p5 = get<3>(cc); > 47 int p7 = get<4>(cc); > 48 if (p2 + p3 + p5 + p7 >= 2) { > 49 vector<int> ds; > 50 for (int _ = 0; _ < p5; ++_) ds. > 51 for (int _ = 0; _ < p7; ++_) ds. > 52 if (ds.empty() && p2 + p3 == 2) > 53 for (int _ = 0; _ < p2; > 54 for (int _ = 0; _ < p3; > 55 } > 56 else if (ds.empty() && p2 == 3 & > 57 ds.push_back(2); > 58 ds.push_back(4); > 59 } > 60 else { > 61 for (; p2 >= 3; p2 -= 3) > 62 for (; p3 >= 2; p3 -= 2) > 63 if (p2 == 0) { > 64 if (p3 == 0) {} > 65 else if (p3 == 1 > 66 } > 67 else if (p2 == 1) { > 68 if (p3 == 0) { d > 69 else if (p3 == 1 > 70 } > 71 else if (p2 == 2) { > 72 if (p3 == 0) { d > 73 else if (p3 == 1 > 74 } > 75 } > 76 > 77 sort(ds.begin(), ds.end()); > 78 if (ds.size() <= 18) { > 79 LL u = 0; > 80 for (int d : ds) > 81 u = u * 10 + d; > 82 vs.push_back(u); > 83 } > 84 } > 85 } > 86 } > 87 return *min_element(vs.begin(), vs.end()); > 88 } > 89 > 90 int value(LL x, const vector<int>& base) { > 91 if (x <= 9) > 92 return base[int(x)]; > 93 > 94 LL p = 1; > 95 for (; x; x /= 10) > 96 p = p * (x % 10); > 97 return value(p, base) + 1; > 98 } > 99 }; > 100 > 101 // BEGIN CUT HERE > 102 #include <ctime> > 103 double start_time; string timer() > 104 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 105 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 106 { os << "{ "; > 107 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 108 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 109 void verify_case(const long long& Expected, const long long& Received) { > 110 bool ok = (Expected == Received); > 111 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 112 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 113 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 114 #define END verify_case(_, ReProduct().minimize(base, goal));} > 115 int main(){ > 116 CASE(0) > 117 int base_[] = {0,1,1,1,1,1,1,1,1,1}; > 118 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 119 int goal = 2; > 120 long long _ = 11LL; > 121 END > 122 CASE(1) > 123 int base_[] = {0,0,0,0,0,0,0,0,0,0}; > 124 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 125 int goal = 3; > 126 long long _ = 39LL; > 127 END > 128 CASE(2) > 129 int base_[] = {2,0,0,0,0,0,0,0,0,0}; > 130 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 131 int goal = 2; > 132 long long _ = 0LL; > 133 END > 134 CASE(3) > 135 int base_[] = {2,2,2,2,2,2,2,2,0,2}; > 136 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 137 int goal = 1; > 138 long long _ = 18LL; > 139 END > 140 CASE(4) > 141 int base_[] = {2,1,2,2,1,1,1,0,1,0}; > 142 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 143 int goal = 6; > 144 long long _ = 268LL; > 145 END > 146 CASE(5) > 147 int base_[] = { 2,1,2,2,1,1,1,0,1,0 }; > 148 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 149 int goal = 11; > 150 long long _ = -1LL; > 151 END > 152 /* > 153 CASE(6) > 154 int base_[] = ; > 155 vector <int> base(base_, base_+sizeof(base_)/sizeof(*base_)); > 156 int goal = ; > 157 long long _ = LL; > 158 END > 159 */ > 160 } > 161 // END CUT HERE
Added SRM/TCO19-4-U/1B-U.cpp version [f261b81b4a27fbad]
> 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 InsidePoints { public: > 23 vector <int> construct(vector <int> x, vector <int> y) > 24 { > 25 map<int, set<int>> x2y; > 26 for (int i = 0; i < x.size(); ++i) > 27 x2y[x[i]].insert(y[i]); > 28 > 29 vector<pair<int,int>> left; > 30 vector<pair<int, int>> upper; > 31 vector<pair<int, int>> lower; > 32 vector<pair<int, int>> right; > 33 > 34 int prevx = -99999999; > 35 int prevy = -99999999; > 36 for (auto it : x2y) { > 37 int x = it.first; > 38 set<int> ys = it.second; > 39 > 40 if (prevx == -99999999) { > 41 upper.emplace_back(x, *ys.rbegin() + 1); > 42 lower.emplace_back(x, *ys.begin() - 1); > 43 > 44 for (int yy = *ys.rbegin(); yy >= *ys.begin(); - > 45 left.emplace_back(ys.count(yy) ? x - 1 : > 46 } > 47 else { > 48 for (int xt = prevx + 1; xt < x; ++xt) { > 49 upper.emplace_back(xt, prevy+1); > 50 lower.emplace_back(xt, prevy); > 51 } > 52 upper.emplace_back(x, *ys.rbegin() + 1); > 53 int id = -1; > 54 for (int yy = *ys.rbegin(); yy >= *ys.begin(); - > 55 if (ys.count(yy) == 0) { > 56 lower.emplace_back(x, yy); > 57 lower.emplace_back(x-1, id--); > 58 } > 59 lower.emplace_back(x, *ys.begin() - 1); > 60 } > 61 > 62 if (x2y.rbegin()->first == x) { > 63 for (int yy = *ys.rbegin(); yy >= *ys.begin(); - > 64 right.emplace_back(ys.count(yy) ? x + 1 > 65 } > 66 > 67 prevx = x; > 68 prevy = *ys.rbegin(); > 69 } > 70 > 71 vector<pair<int,int>> ans; > 72 ans.insert(ans.end(), left.begin(), left.end()); > 73 ans.insert(ans.end(), lower.begin(), lower.end()); > 74 ans.insert(ans.end(), right.rbegin(), right.rend()); > 75 ans.insert(ans.end(), upper.rbegin(), upper.rend()); > 76 vector<int> flat_ans; > 77 for (auto xy : ans) { > 78 flat_ans.push_back(xy.first); > 79 flat_ans.push_back(xy.second); > 80 } > 81 return flat_ans; > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const vector <int>& Expected, const vector <int>& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, InsidePoints().construct(x, y));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int x_[] = {4}; > 103 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 104 int y_[] = {7}; > 105 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 106 int __[] = {3, 7, 4, 8, 5, 6 }; > 107 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 108 END > 109 CASE(1) > 110 int x_[] = {4, 6}; > 111 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 112 int y_[] = {7, 7}; > 113 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 114 int __[] = {3, 6, 7, 6, 7, 8, 5, 7, 3, 8 }; > 115 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 116 END > 117 CASE(2) > 118 int x_[] = {1, 1, 2, 2}; > 119 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 120 int y_[] = {1, 2, 1, 2}; > 121 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 122 int __[] = {0, 0, 3, 0, 3, 3, 0, 3 }; > 123 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 124 END > 125 CASE(3) > 126 int x_[] = {1, 2, 3, 3, 3, 3, 5, 4}; > 127 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 128 int y_[] = {3, 3, 1, 5, 2, 4, 3, 3}; > 129 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 130 int __[] = {0, 2, 2, 2, 2, 0, 4, 0, 4, 2, 6, 2, 6, 4, 4, 4, 4, 6, 2, 6, > 131 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 132 END > 133 /* > 134 CASE(4) > 135 int x_[] = ; > 136 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 137 int y_[] = ; > 138 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 139 int __[] = ; > 140 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 141 END > 142 CASE(5) > 143 int x_[] = ; > 144 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 145 int y_[] = ; > 146 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 147 int __[] = ; > 148 vector <int> _(__, __+sizeof(__)/sizeof(*__)); > 149 END > 150 */ > 151 } > 152 // END CUT HERE