0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 am>..#include <s
0020: 73 74 72 65 61 6d 3e 0d 0a 23 69 6e 63 6c 75 64 stream>..#includ
0030: 65 20 3c 69 6f 6d 61 6e 69 70 3e 0d 0a 23 69 6e e <iomanip>..#in
0040: 63 6c 75 64 65 20 3c 76 65 63 74 6f 72 3e 0d 0a clude <vector>..
0050: 23 69 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 #include <string
0060: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 70 >..#include <map
0070: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 73 65 74 >..#include <set
0080: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 61 6c 67 >..#include <alg
0090: 6f 72 69 74 68 6d 3e 0d 0a 23 69 6e 63 6c 75 64 orithm>..#includ
00a0: 65 20 3c 6e 75 6d 65 72 69 63 3e 0d 0a 23 69 6e e <numeric>..#in
00b0: 63 6c 75 64 65 20 3c 69 74 65 72 61 74 6f 72 3e clude <iterator>
00c0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 66 75 6e 63 ..#include <func
00d0: 74 69 6f 6e 61 6c 3e 0d 0a 23 69 6e 63 6c 75 64 tional>..#includ
00e0: 65 20 3c 63 6f 6d 70 6c 65 78 3e 0d 0a 23 69 6e e <complex>..#in
00f0: 63 6c 75 64 65 20 3c 71 75 65 75 65 3e 0d 0a 23 clude <queue>..#
0100: 69 6e 63 6c 75 64 65 20 3c 73 74 61 63 6b 3e 0d include <stack>.
0110: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 6d 61 74 68 .#include <cmath
0120: 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 61 73 >..#include <cas
0130: 73 65 72 74 3e 0d 0a 75 73 69 6e 67 20 6e 61 6d sert>..using nam
0140: 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 79 70 espace std;..typ
0150: 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 20 4c edef long long L
0160: 4c 3b 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 L;..typedef long
0170: 20 64 6f 75 62 6c 65 20 4c 44 3b 0d 0a 74 79 70 double LD;..typ
0180: 65 64 65 66 20 63 6f 6d 70 6c 65 78 3c 4c 44 3e edef complex<LD>
0190: 20 43 4d 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 43 CMP;....class C
01a0: 65 6e 74 61 75 72 43 6f 6d 70 61 6e 79 20 7b 20 entaurCompany {
01b0: 70 75 62 6c 69 63 3a 0d 0a 09 73 74 72 75 63 74 public:...struct
01c0: 20 53 74 61 74 65 20 7b 0d 0a 09 09 69 6e 74 20 State {....int
01d0: 6e 4e 6f 64 65 3b 0d 0a 09 09 76 65 63 74 6f 72 nNode;....vector
01e0: 3c 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 < vector< vector
01f0: 3c 64 6f 75 62 6c 65 3e 20 3e 20 3e 20 74 68 3b <double> > > th;
0200: 20 2f 2f 20 6e 48 75 6d 61 6e 4e 6f 64 65 73 20 // nHumanNodes
0210: 2d 3e 20 6e 45 71 20 2d 3e 20 6e 45 71 20 2d 3e -> nEq -> nEq ->
0220: 20 70 72 6f 62 0d 0a 09 09 76 65 63 74 6f 72 3c prob....vector<
0230: 20 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c vector< vector<
0240: 64 6f 75 62 6c 65 3e 20 3e 20 3e 20 74 6b 3b 20 double> > > tk;
0250: 2f 2f 20 6e 48 75 6d 61 6e 4e 6f 64 65 73 20 2d // nHumanNodes -
0260: 3e 20 6e 45 71 20 2d 3e 20 6e 45 71 20 2d 3e 20 > nEq -> nEq ->
0270: 70 72 6f 62 0d 0a 09 7d 3b 0d 0a 0d 0a 09 64 6f prob...};.....do
0280: 75 62 6c 65 20 67 65 74 76 61 6c 75 65 28 76 65 uble getvalue(ve
0290: 63 74 6f 72 20 3c 69 6e 74 3e 20 61 2c 20 76 65 ctor <int> a, ve
02a0: 63 74 6f 72 20 3c 69 6e 74 3e 20 62 29 0d 0a 09 ctor <int> b)...
02b0: 7b 0d 0a 09 09 69 6e 74 20 4e 20 3d 20 61 2e 73 {....int N = a.s
02c0: 69 7a 65 28 29 20 2b 20 31 3b 0d 0a 09 09 76 65 ize() + 1;....ve
02d0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 69 6e 74 ctor< vector<int
02e0: 3e 20 3e 20 47 28 4e 29 3b 0d 0a 09 09 66 6f 72 > > G(N);....for
02f0: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 61 2e 73 69 (int i=0; i<a.si
0300: 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 ze(); ++i) {....
0310: 09 47 5b 61 5b 69 5d 2d 31 5d 2e 70 75 73 68 5f .G[a[i]-1].push_
0320: 62 61 63 6b 28 62 5b 69 5d 2d 31 29 3b 0d 0a 09 back(b[i]-1);...
0330: 09 09 47 5b 62 5b 69 5d 2d 31 5d 2e 70 75 73 68 ..G[b[i]-1].push
0340: 5f 62 61 63 6b 28 61 5b 69 5d 2d 31 29 3b 0d 0a _back(a[i]-1);..
0350: 09 09 7d 0d 0a 0d 0a 09 09 64 6f 75 62 6c 65 20 ..}......double
0360: 65 20 3d 20 30 2e 30 3b 0d 0a 09 09 53 74 61 74 e = 0.0;....Stat
0370: 65 20 73 20 3d 20 72 65 63 28 2d 31 2c 20 30 2c e s = rec(-1, 0,
0380: 20 47 29 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 G);....for(int
0390: 61 68 3d 30 3b 20 61 68 3c 3d 73 2e 6e 4e 6f 64 ah=0; ah<=s.nNod
03a0: 65 3b 20 2b 2b 61 68 29 0d 0a 09 09 66 6f 72 28 e; ++ah)....for(
03b0: 69 6e 74 20 61 68 65 3d 30 3b 20 61 68 65 3c 3d int ahe=0; ahe<=
03c0: 61 68 3b 20 2b 2b 61 68 65 29 0d 0a 09 09 66 6f ah; ++ahe)....fo
03d0: 72 28 69 6e 74 20 61 6b 65 3d 30 3b 20 61 6b 65 r(int ake=0; ake
03e0: 3c 3d 28 73 2e 6e 4e 6f 64 65 2d 61 68 29 3b 20 <=(s.nNode-ah);
03f0: 2b 2b 61 6b 65 29 0d 0a 09 09 7b 0d 0a 09 09 09 ++ake)....{.....
0400: 69 6e 74 20 61 6b 20 3d 20 73 2e 6e 4e 6f 64 65 int ak = s.nNode
0410: 20 2d 20 61 68 3b 0d 0a 09 09 09 7b 0d 0a 09 09 - ah;.....{....
0420: 09 09 64 6f 75 62 6c 65 20 70 20 3d 20 73 2e 74 ..double p = s.t
0430: 68 5b 61 68 5d 5b 61 68 65 5d 5b 61 6b 65 5d 3b h[ah][ahe][ake];
0440: 0d 0a 09 09 09 09 65 20 2b 3d 20 70 20 2a 20 28 ......e += p * (
0450: 6d 61 78 28 32 2a 28 61 68 65 2d 31 29 2d 61 68 max(2*(ahe-1)-ah
0460: 2c 30 29 2b 6d 61 78 28 32 2a 28 61 6b 65 2d 31 ,0)+max(2*(ake-1
0470: 29 2d 61 6b 2c 30 29 29 3b 0d 0a 09 09 09 7d 0d )-ak,0));.....}.
0480: 0a 09 09 09 7b 0d 0a 09 09 09 09 64 6f 75 62 6c ....{......doubl
0490: 65 20 70 20 3d 20 73 2e 74 6b 5b 61 68 5d 5b 61 e p = s.tk[ah][a
04a0: 68 65 5d 5b 61 6b 65 5d 3b 0d 0a 09 09 09 09 65 he][ake];......e
04b0: 20 2b 3d 20 70 20 2a 20 28 6d 61 78 28 32 2a 28 += p * (max(2*(
04c0: 61 68 65 2d 31 29 2d 61 68 2c 30 29 2b 6d 61 78 ahe-1)-ah,0)+max
04d0: 28 32 2a 28 61 6b 65 2d 31 29 2d 61 6b 2c 30 29 (2*(ake-1)-ak,0)
04e0: 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a 09 );.....}....}...
04f0: 09 72 65 74 75 72 6e 20 65 3b 0d 0a 09 7d 0d 0a .return e;...}..
0500: 0d 0a 09 53 74 61 74 65 20 72 65 63 28 69 6e 74 ...State rec(int
0510: 20 70 2c 20 69 6e 74 20 76 2c 20 63 6f 6e 73 74 p, int v, const
0520: 20 76 65 63 74 6f 72 3c 76 65 63 74 6f 72 3c 69 vector<vector<i
0530: 6e 74 3e 20 3e 26 20 47 29 0d 0a 09 7b 0d 0a 09 nt> >& G)...{...
0540: 09 53 74 61 74 65 20 73 20 3d 20 7b 31 2c 0d 0a .State s = {1,..
0550: 09 09 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f ...vector< vecto
0560: 72 3c 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 r< vector<double
0570: 3e 20 3e 20 3e 28 32 2c 20 76 65 63 74 6f 72 3c > > >(2, vector<
0580: 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 vector<double>
0590: 3e 28 32 2c 20 76 65 63 74 6f 72 3c 64 6f 75 62 >(2, vector<doub
05a0: 6c 65 3e 28 32 29 29 29 2c 0d 0a 09 09 09 76 65 le>(2))),.....ve
05b0: 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c 20 76 65 ctor< vector< ve
05c0: 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 3e 20 3e ctor<double> > >
05d0: 28 32 2c 20 76 65 63 74 6f 72 3c 20 76 65 63 74 (2, vector< vect
05e0: 6f 72 3c 64 6f 75 62 6c 65 3e 20 3e 28 32 2c 20 or<double> >(2,
05f0: 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 28 32 vector<double>(2
0600: 29 29 29 0d 0a 09 09 7d 3b 0d 0a 09 09 73 2e 74 )))....};....s.t
0610: 68 5b 31 5d 5b 31 5d 5b 30 5d 20 3d 20 30 2e 35 h[1][1][0] = 0.5
0620: 3b 0d 0a 09 09 73 2e 74 6b 5b 30 5d 5b 30 5d 5b ;....s.tk[0][0][
0630: 31 5d 20 3d 20 30 2e 35 3b 0d 0a 09 09 66 6f 72 1] = 0.5;....for
0640: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 47 5b 76 5d (int i=0; i<G[v]
0650: 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 69 66 .size(); ++i) if
0660: 28 47 5b 76 5d 5b 69 5d 20 21 3d 20 70 29 0d 0a (G[v][i] != p)..
0670: 09 09 09 73 20 3d 20 63 6f 6d 62 69 6e 65 28 73 ...s = combine(s
0680: 2c 20 72 65 63 28 76 2c 20 47 5b 76 5d 5b 69 5d , rec(v, G[v][i]
0690: 2c 20 47 29 29 3b 0d 0a 09 09 72 65 74 75 72 6e , G));....return
06a0: 20 73 3b 0d 0a 09 7d 0d 0a 0d 0a 09 53 74 61 74 s;...}.....Stat
06b0: 65 20 63 6f 6d 62 69 6e 65 28 63 6f 6e 73 74 20 e combine(const
06c0: 53 74 61 74 65 26 20 61 2c 20 63 6f 6e 73 74 20 State& a, const
06d0: 53 74 61 74 65 26 20 62 29 0d 0a 09 7b 0d 0a 09 State& b)...{...
06e0: 09 69 6e 74 20 4e 20 3d 20 61 2e 6e 4e 6f 64 65 .int N = a.nNode
06f0: 20 2b 20 62 2e 6e 4e 6f 64 65 3b 0d 0a 09 09 53 + b.nNode;....S
0700: 74 61 74 65 20 73 20 3d 20 7b 4e 2c 0d 0a 09 09 tate s = {N,....
0710: 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 3c .vector< vector<
0720: 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 vector<double>
0730: 3e 20 3e 28 4e 2b 31 2c 20 76 65 63 74 6f 72 3c > >(N+1, vector<
0740: 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e 20 vector<double>
0750: 3e 28 4e 2b 31 2c 20 76 65 63 74 6f 72 3c 64 6f >(N+1, vector<do
0760: 75 62 6c 65 3e 28 4e 2b 31 29 29 29 2c 0d 0a 09 uble>(N+1))),...
0770: 09 09 76 65 63 74 6f 72 3c 20 76 65 63 74 6f 72 ..vector< vector
0780: 3c 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e < vector<double>
0790: 20 3e 20 3e 28 4e 2b 31 2c 20 76 65 63 74 6f 72 > >(N+1, vector
07a0: 3c 20 76 65 63 74 6f 72 3c 64 6f 75 62 6c 65 3e < vector<double>
07b0: 20 3e 28 4e 2b 31 2c 20 76 65 63 74 6f 72 3c 64 >(N+1, vector<d
07c0: 6f 75 62 6c 65 3e 28 4e 2b 31 29 29 29 0d 0a 09 ouble>(N+1)))...
07d0: 09 7d 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 61 .};....for(int a
07e0: 68 3d 30 3b 20 61 68 3c 3d 61 2e 6e 4e 6f 64 65 h=0; ah<=a.nNode
07f0: 3b 20 2b 2b 61 68 29 0d 0a 09 09 66 6f 72 28 69 ; ++ah)....for(i
0800: 6e 74 20 61 68 65 3d 30 3b 20 61 68 65 3c 3d 61 nt ahe=0; ahe<=a
0810: 68 3b 20 2b 2b 61 68 65 29 0d 0a 09 09 66 6f 72 h; ++ahe)....for
0820: 28 69 6e 74 20 61 6b 65 3d 30 3b 20 61 6b 65 3c (int ake=0; ake<
0830: 3d 28 61 2e 6e 4e 6f 64 65 2d 61 68 29 3b 20 2b =(a.nNode-ah); +
0840: 2b 61 6b 65 29 0d 0a 09 09 66 6f 72 28 69 6e 74 +ake)....for(int
0850: 20 62 68 3d 30 3b 20 62 68 3c 3d 62 2e 6e 4e 6f bh=0; bh<=b.nNo
0860: 64 65 3b 20 2b 2b 62 68 29 0d 0a 09 09 66 6f 72 de; ++bh)....for
0870: 28 69 6e 74 20 62 68 65 3d 30 3b 20 62 68 65 3c (int bhe=0; bhe<
0880: 3d 62 68 3b 20 2b 2b 62 68 65 29 0d 0a 09 09 66 =bh; ++bhe)....f
0890: 6f 72 28 69 6e 74 20 62 6b 65 3d 30 3b 20 62 6b or(int bke=0; bk
08a0: 65 3c 3d 28 62 2e 6e 4e 6f 64 65 2d 62 68 29 3b e<=(b.nNode-bh);
08b0: 20 2b 2b 62 6b 65 29 20 7b 0d 0a 09 09 09 69 66 ++bke) {.....if
08c0: 28 61 68 65 2b 62 68 65 21 3d 30 29 0d 0a 09 09 (ahe+bhe!=0)....
08d0: 09 73 2e 74 68 5b 61 68 2b 62 68 5d 5b 61 68 65 .s.th[ah+bh][ahe
08e0: 2b 62 68 65 2d 31 5d 5b 61 6b 65 2b 62 6b 65 5d +bhe-1][ake+bke]
08f0: 20 2b 3d 20 61 2e 74 68 5b 61 68 5d 5b 61 68 65 += a.th[ah][ahe
0900: 5d 5b 61 6b 65 5d 2a 62 2e 74 68 5b 62 68 5d 5b ][ake]*b.th[bh][
0910: 62 68 65 5d 5b 62 6b 65 5d 3b 0d 0a 09 09 09 73 bhe][bke];.....s
0920: 2e 74 68 5b 61 68 2b 62 68 5d 5b 61 68 65 2b 62 .th[ah+bh][ahe+b
0930: 68 65 5d 5b 61 6b 65 2b 62 6b 65 5d 20 2b 3d 20 he][ake+bke] +=
0940: 61 2e 74 68 5b 61 68 5d 5b 61 68 65 5d 5b 61 6b a.th[ah][ahe][ak
0950: 65 5d 2a 62 2e 74 6b 5b 62 68 5d 5b 62 68 65 5d e]*b.tk[bh][bhe]
0960: 5b 62 6b 65 5d 3b 0d 0a 09 09 09 73 2e 74 6b 5b [bke];.....s.tk[
0970: 61 68 2b 62 68 5d 5b 61 68 65 2b 62 68 65 5d 5b ah+bh][ahe+bhe][
0980: 61 6b 65 2b 62 6b 65 5d 20 2b 3d 20 61 2e 74 6b ake+bke] += a.tk
0990: 5b 61 68 5d 5b 61 68 65 5d 5b 61 6b 65 5d 2a 62 [ah][ahe][ake]*b
09a0: 2e 74 68 5b 62 68 5d 5b 62 68 65 5d 5b 62 6b 65 .th[bh][bhe][bke
09b0: 5d 3b 0d 0a 09 09 09 69 66 28 61 6b 65 2b 62 6b ];.....if(ake+bk
09c0: 65 21 3d 30 29 0d 0a 09 09 09 73 2e 74 6b 5b 61 e!=0).....s.tk[a
09d0: 68 2b 62 68 5d 5b 61 68 65 2b 62 68 65 5d 5b 61 h+bh][ahe+bhe][a
09e0: 6b 65 2b 62 6b 65 2d 31 5d 20 2b 3d 20 61 2e 74 ke+bke-1] += a.t
09f0: 6b 5b 61 68 5d 5b 61 68 65 5d 5b 61 6b 65 5d 2a k[ah][ahe][ake]*
0a00: 62 2e 74 6b 5b 62 68 5d 5b 62 68 65 5d 5b 62 6b b.tk[bh][bhe][bk
0a10: 65 5d 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 e];....}....retu
0a20: 72 6e 20 73 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d rn s;...}..};...
0a30: 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 .// BEGIN CUT HE
0a40: 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 RE..#include <ct
0a50: 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 ime>..double sta
0a60: 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 rt_time; string
0a70: 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 timer().. { ostr
0a80: 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 ingstream os; os
0a90: 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 << " (" << int(
0aa0: 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 (clock()-start_t
0ab0: 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f ime)/CLOCKS_PER_
0ac0: 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d SEC*1000) << " m
0ad0: 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 sec)"; return os
0ae0: 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c .str(); }..templ
0af0: 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 ate<typename T>
0b00: 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f ostream& operato
0b10: 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c r<<(ostream& os,
0b20: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e const vector<T>
0b30: 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 & v).. { os << "
0b40: 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 { ";.. for(typ
0b50: 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a ename vector<T>:
0b60: 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 :const_iterator
0b70: 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 it=v.begin(); it
0b80: 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 !=v.end(); ++it)
0b90: 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 .. os << '\"'
0ba0: 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c << *it << '\"' <
0bb0: 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 < (it+1==v.end()
0bc0: 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f ? "" : ", "); o
0bd0: 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 s << " }"; retur
0be0: 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 n os; }..void ve
0bf0: 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 rify_case(const
0c00: 64 6f 75 62 6c 65 26 20 45 78 70 65 63 74 65 64 double& Expected
0c10: 2c 20 63 6f 6e 73 74 20 64 6f 75 62 6c 65 26 20 , const double&
0c20: 52 65 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f Received) {.. bo
0c30: 6f 6c 20 6f 6b 20 3d 20 28 61 62 73 28 45 78 70 ol ok = (abs(Exp
0c40: 65 63 74 65 64 20 2d 20 52 65 63 65 69 76 65 64 ected - Received
0c50: 29 20 3c 20 31 65 2d 39 29 3b 0d 0a 20 69 66 28 ) < 1e-9);.. if(
0c60: 6f 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 ok) cerr << "PAS
0c70: 53 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 SED" << timer()
0c80: 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b << endl; else {
0c90: 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 cerr << "FAILED
0ca0: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
0cb0: 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 endl;.. cerr <<
0cc0: 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 "\to: \"" << Exp
0cd0: 65 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c ected << '\"' <<
0ce0: 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c endl << "\tx: \
0cf0: 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c "" << Received <
0d00: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 < '\"' << endl;
0d10: 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 } }..#define CAS
0d20: 45 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 E(N) {cerr << "T
0d30: 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e est Case #" << N
0d40: 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 << "..." << flu
0d50: 73 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 sh; start_time=c
0d60: 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 lock();..#define
0d70: 20 45 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 END. verify_cas
0d80: 65 28 5f 2c 20 43 65 6e 74 61 75 72 43 6f 6d 70 e(_, CentaurComp
0d90: 61 6e 79 28 29 2e 67 65 74 76 61 6c 75 65 28 61 any().getvalue(a
0da0: 2c 20 62 29 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 , b));}..int mai
0db0: 6e 28 29 7b 0d 0a 0d 0a 43 41 53 45 28 30 29 0d n(){....CASE(0).
0dc0: 0a 09 69 6e 74 20 61 5f 5b 5d 20 3d 20 7b 31 7d ..int a_[] = {1}
0dd0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0de0: 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 t> a(a_, a_+size
0df0: 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 of(a_)/sizeof(*a
0e00: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d _)); ...int b_[]
0e10: 20 3d 20 7b 32 7d 3b 0d 0a 09 20 20 76 65 63 74 = {2};... vect
0e20: 6f 72 20 3c 69 6e 74 3e 20 62 28 62 5f 2c 20 62 or <int> b(b_, b
0e30: 5f 2b 73 69 7a 65 6f 66 28 62 5f 29 2f 73 69 7a _+sizeof(b_)/siz
0e40: 65 6f 66 28 2a 62 5f 29 29 3b 20 0d 0a 09 64 6f eof(*b_)); ...do
0e50: 75 62 6c 65 20 5f 20 3d 20 30 2e 30 3b 20 0d 0a uble _ = 0.0; ..
0e60: 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 END..CASE(1)...i
0e70: 6e 74 20 61 5f 5b 5d 20 3d 20 7b 31 2c 31 2c 31 nt a_[] = {1,1,1
0e80: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
0e90: 6e 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a nt> a(a_, a_+siz
0ea0: 65 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(a_)/sizeof(*
0eb0: 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b a_)); ...int b_[
0ec0: 5d 20 3d 20 7b 32 2c 33 2c 34 7d 3b 0d 0a 09 20 ] = {2,3,4};...
0ed0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 28 vector <int> b(
0ee0: 62 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 28 62 5f b_, b_+sizeof(b_
0ef0: 29 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 29 3b 20 )/sizeof(*b_));
0f00: 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e ...double _ = 0.
0f10: 31 32 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 125; ..END..CASE
0f20: 28 32 29 0d 0a 09 69 6e 74 20 61 5f 5b 5d 20 3d (2)...int a_[] =
0f30: 20 7b 31 2c 32 2c 33 2c 32 2c 32 7d 3b 0d 0a 09 {1,2,3,2,2};...
0f40: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 61 vector <int> a
0f50: 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 61 (a_, a_+sizeof(a
0f60: 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 29 3b _)/sizeof(*a_));
0f70: 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 7b ...int b_[] = {
0f80: 32 2c 33 2c 34 2c 35 2c 36 7d 3b 0d 0a 09 20 20 2,3,4,5,6};...
0f90: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 28 62 vector <int> b(b
0fa0: 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 28 62 5f 29 _, b_+sizeof(b_)
0fb0: 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 29 3b 20 0d /sizeof(*b_)); .
0fc0: 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e 33 ..double _ = 0.3
0fd0: 37 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 75; ..END..CASE(
0fe0: 33 29 0d 0a 09 69 6e 74 20 61 5f 5b 5d 20 3d 20 3)...int a_[] =
0ff0: 7b 31 2c 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 {1,2,3,4,5,6,7,8
1000: 2c 39 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 ,9};... vector
1010: 3c 69 6e 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 <int> a(a_, a_+s
1020: 69 7a 65 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 izeof(a_)/sizeof
1030: 28 2a 61 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 (*a_)); ...int b
1040: 5f 5b 5d 20 3d 20 7b 32 2c 33 2c 34 2c 35 2c 36 _[] = {2,3,4,5,6
1050: 2c 37 2c 38 2c 39 2c 31 30 7d 3b 0d 0a 09 20 20 ,7,8,9,10};...
1060: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 28 62 vector <int> b(b
1070: 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 28 62 5f 29 _, b_+sizeof(b_)
1080: 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 29 3b 20 0d /sizeof(*b_)); .
1090: 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e 34 ..double _ = 0.4
10a0: 31 37 39 36 38 37 35 3b 20 0d 0a 45 4e 44 0d 0a 1796875; ..END..
10b0: 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 61 5f CASE(4)...int a_
10c0: 5b 5d 20 3d 20 7b 31 2c 31 2c 31 2c 31 2c 31 2c [] = {1,1,1,1,1,
10d0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
10e0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
10f0: 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 31 2c 1,1,1,1,1,1,1,1,
1100: 31 2c 31 2c 31 2c 31 2c 31 2c 31 7d 3b 0d 0a 09 1,1,1,1,1,1};...
1110: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 61 vector <int> a
1120: 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 61 (a_, a_+sizeof(a
1130: 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 29 3b _)/sizeof(*a_));
1140: 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 7b ...int b_[] = {
1150: 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 2,3,4,5,6,7,8,9,
1160: 31 30 2c 31 31 2c 31 32 2c 31 33 2c 31 34 2c 31 10,11,12,13,14,1
1170: 35 2c 31 36 2c 31 37 2c 31 38 2c 31 39 2c 32 30 5,16,17,18,19,20
1180: 2c 32 31 2c 32 32 2c 32 33 2c 32 34 2c 32 35 2c ,21,22,23,24,25,
1190: 32 36 2c 32 37 2c 32 38 2c 32 39 2c 33 30 2c 33 26,27,28,29,30,3
11a0: 31 2c 33 32 2c 33 33 2c 33 34 2c 33 35 2c 33 36 1,32,33,34,35,36
11b0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 };... vector <i
11c0: 6e 74 3e 20 62 28 62 5f 2c 20 62 5f 2b 73 69 7a nt> b(b_, b_+siz
11d0: 65 6f 66 28 62 5f 29 2f 73 69 7a 65 6f 66 28 2a eof(b_)/sizeof(*
11e0: 62 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 b_)); ...double
11f0: 5f 20 3d 20 31 35 2e 35 30 30 30 30 30 30 30 31 _ = 15.500000001
1200: 30 37 36 38 34 32 3b 20 0d 0a 45 4e 44 0d 0a 43 076842; ..END..C
1210: 41 53 45 28 35 29 0d 0a 09 69 6e 74 20 61 5f 5b ASE(5)...int a_[
1220: 5d 20 3d 20 7b 31 30 2c 20 37 2c 20 32 2c 20 35 ] = {10, 7, 2, 5
1230: 2c 20 36 2c 20 32 2c 20 34 2c 20 39 2c 20 37 7d , 6, 2, 4, 9, 7}
1240: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
1250: 74 3e 20 61 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 t> a(a_, a_+size
1260: 6f 66 28 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 of(a_)/sizeof(*a
1270: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d _)); ...int b_[]
1280: 20 3d 20 7b 38 2c 20 31 30 2c 20 31 30 2c 20 34 = {8, 10, 10, 4
1290: 2c 20 31 2c 20 36 2c 20 32 2c 20 32 2c 20 33 7d , 1, 6, 2, 2, 3}
12a0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
12b0: 74 3e 20 62 28 62 5f 2c 20 62 5f 2b 73 69 7a 65 t> b(b_, b_+size
12c0: 6f 66 28 62 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 of(b_)/sizeof(*b
12d0: 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f _)); ...double _
12e0: 20 3d 20 30 2e 36 34 36 34 38 34 33 37 35 3b 20 = 0.646484375;
12f0: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 29 0d 0a ..END..CASE(6)..
1300: 09 69 6e 74 20 61 5f 5b 5d 20 3d 20 7b 31 2c 32 .int a_[] = {1,2
1310: 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 2c 31 ,3,4,5,6,7,8,9,1
1320: 30 2c 31 31 2c 31 32 2c 31 33 2c 31 34 2c 31 35 0,11,12,13,14,15
1330: 2c 31 36 2c 31 37 2c 31 38 2c 31 39 2c 32 30 2c ,16,17,18,19,20,
1340: 32 31 2c 32 32 2c 32 33 2c 32 34 2c 32 35 2c 32 21,22,23,24,25,2
1350: 36 2c 32 37 2c 32 38 2c 32 39 2c 33 30 2c 33 31 6,27,28,29,30,31
1360: 2c 33 32 2c 33 33 2c 33 34 2c 33 35 7d 3b 0d 0a ,32,33,34,35};..
1370: 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 . vector <int>
1380: 61 28 61 5f 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 a(a_, a_+sizeof(
1390: 61 5f 29 2f 73 69 7a 65 6f 66 28 2a 61 5f 29 29 a_)/sizeof(*a_))
13a0: 3b 20 0d 0a 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 ; ...int b_[] =
13b0: 7b 32 2c 33 2c 34 2c 35 2c 36 2c 37 2c 38 2c 39 {2,3,4,5,6,7,8,9
13c0: 2c 31 30 2c 31 31 2c 31 32 2c 31 33 2c 31 34 2c ,10,11,12,13,14,
13d0: 31 35 2c 31 36 2c 31 37 2c 31 38 2c 31 39 2c 32 15,16,17,18,19,2
13e0: 30 2c 32 31 2c 32 32 2c 32 33 2c 32 34 2c 32 35 0,21,22,23,24,25
13f0: 2c 32 36 2c 32 37 2c 32 38 2c 32 39 2c 33 30 2c ,26,27,28,29,30,
1400: 33 31 2c 33 32 2c 33 33 2c 33 34 2c 33 35 2c 33 31,32,33,34,35,3
1410: 36 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 6};... vector <
1420: 69 6e 74 3e 20 62 28 62 5f 2c 20 62 5f 2b 73 69 int> b(b_, b_+si
1430: 7a 65 6f 66 28 62 5f 29 2f 73 69 7a 65 6f 66 28 zeof(b_)/sizeof(
1440: 2a 62 5f 29 29 3b 20 0d 0a 09 64 6f 75 62 6c 65 *b_)); ...double
1450: 20 5f 20 3d 20 2d 31 3b 20 0d 0a 45 4e 44 0d 0a _ = -1; ..END..
1460: 2f 2a 0d 0a 43 41 53 45 28 37 29 0d 0a 09 69 6e /*..CASE(7)...in
1470: 74 20 61 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 t a_[] = ;... v
1480: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 61 28 61 5f ector <int> a(a_
1490: 2c 20 61 5f 2b 73 69 7a 65 6f 66 28 61 5f 29 2f , a_+sizeof(a_)/
14a0: 73 69 7a 65 6f 66 28 2a 61 5f 29 29 3b 20 0d 0a sizeof(*a_)); ..
14b0: 09 69 6e 74 20 62 5f 5b 5d 20 3d 20 3b 0d 0a 09 .int b_[] = ;...
14c0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 62 vector <int> b
14d0: 28 62 5f 2c 20 62 5f 2b 73 69 7a 65 6f 66 28 62 (b_, b_+sizeof(b
14e0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 5f 29 29 3b _)/sizeof(*b_));
14f0: 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 3b ...double _ = ;
1500: 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f ..END..*/..}../
1510: 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a / END CUT HERE..