Overview
| SHA1 Hash: | d6047a481e7e89f52fdf159d0207332fbdc27a70 |
|---|---|
| Date: | 2014-07-05 15:37:46 |
| User: | kinaba |
| Comment: | 626 |
| 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/626-U/1A.cpp version [75565be9d11ad28a]
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 FixedDiceGameDiv1 { public: 23 + double getExpectation(int a, int b, int c, int d) 24 + { 25 + if(a*b<=c*1) 26 + return -1.0; 27 + auto d1 = distr(a, b); 28 + auto d2 = distr(c, d); 29 + 30 + double total_prob = 0.0; 31 + for(auto& vp: d1) 32 + for(auto& zq: d2) 33 + { 34 + int v = vp.first; 35 + double p = vp.second; 36 + int z = zq.first; 37 + double q = zq.second; 38 + if(v > z) 39 + total_prob += p*q; 40 + } 41 + 42 + double e = 0.0; 43 + for(auto& vp: d1) 44 + for(auto& zq: d2) 45 + { 46 + int v = vp.first; 47 + double p = vp.second; 48 + int z = zq.first; 49 + double q = zq.second; 50 + if(v > z) 51 + e += v * p*q/total_prob; 52 + } 53 + return e; 54 + } 55 + 56 + map<int, double> distr(int n, int f) 57 + { 58 + if(n == 0) { 59 + map<int, double> m; 60 + m[0] = 1,0; 61 + return m; 62 + } 63 + map<int, double> m = distr(n-1, f), m2; 64 + for(auto& up: m) { 65 + int u = up.first; 66 + double p = up.second; 67 + for(int v=1; v<=f; ++v) 68 + m2[u+v] += p/f; 69 + } 70 + return m2; 71 + } 72 +}; 73 + 74 +// BEGIN CUT HERE 75 +#include <ctime> 76 +double start_time; string timer() 77 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 78 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 79 + { os << "{ "; 80 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 81 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 82 +void verify_case(const double& Expected, const double& Received) { 83 + bool ok = (abs(Expected - Received) < 1e-9); 84 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 85 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 86 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 87 +#define END verify_case(_, FixedDiceGameDiv1().getExpectation(a, b, c, d));} 88 +int main(){ 89 + 90 +CASE(0) 91 + int a = 1; 92 + int b = 2; 93 + int c = 1; 94 + int d = 5; 95 + double _ = 2.0; 96 +END 97 +CASE(1) 98 + int a = 3; 99 + int b = 1; 100 + int c = 1; 101 + int d = 3; 102 + double _ = 3.0; 103 +END 104 +CASE(2) 105 + int a = 1; 106 + int b = 5; 107 + int c = 1; 108 + int d = 1; 109 + double _ = 3.4999999999999996; 110 +END 111 +CASE(3) 112 + int a = 2; 113 + int b = 6; 114 + int c = 50; 115 + int d = 30; 116 + double _ = -1.0; 117 +END 118 +CASE(4) 119 + int a = 50; 120 + int b = 11; 121 + int c = 50; 122 + int d = 50; 123 + double _ = 369.8865999182022; 124 +END 125 +/* 126 +CASE(5) 127 + int a = ; 128 + int b = ; 129 + int c = ; 130 + int d = ; 131 + double _ = ; 132 +END 133 +CASE(6) 134 + int a = ; 135 + int b = ; 136 + int c = ; 137 + int d = ; 138 + double _ = ; 139 +END 140 +*/ 141 +} 142 +// END CUT HERE
Added SRM/626-U/1B-U.cpp version [b9e1391bc29563f6]
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 +static const LL INF = 0x1fffffffffffffffLL; 22 + 23 +class NegativeGraphDiv1 { public: 24 + long long findMin(int N, vector <int> from, vector <int> to, vector <int> weight, int charges) 25 + { 26 + // base graph 27 + vector<vector<LL>> g(N, vector<LL>(N, INF)); 28 + vector<vector<LL>> g_neg(N, vector<LL>(N, INF)); 29 + for(int i=0; i<N; ++i) 30 + g[i][i] = 0; 31 + for(int i=0; i<from.size(); ++i) { 32 + int f = from[i]-1; 33 + int t = to[i]-1; 34 + LL w = weight[i]; 35 + g[f][t] = min(g[f][t], w); 36 + g_neg[f][t] = min(g_neg[f][t], -w); 37 + } 38 + 39 + int CMAX = N*2; 40 + 41 + // 0-magic 42 + vector<vector<vector<LL>>> d(CMAX+1, g); 43 + for(int k=0; k<N; ++k) 44 + for(int i=0; i<N; ++i) 45 + for(int j=0; j<N; ++j) 46 + d[0][i][j] = min(d[0][i][j], d[0][i][k]+d[0][k][j]); 47 + // 1-magic 48 + for(int a=0; a<N; ++a) 49 + for(int b=0; b<N; ++b) 50 + for(int c=0; c<N; ++c) 51 + for(int z=0; z<N; ++z) 52 + d[1][a][z] = min(d[1][a][z], d[0][a][b] + g_neg[b][c] + d[0][c][z]); 53 + 54 + // C-magic 55 + for(int C=1; C<=CMAX; ++C) { 56 + for(int a=0; a<N; ++a) 57 + for(int b=0; b<N; ++b) 58 + for(int z=0; z<N; ++z) 59 + d[C][a][z] = min(d[C][a][z], d[1][a][b] + d[C-1][b][z]); 60 + } 61 + 62 + // go,cycle,go 63 + LL best = INF; 64 + for(int S=0; S<=min(CMAX,charges); ++S) 65 + best = min(best, d[S][0][N-1]); 66 + for(int S=0; S<=N; ++S) 67 + for(int M=1; M<=N; ++M) 68 + for(int E=0; E<=CMAX; ++E) if(S+E<=charges) 69 + for(int x=0; x<N; ++x) 70 + best = min(best, d[S][0][x] + d[M][x][x]*((charges-S-E)/M) + d[E][x][N-1]); 71 + return best; 72 + } 73 +}; 74 + 75 +// BEGIN CUT HERE 76 +#include <ctime> 77 +double start_time; string timer() 78 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 79 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 80 + { os << "{ "; 81 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 82 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 83 +void verify_case(const long long& Expected, const long long& Received) { 84 + bool ok = (Expected == Received); 85 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 86 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 87 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 88 +#define END verify_case(_, NegativeGraphDiv1().findMin(N, from, to, weight, charges));} 89 +int main(){ 90 + 91 +CASE(0) 92 + int N = 3; 93 + int from_[] = {1,1,2,2,3,3}; 94 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 95 + int to_[] = {2,3,1,3,1,2}; 96 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 97 + int weight_[] = {1,5,1,10,1,1}; 98 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 99 + int charges = 1; 100 + long long _ = -9LL; 101 +END 102 +CASE(1) 103 + int N = 1; 104 + int from_[] = {1}; 105 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 106 + int to_[] = {1}; 107 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 108 + int weight_[] = {100}; 109 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 110 + int charges = 100000; 111 + long long _ = -10000000LL; 112 +END 113 +CASE(2) 114 + int N = 2; 115 + int from_[] = {1,1,2}; 116 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 117 + int to_[] = {2,2,1}; 118 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 119 + int weight_[] = {6,1,4}; 120 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 121 + int charges = 2; 122 + long long _ = -9LL; 123 +END 124 +CASE(3) 125 + int N = 2; 126 + int from_[] = {1}; 127 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 128 + int to_[] = {2}; 129 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 130 + int weight_[] = {98765}; 131 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 132 + int charges = 1000000000; 133 + long long _ = -98765LL; 134 +END 135 +CASE(4) 136 + int N = 40; 137 + int from_[] = {21,2,36,21,32,1,34,1,40,38,19,10,39,40,31,29,22,18,24,8,25,1,12,31,1,34,16,13,39,39,26,30,4,28,8,9,27,13,6,16,7,11,7,38,30,20,22,29,19,5,22,13,12,7, 138 +33,5,10,31,10,39,18,18,3,19,17,17,34,9,7,17,21,13,12,16,36,39,9,7,3,5,26,16,32,4,26,12,27,24,19,1,19,17,9,22,16,12,31,37,32,9,31,8,2,39,18,26,32,12, 139 +28,11,32,34,2,12,12,33,27,24,5,5,40,34,4,8,10,17,39,30,26,24,10,37,23,40,38,17,4,28,33,31,28,19,36,5,24,17,11,19,4,40,20,16,11,10,9,22,23,23,8,30,10, 140 +23,16,21,10,18,8,28,15,20,38,5,22,4,29,32,13,13,15,24,28,27,11,24,24,23,40,34,20,28,18,26,34,21,13,11,33,28,8,5,9,31,1,32,7,22,12,8,12,8,12,31,35,33, 141 +27,18,6,22,38,9,40,35,15,16,30,4,3,29,2,34,40,3,12,20,29,14,2,3,8,37,12,28,25,7,22,33,4,15,5,14,26,22,16,33,12,11,14,11,5,25,30,21,20,30,25,30,28,37, 142 +23,31,30,3,15,5,25,14,8,13,12,4,18,9,20,17,11,21,5,25,15,9,40,26,28,36,1,10,33,34,5,3,21,32,15,30,33,32,31,19,12,2,16,13,15,4,33,33,26,6,7,36,20,14,7, 143 +39,17,33,4,5,22,21,13,29,38,34,6,24,18,29,4,20,33,16,14,30,20,20,7,21,13,5,20,1,8,18,9,12,24,10,22,33,40,28,30,23,7,36,27,38,36,15,3,36,8,20,27,12,5, 144 +33,40,7,25,20,13,36,30,13,9,3,15,38,33,27,36,4,9,18,39,7,12,30,17,2,21,17,11,26,14,29,26,31,15,13,12,19,35,11,25,19,15,34,9,12,17,37,22,22,16,10,13, 145 +17,12,12,32,1,40,10,34,29,39,7,17,3}; 146 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 147 + int to_[] = {27,37,32,14,19,25,4,14,40,9,36,23,21,25,39,13,4,30,11,32,22,12,29,40,35,32,4,15,25,8,17,18,17,19,34,1,16,16,26,28,2,28,21,16,6,3,12,39,24,31,3,25,26, 148 +30,9,35,29,20,4,21,25,15,32,27,24,13,3,10,21,40,12,39,4,10,2,39,28,23,21,19,21,11,32,20,36,7,11,21,16,29,17,24,18,32,17,38,23,35,1,19,28,20,31,37,16, 149 +20,7,31,3,7,36,15,36,10,6,37,26,39,39,26,31,8,36,26,10,21,24,33,13,29,31,10,12,20,31,39,35,29,39,30,34,26,15,30,4,36,16,38,2,31,22,18,17,12,21,4,11, 150 +32,3,27,14,22,16,37,40,18,25,28,20,27,27,30,11,19,16,18,25,4,21,14,14,13,22,34,25,9,31,27,14,32,23,21,3,1,24,15,30,35,1,24,37,7,28,8,21,40,6,29,36,37, 151 +21,8,17,20,20,28,22,22,13,29,34,20,26,11,10,8,33,10,37,11,16,5,9,18,39,1,8,4,5,2,20,30,4,23,30,23,19,25,30,37,40,31,31,33,33,8,36,40,15,11,31,37,5,40, 152 +2,11,19,32,1,32,27,7,23,9,13,18,12,36,11,32,34,38,35,15,6,36,32,28,6,40,2,33,2,6,7,27,40,30,40,12,39,13,1,22,17,36,1,4,34,25,25,6,20,25,30,4,24,35,7,5, 153 +29,20,28,37,1,30,6,5,5,1,10,40,13,14,21,32,19,25,37,21,28,34,28,29,27,24,33,35,12,25,3,4,12,31,12,7,28,27,10,35,35,18,6,5,16,24,39,26,15,29,13,5,14,36, 154 +35,14,2,39,22,21,2,2,19,38,15,25,10,13,2,39,31,13,5,39,11,33,4,18,18,38,19,39,39,32,23,34,30,21,30,16,36,22,25,14,13,16,10,8,27,29,40,1,29,4,20,25,32, 155 +21,40,1,10,2,17,5,8,5,31,18,18,25,13,3}; 156 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 157 + int weight_[] = {93486,55539,34680,56705,10415,99106,26365,51838,20794,93178,33943,80260,60780,2405,78346,71929,24723,37614,62649,83486,32073,83866,88345,83213,28266, 158 +12730,27623,25353,89948,55002,36720,87151,39759,66091,3690,83881,82635,69084,54138,65876,54205,10236,90478,37230,22337,8209,14258,18375,5268,21824, 159 +76819,4094,63971,1454,21318,44848,92540,26354,18611,2394,68363,64345,60985,725,33692,21195,60992,10243,62006,74884,7822,66830,16114,14663,60701,38174, 160 +30493,26360,7745,7165,47668,83884,89463,46615,7729,22187,78818,10817,31141,79159,24280,67585,48039,3000,98743,39455,12030,27595,55470,14617,93275, 161 +21233,72418,26911,74250,13704,68327,89871,72035,3437,97910,2325,83391,39732,79248,22431,93095,65547,74205,33341,2112,93431,32198,96772,20187,71348, 162 +19102,10840,27306,76027,86368,55373,40192,49370,90597,21685,23630,68099,50880,84474,61907,8446,30127,80977,53007,36125,47411,16950,7445,17166,71035, 163 +20293,24724,7404,6579,11282,83421,37466,80598,53398,15720,66117,28965,90631,44004,27582,29003,65915,35683,48237,66625,50977,82957,54602,3610,431,36560, 164 +38034,5948,72313,16772,81862,11871,33534,91097,93908,57721,91890,46009,21400,41257,66253,90004,56285,85267,23486,6953,66722,69568,74398,32371,15307, 165 +26503,31676,50683,46103,43963,90273,8938,41054,90794,95115,11689,61662,72089,12258,2816,4029,36441,17784,53116,4444,93653,63726,57293,38647,59684, 166 +72212,770,60745,25817,47807,85312,27451,51063,83640,2978,49906,744,69457,20244,8799,7,89118,78421,58827,38689,21327,32558,35756,53505,30526,39049, 167 +63417,24967,54923,62001,38920,59719,65486,174,52231,84176,83531,39896,70918,52397,5169,14876,92511,70020,88390,1168,35311,56953,12966,94805,3885, 168 +14103,24615,10710,27635,24064,23022,4506,29939,2044,48330,53688,41320,21646,62598,41367,22910,70284,11512,64411,16215,41072,87263,38301,81731,41930, 169 +96029,93359,32457,98487,62899,51282,8656,45002,83345,36991,77420,37086,53484,18823,74711,81453,81394,79933,38466,61198,98665,5528,9196,40298,55089, 170 +24162,99257,58066,90088,66809,53472,73237,31964,4792,42336,88141,80467,96893,44276,76106,79430,17072,85727,49790,84394,47215,16792,44544,75123,4203, 171 +6283,49250,54852,27312,42709,97204,16834,80593,27523,31700,44435,25338,43513,84894,43514,90145,74675,54302,85249,10281,44231,28994,63813,24198,24686, 172 +7082,46471,3025,57872,57510,13666,48726,3907,12500,53578,28346,15804,32122,89396,15406,11207,59571,78192,84950,84280,84597,27811,56165,69239,53400, 173 +32562,95679,32377,5909,29805,85810,31593,85985,27637,24974,41557,56442,48912,62362,98580,59154,78739,75721,72097,90622,91334,79685,19371,15487,67804, 174 +2582,26623,14347,98894,92041,83228,58089,96181,3913,75974,18569,11428,95165,27563}; 175 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 176 + int charges = 160743953; 177 + long long _ = -15328623718914LL; 178 +END 179 +CASE(4) 180 + int N = 50; 181 + int from_[] = {21,2,36,21,32,1,34,1,40,38,19,10,39,40,31,29,22,18,24,8,25,1,12,31,1,34,16,13,39,39,26,30,4,28,8,9,27,13,6,16,7,11,7,38,30,20,22,29,19,5,22,13,12,7, 182 +33,5,10,31,10,39,18,18,3,19,17,17,34,9,7,17,21,13,12,16,36,39,9,7,3,5,26,16,32,4,26,12,27,24,19,1,19,17,9,22,16,12,31,37,32,9,31,8,2,39,18,26,32,12, 183 +28,11,32,34,2,12,12,33,27,24,5,5,40,34,4,8,10,17,39,30,26,24,10,37,23,40,38,17,4,28,33,31,28,19,36,5,24,17,11,19,4,40,20,16,11,10,9,22,23,23,8,30,10, 184 +23,16,21,10,18,8,28,15,20,38,5,22,4,29,32,13,13,15,24,28,27,11,24,24,23,40,34,20,28,18,26,34,21,13,11,33,28,8,5,9,31,1,32,7,22,12,8,12,8,12,31,35,33, 185 +27,18,6,22,38,9,40,35,15,16,30,4,3,29,2,34,40,3,12,20,29,14,2,3,8,37,12,28,25,7,22,33,4,15,5,14,26,22,16,33,12,11,14,11,5,25,30,21,20,30,25,30,28,37, 186 +23,31,30,3,15,5,25,14,8,13,12,4,18,9,20,17,11,21,5,25,15,9,40,26,28,36,1,10,33,34,5,3,21,32,15,30,33,32,31,19,12,2,16,13,15,4,33,33,26,6,7,36,20,14,7, 187 +39,17,33,4,5,22,21,13,29,38,34,6,24,18,29,4,20,33,16,14,30,20,20,7,21,13,5,20,1,8,18,9,12,24,10,22,33,40,28,30,23,7,36,27,38,36,15,3,36,8,20,27,12,5, 188 +33,40,7,25,20,13,36,30,13,9,3,15,38,33,27,36,4,9,18,39,7,12,30,17,2,21,17,11,26,14,29,26,31,15,13,12,19,35,11,25,19,15,34,9,12,17,37,22,22,16,10,13, 189 +17,12,12,32,1,40,10,34,29,39,7,17,3,1,1,1,1,1,1,1,1,1,1}; 190 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 191 + int to_[] = {27,37,32,14,19,25,4,14,40,9,36,23,21,25,39,13,4,30,11,32,22,12,29,40,35,32,4,15,25,8,17,18,17,19,34,1,16,16,26,28,2,28,21,16,6,3,12,39,24,31,3,25,26, 192 +30,9,35,29,20,4,21,25,15,32,27,24,13,3,10,21,40,12,39,4,10,2,39,28,23,21,19,21,11,32,20,36,7,11,21,16,29,17,24,18,32,17,38,23,35,1,19,28,20,31,37,16, 193 +20,7,31,3,7,36,15,36,10,6,37,26,39,39,26,31,8,36,26,10,21,24,33,13,29,31,10,12,20,31,39,35,29,39,30,34,26,15,30,4,36,16,38,2,31,22,18,17,12,21,4,11, 194 +32,3,27,14,22,16,37,40,18,25,28,20,27,27,30,11,19,16,18,25,4,21,14,14,13,22,34,25,9,31,27,14,32,23,21,3,1,24,15,30,35,1,24,37,7,28,8,21,40,6,29,36,37, 195 +21,8,17,20,20,28,22,22,13,29,34,20,26,11,10,8,33,10,37,11,16,5,9,18,39,1,8,4,5,2,20,30,4,23,30,23,19,25,30,37,40,31,31,33,33,8,36,40,15,11,31,37,5,40, 196 +2,11,19,32,1,32,27,7,23,9,13,18,12,36,11,32,34,38,35,15,6,36,32,28,6,40,2,33,2,6,7,27,40,30,40,12,39,13,1,22,17,36,1,4,34,25,25,6,20,25,30,4,24,35,7,5, 197 +29,20,28,37,1,30,6,5,5,1,10,40,13,14,21,32,19,25,37,21,28,34,28,29,27,24,33,35,12,25,3,4,12,31,12,7,28,27,10,35,35,18,6,5,16,24,39,26,15,29,13,5,14,36, 198 +35,14,2,39,22,21,2,2,19,38,15,25,10,13,2,39,31,13,5,39,11,33,4,18,18,38,19,39,39,32,23,34,30,21,30,16,36,22,25,14,13,16,10,8,27,29,40,1,29,4,20,25,32, 199 +21,40,1,10,2,17,5,8,5,31,18,18,25,13,3,41,42,43,44,45,46,47,48,49,50}; 200 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 201 + int weight_[] = {93486,55539,34680,56705,10415,99106,26365,51838,20794,93178,33943,80260,60780,2405,78346,71929,24723,37614,62649,83486,32073,83866,88345,83213,28266, 202 +12730,27623,25353,89948,55002,36720,87151,39759,66091,3690,83881,82635,69084,54138,65876,54205,10236,90478,37230,22337,8209,14258,18375,5268,21824, 203 +76819,4094,63971,1454,21318,44848,92540,26354,18611,2394,68363,64345,60985,725,33692,21195,60992,10243,62006,74884,7822,66830,16114,14663,60701,38174, 204 +30493,26360,7745,7165,47668,83884,89463,46615,7729,22187,78818,10817,31141,79159,24280,67585,48039,3000,98743,39455,12030,27595,55470,14617,93275, 205 +21233,72418,26911,74250,13704,68327,89871,72035,3437,97910,2325,83391,39732,79248,22431,93095,65547,74205,33341,2112,93431,32198,96772,20187,71348, 206 +19102,10840,27306,76027,86368,55373,40192,49370,90597,21685,23630,68099,50880,84474,61907,8446,30127,80977,53007,36125,47411,16950,7445,17166,71035, 207 +20293,24724,7404,6579,11282,83421,37466,80598,53398,15720,66117,28965,90631,44004,27582,29003,65915,35683,48237,66625,50977,82957,54602,3610,431,36560, 208 +38034,5948,72313,16772,81862,11871,33534,91097,93908,57721,91890,46009,21400,41257,66253,90004,56285,85267,23486,6953,66722,69568,74398,32371,15307, 209 +26503,31676,50683,46103,43963,90273,8938,41054,90794,95115,11689,61662,72089,12258,2816,4029,36441,17784,53116,4444,93653,63726,57293,38647,59684, 210 +72212,770,60745,25817,47807,85312,27451,51063,83640,2978,49906,744,69457,20244,8799,7,89118,78421,58827,38689,21327,32558,35756,53505,30526,39049, 211 +63417,24967,54923,62001,38920,59719,65486,174,52231,84176,83531,39896,70918,52397,5169,14876,92511,70020,88390,1168,35311,56953,12966,94805,3885, 212 +14103,24615,10710,27635,24064,23022,4506,29939,2044,48330,53688,41320,21646,62598,41367,22910,70284,11512,64411,16215,41072,87263,38301,81731,41930, 213 +96029,93359,32457,98487,62899,51282,8656,45002,83345,36991,77420,37086,53484,18823,74711,81453,81394,79933,38466,61198,98665,5528,9196,40298,55089, 214 +24162,99257,58066,90088,66809,53472,73237,31964,4792,42336,88141,80467,96893,44276,76106,79430,17072,85727,49790,84394,47215,16792,44544,75123,4203, 215 +6283,49250,54852,27312,42709,97204,16834,80593,27523,31700,44435,25338,43513,84894,43514,90145,74675,54302,85249,10281,44231,28994,63813,24198,24686, 216 +7082,46471,3025,57872,57510,13666,48726,3907,12500,53578,28346,15804,32122,89396,15406,11207,59571,78192,84950,84280,84597,27811,56165,69239,53400, 217 +32562,95679,32377,5909,29805,85810,31593,85985,27637,24974,41557,56442,48912,62362,98580,59154,78739,75721,72097,90622,91334,79685,19371,15487,67804, 218 +2582,26623,14347,98894,92041,83228,58089,96181,3913,75974,18569,11428,95165,27563,10,10,10,10,10,10,10,10,10,10}; 219 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 220 + int charges = 160743953; 221 + long long _ = -15328623718914LL; 222 +END 223 +CASE(5) 224 + int N = 2; 225 + int from_[] = {1,1}; 226 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 227 + int to_[] = {2,2}; 228 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 229 + int weight_[] = {3,1}; 230 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 231 + int charges = 1; 232 + long long _ = -3LL; 233 +END 234 +/* 235 +CASE(6) 236 + int N = ; 237 + int from_[] = ; 238 + vector <int> from(from_, from_+sizeof(from_)/sizeof(*from_)); 239 + int to_[] = ; 240 + vector <int> to(to_, to_+sizeof(to_)/sizeof(*to_)); 241 + int weight_[] = ; 242 + vector <int> weight(weight_, weight_+sizeof(weight_)/sizeof(*weight_)); 243 + int charges = ; 244 + long long _ = LL; 245 +END 246 +*/ 247 +} 248 +// END CUT HERE
Added SRM/626-U/1C-U.cpp version [e67bc0ae357b08b2]
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 +struct mint 24 +{ 25 + unsigned val; 26 + mint():val(0){} 27 + mint(int x):val(x%MODVAL) {} 28 + mint(unsigned x):val(x%MODVAL) {} 29 + mint(LL x):val(x%MODVAL) {} 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 +int gcd(int a, int b) 37 +{ 38 + while(a) 39 + swap(a, b%=a); 40 + return b; 41 +} 42 + 43 +class ReflectiveRectangle { public: 44 + int findSum(int A, int B, int bounces) 45 + { 46 + if(bounces%2 == 1) 47 + return 0; 48 + if(bounces == 0) 49 + return (mint(A)*A+mint(B)*B).val; 50 + 51 + mint sh; 52 + for(int h=1; h<bounces+2; h+=2) { 53 + if(gcd(h, bounces+2) == 1) 54 + sh += LL(h)*h; 55 + } 56 + // solution: Sigma(h*h) - Sigma_divisors(h*h) ? 57 + // but no time to code...... 58 + 59 + return (sh*A*A+sh*B*B).val; 60 + } 61 +}; 62 + 63 +// BEGIN CUT HERE 64 +#include <ctime> 65 +double start_time; string timer() 66 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 67 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 68 + { os << "{ "; 69 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 70 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 71 +void verify_case(const int& Expected, const int& Received) { 72 + bool ok = (Expected == Received); 73 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 74 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 75 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 76 +#define END verify_case(_, ReflectiveRectangle().findSum(sideA, sideB, bounces));} 77 +int main(){ 78 + 79 +CASE(0) 80 + int sideA = 3; 81 + int sideB = 4; 82 + int bounces = 0; 83 + int _ = 25; 84 +END 85 +CASE(1) 86 + int sideA = 3; 87 + int sideB = 3; 88 + int bounces = 2; 89 + int _ = 180; 90 +END 91 +CASE(2) 92 + int sideA = 13; 93 + int sideB = 17; 94 + int bounces = 1; 95 + int _ = 0; 96 +END 97 +CASE(3) 98 + int sideA = 59325; 99 + int sideB = 31785; 100 + int bounces = 262142; 101 + int _ = 48032850; 102 +END 103 +CASE(4) 104 + int sideA = 1000000; 105 + int sideB = 1000000; 106 + int bounces = 1000000000; 107 + int _ = 145972110; 108 +END 109 +/* 110 +CASE(5) 111 + int sideA = ; 112 + int sideB = ; 113 + int bounces = ; 114 + int _ = ; 115 +END 116 +CASE(6) 117 + int sideA = ; 118 + int sideB = ; 119 + int bounces = ; 120 + int _ = ; 121 +END 122 +*/ 123 +} 124 +// END CUT HERE