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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 57 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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 -> nEq -> prob 26 + vector< vector< vector<double> > > tk; // nHumanNodes -> nEq -> nEq -> prob 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<double> >(2, vector<double>(2))), 61 + vector< vector< vector<double> > >(2, vector< vector<double> >(2, vector<double>(2))) 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<double> >(N+1, vector<double>(N+1))), 75 + vector< vector< vector<double> > >(N+1, vector< vector<double> >(N+1, vector<double>(N+1))) 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.th[bh][bhe][bke]; 85 + s.th[ah+bh][ahe+bhe][ake+bke] += a.th[ah][ahe][ake]*b.tk[bh][bhe][bke]; 86 + s.tk[ah+bh][ahe+bhe][ake+bke] += a.tk[ah][ahe][ake]*b.th[bh][bhe][bke]; 87 + if(ake+bke!=0) 88 + s.tk[ah+bh][ahe+bhe][ake+bke-1] += a.tk[ah][ahe][ake]*b.tk[bh][bhe][bke]; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 105 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,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,25,26,27,28,29,30,31,32,33,34,35,36}; 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,24,25,26,27,28,29,30,31,32,33,34,35}; 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,25,26,27,28,29,30,31,32,33,34,35,36}; 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