Overview
| SHA1 Hash: | 01b4c419a6413e29e9ba671e73b7ca61dc035df6 |
|---|---|
| Date: | 2013-02-19 11:03:02 |
| User: | kinaba |
| Comment: | 570 |
| 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 [80509898d6857d5c] to [1f692893d744c87d].
cannot compute difference between binary files
Added SRM/570-U/1A.cpp version [735a19ded3f1e4b9]
> 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 RobotHerb { public: > 23 long long getdist(int T, vector <int> a) > 24 { > 25 static const LL dx[] = {+1,0,-1,0}; > 26 static const LL dy[] = {0,+1,0,-1}; > 27 > 28 LL x=0, y=0, d=0, xs[5]={}, ys[5]={}; > 29 for(int i=0; i<4; ++i) > 30 { > 31 for(int k=0; k<a.size(); ++k) > 32 { > 33 x += dx[d%4] * a[k]; > 34 y += dy[d%4] * a[k]; > 35 d += a[k]; > 36 } > 37 xs[i+1] = x; > 38 ys[i+1] = y; > 39 } > 40 x = (xs[4]-xs[0])*(T/4) + xs[T%4]; > 41 y = (ys[4]-ys[0])*(T/4) + ys[T%4]; > 42 return abs(x)+abs(y); > 43 } > 44 }; > 45 > 46 // BEGIN CUT HERE > 47 #include <ctime> > 48 double start_time; string timer() > 49 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 50 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 51 { os << "{ "; > 52 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 53 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 54 void verify_case(const long long& Expected, const long long& Received) { > 55 bool ok = (Expected == Received); > 56 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 57 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 58 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 59 #define END verify_case(_, RobotHerb().getdist(T, a));} > 60 int main(){ > 61 > 62 CASE(0) > 63 int T = 1; > 64 int a_[] = {1,2,3}; > 65 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 66 long long _ = 2LL; > 67 END > 68 CASE(1) > 69 int T = 100; > 70 int a_[] = {1}; > 71 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 72 long long _ = 0LL; > 73 END > 74 CASE(2) > 75 int T = 5; > 76 int a_[] = {1,1,2}; > 77 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 78 long long _ = 10LL; > 79 END > 80 CASE(3) > 81 int T = 1000000000; > 82 int a_[] = {100}; > 83 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 84 long long _ = 100000000000LL; > 85 END > 86 CASE(4) > 87 int T = 570; > 88 int a_[] = {2013,2,13,314,271,1414,1732}; > 89 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 90 long long _ = 4112LL; > 91 END > 92 /* > 93 CASE(5) > 94 int T = ; > 95 int a_[] = ; > 96 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 97 long long _ = LL; > 98 END > 99 CASE(6) > 100 int T = ; > 101 int a_[] = ; > 102 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 103 long long _ = LL; > 104 END > 105 */ > 106 } > 107 // END CUT HERE
Added SRM/570-U/1B.cpp version [16d4f478d9851855]
> 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 CentaurCompany { public: > 23 struct State { > 24 int nNode; > 25 vector< vector< vector<double> > > th; // nHumanNodes -> nEq -> > 26 vector< vector< vector<double> > > tk; // nHumanNodes -> nEq -> > 27 }; > 28 > 29 double getvalue(vector <int> a, vector <int> b) > 30 { > 31 int N = a.size() + 1; > 32 vector< vector<int> > G(N); > 33 for(int i=0; i<a.size(); ++i) { > 34 G[a[i]-1].push_back(b[i]-1); > 35 G[b[i]-1].push_back(a[i]-1); > 36 } > 37 > 38 double e = 0.0; > 39 State s = rec(-1, 0, G); > 40 for(int ah=0; ah<=s.nNode; ++ah) > 41 for(int ahe=0; ahe<=ah; ++ahe) > 42 for(int ake=0; ake<=(s.nNode-ah); ++ake) > 43 { > 44 int ak = s.nNode - ah; > 45 { > 46 double p = s.th[ah][ahe][ake]; > 47 e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0 > 48 } > 49 { > 50 double p = s.tk[ah][ahe][ake]; > 51 e += p * (max(2*(ahe-1)-ah,0)+max(2*(ake-1)-ak,0 > 52 } > 53 } > 54 return e; > 55 } > 56 > 57 State rec(int p, int v, const vector<vector<int> >& G) > 58 { > 59 State s = {1, > 60 vector< vector< vector<double> > >(2, vector< vector<dou > 61 vector< vector< vector<double> > >(2, vector< vector<dou > 62 }; > 63 s.th[1][1][0] = 0.5; > 64 s.tk[0][0][1] = 0.5; > 65 for(int i=0; i<G[v].size(); ++i) if(G[v][i] != p) > 66 s = combine(s, rec(v, G[v][i], G)); > 67 return s; > 68 } > 69 > 70 State combine(const State& a, const State& b) > 71 { > 72 int N = a.nNode + b.nNode; > 73 State s = {N, > 74 vector< vector< vector<double> > >(N+1, vector< vector<d > 75 vector< vector< vector<double> > >(N+1, vector< vector<d > 76 }; > 77 for(int ah=0; ah<=a.nNode; ++ah) > 78 for(int ahe=0; ahe<=ah; ++ahe) > 79 for(int ake=0; ake<=(a.nNode-ah); ++ake) > 80 for(int bh=0; bh<=b.nNode; ++bh) > 81 for(int bhe=0; bhe<=bh; ++bhe) > 82 for(int bke=0; bke<=(b.nNode-bh); ++bke) { > 83 if(ahe+bhe!=0) > 84 s.th[ah+bh][ahe+bhe-1][ake+bke] += a.th[ah][ahe][ake]*b. > 85 s.th[ah+bh][ahe+bhe][ake+bke] += a.th[ah][ahe][ake]*b.tk > 86 s.tk[ah+bh][ahe+bhe][ake+bke] += a.tk[ah][ahe][ake]*b.th > 87 if(ake+bke!=0) > 88 s.tk[ah+bh][ahe+bhe][ake+bke-1] += a.tk[ah][ahe][ake]*b. > 89 } > 90 return s; > 91 } > 92 }; > 93 > 94 // BEGIN CUT HERE > 95 #include <ctime> > 96 double start_time; string timer() > 97 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 98 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 99 { os << "{ "; > 100 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 101 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 102 void verify_case(const double& Expected, const double& Received) { > 103 bool ok = (abs(Expected - Received) < 1e-9); > 104 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 105 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 106 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 107 #define END verify_case(_, CentaurCompany().getvalue(a, b));} > 108 int main(){ > 109 > 110 CASE(0) > 111 int a_[] = {1}; > 112 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 113 int b_[] = {2}; > 114 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 115 double _ = 0.0; > 116 END > 117 CASE(1) > 118 int a_[] = {1,1,1}; > 119 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 120 int b_[] = {2,3,4}; > 121 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 122 double _ = 0.125; > 123 END > 124 CASE(2) > 125 int a_[] = {1,2,3,2,2}; > 126 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 127 int b_[] = {2,3,4,5,6}; > 128 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 129 double _ = 0.375; > 130 END > 131 CASE(3) > 132 int a_[] = {1,2,3,4,5,6,7,8,9}; > 133 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 134 int b_[] = {2,3,4,5,6,7,8,9,10}; > 135 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 136 double _ = 0.41796875; > 137 END > 138 CASE(4) > 139 int a_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, > 140 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 141 int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 > 142 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 143 double _ = 15.500000001076842; > 144 END > 145 CASE(5) > 146 int a_[] = {10, 7, 2, 5, 6, 2, 4, 9, 7}; > 147 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 148 int b_[] = {8, 10, 10, 4, 1, 6, 2, 2, 3}; > 149 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 150 double _ = 0.646484375; > 151 END > 152 CASE(6) > 153 int a_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23, > 154 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 155 int b_[] = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 > 156 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 157 double _ = -1; > 158 END > 159 /* > 160 CASE(7) > 161 int a_[] = ; > 162 vector <int> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 163 int b_[] = ; > 164 vector <int> b(b_, b_+sizeof(b_)/sizeof(*b_)); > 165 double _ = ; > 166 END > 167 */ > 168 } > 169 // END CUT HERE