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 23 69 6e 63 6c 75 64 65 20 sert>..#include
0140: 3c 63 73 74 72 69 6e 67 3e 0d 0a 75 73 69 6e 67 <cstring>..using
0150: 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d namespace std;.
0160: 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f .typedef long lo
0170: 6e 67 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 ng LL;..typedef
0180: 63 6f 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 complex<double>
0190: 43 4d 50 3b 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 CMP;....template
01a0: 3c 74 79 70 65 6e 61 6d 65 20 54 3e 0d 0a 73 74 <typename T>..st
01b0: 72 75 63 74 20 44 50 32 0d 0a 7b 0d 0a 09 69 6e ruct DP2..{...in
01c0: 74 20 4e 31 2c 20 4e 32 3b 0d 0a 09 76 65 63 74 t N1, N2;...vect
01d0: 6f 72 3c 54 3e 20 64 61 74 61 3b 0d 0a 09 44 50 or<T> data;...DP
01e0: 32 28 29 7b 7d 0d 0a 09 44 50 32 28 69 6e 74 20 2(){}...DP2(int
01f0: 4e 31 2c 20 69 6e 74 20 4e 32 2c 20 63 6f 6e 73 N1, int N2, cons
0200: 74 20 54 26 20 74 20 3d 20 54 28 29 29 0d 0a 09 t T& t = T())...
0210: 09 3a 20 4e 31 28 4e 31 29 2c 20 4e 32 28 4e 32 .: N1(N1), N2(N2
0220: 29 2c 20 64 61 74 61 28 4e 31 2a 4e 32 2c 20 74 ), data(N1*N2, t
0230: 29 20 7b 20 61 73 73 65 72 74 28 64 61 74 61 2e ) { assert(data.
0240: 73 69 7a 65 28 29 2a 73 69 7a 65 6f 66 28 54 29 size()*sizeof(T)
0250: 3c 28 31 3c 3c 32 36 29 29 3b 20 7d 0d 0a 09 54 <(1<<26)); }...T
0260: 26 20 6f 70 65 72 61 74 6f 72 28 29 28 69 6e 74 & operator()(int
0270: 20 69 31 2c 20 69 6e 74 20 69 32 29 0d 0a 09 09 i1, int i2)....
0280: 7b 20 72 65 74 75 72 6e 20 64 61 74 61 5b 20 28 { return data[ (
0290: 69 31 2a 4e 32 29 2b 69 32 20 5d 3b 20 7d 0d 0a i1*N2)+i2 ]; }..
02a0: 09 76 6f 69 64 20 73 77 61 70 28 44 50 32 26 20 .void swap(DP2&
02b0: 72 68 73 29 0d 0a 09 09 7b 20 64 61 74 61 2e 73 rhs)....{ data.s
02c0: 77 61 70 28 72 68 73 2e 64 61 74 61 29 3b 20 7d wap(rhs.data); }
02d0: 0d 0a 7d 3b 0d 0a 0d 0a 63 6c 61 73 73 20 46 72 ..};....class Fr
02e0: 69 65 6e 64 54 6f 75 72 20 7b 20 70 75 62 6c 69 iendTour { publi
02f0: 63 3a 0d 0a 09 64 6f 75 62 6c 65 20 74 6f 75 72 c:...double tour
0300: 50 72 6f 62 61 62 69 6c 69 74 79 28 76 65 63 74 Probability(vect
0310: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 66 72 69 65 or <string> frie
0320: 6e 64 73 2c 20 69 6e 74 20 4b 29 20 0d 0a 09 7b nds, int K) ...{
0330: 0d 0a 09 09 69 6e 74 20 4e 20 3d 20 28 69 6e 74 ....int N = (int
0340: 29 66 72 69 65 6e 64 73 2e 73 69 7a 65 28 29 3b )friends.size();
0350: 0d 0a 09 09 76 65 63 74 6f 72 3c 20 76 65 63 74 ....vector< vect
0360: 6f 72 3c 69 6e 74 3e 20 3e 20 66 28 4e 29 3b 0d or<int> > f(N);.
0370: 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 ...for(int i=0;
0380: 69 3c 4e 3b 20 2b 2b 69 29 0d 0a 09 09 7b 0d 0a i<N; ++i)....{..
0390: 09 09 09 73 74 72 69 6e 67 73 74 72 65 61 6d 20 ...stringstream
03a0: 73 69 6e 28 20 66 72 69 65 6e 64 73 5b 69 5d 20 sin( friends[i]
03b0: 29 3b 0d 0a 09 09 09 66 6f 72 28 69 6e 74 20 76 );.....for(int v
03c0: 3b 20 73 69 6e 3e 3e 76 3b 20 29 0d 0a 09 09 09 ; sin>>v; ).....
03d0: 09 66 5b 69 5d 2e 70 75 73 68 5f 62 61 63 6b 28 .f[i].push_back(
03e0: 76 2d 31 29 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 v-1);....}......
03f0: 6d 61 70 3c 69 6e 74 2c 69 6e 74 3e 20 72 65 6e map<int,int> ren
0400: 61 6d 65 3b 0d 0a 09 09 72 65 6e 61 6d 65 5b 30 ame;....rename[0
0410: 5d 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 69 6e ] = 0;....for(in
0420: 74 20 6b 3d 30 3b 20 6b 3c 66 5b 30 5d 2e 73 69 t k=0; k<f[0].si
0430: 7a 65 28 29 3b 20 2b 2b 6b 29 0d 0a 09 09 7b 0d ze(); ++k)....{.
0440: 0a 09 09 09 69 6e 74 20 6e 65 77 69 64 20 3d 20 ....int newid =
0450: 72 65 6e 61 6d 65 2e 73 69 7a 65 28 29 3b 0d 0a rename.size();..
0460: 09 09 09 72 65 6e 61 6d 65 5b 66 5b 30 5d 5b 6b ...rename[f[0][k
0470: 5d 5d 20 3d 20 6e 65 77 69 64 3b 0d 0a 09 09 7d ]] = newid;....}
0480: 0d 0a 0d 0a 09 09 76 65 63 74 6f 72 3c 20 76 65 ......vector< ve
0490: 63 74 6f 72 3c 69 6e 74 3e 20 3e 20 66 66 28 72 ctor<int> > ff(r
04a0: 65 6e 61 6d 65 2e 73 69 7a 65 28 29 29 3b 0d 0a ename.size());..
04b0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
04c0: 3c 4e 3b 20 2b 2b 69 29 0d 0a 09 09 09 69 66 28 <N; ++i).....if(
04d0: 20 72 65 6e 61 6d 65 2e 63 6f 75 6e 74 28 69 29 rename.count(i)
04e0: 20 29 0d 0a 09 09 09 7b 0d 0a 09 09 09 09 69 6e ).....{......in
04f0: 74 20 6b 20 3d 20 72 65 6e 61 6d 65 5b 69 5d 3b t k = rename[i];
0500: 0d 0a 09 09 09 09 66 6f 72 28 69 6e 74 20 6a 3d ......for(int j=
0510: 30 3b 20 6a 3c 66 5b 69 5d 2e 73 69 7a 65 28 29 0; j<f[i].size()
0520: 3b 20 2b 2b 6a 29 0d 0a 09 09 09 09 09 69 66 28 ; ++j).......if(
0530: 20 66 5b 69 5d 5b 6a 5d 21 3d 30 20 26 26 20 72 f[i][j]!=0 && r
0540: 65 6e 61 6d 65 2e 63 6f 75 6e 74 28 66 5b 69 5d ename.count(f[i]
0550: 5b 6a 5d 29 20 29 0d 0a 09 09 09 09 09 09 66 66 [j]) )........ff
0560: 5b 6b 5d 2e 70 75 73 68 5f 62 61 63 6b 28 20 72 [k].push_back( r
0570: 65 6e 61 6d 65 5b 66 5b 69 5d 5b 6a 5d 5d 20 29 ename[f[i][j]] )
0580: 3b 0d 0a 09 09 09 09 09 65 6c 73 65 0d 0a 09 09 ;.......else....
0590: 09 09 09 09 66 66 5b 6b 5d 2e 70 75 73 68 5f 62 ....ff[k].push_b
05a0: 61 63 6b 28 20 2d 31 20 29 3b 0d 0a 09 09 09 7d ack( -1 );.....}
05b0: 0d 0a 09 09 72 65 74 75 72 6e 20 73 6f 6c 76 65 ....return solve
05c0: 28 66 66 2c 20 4b 29 3b 0d 0a 09 7d 0d 0a 0d 0a (ff, K);...}....
05d0: 09 64 6f 75 62 6c 65 20 73 6f 6c 76 65 28 76 65 .double solve(ve
05e0: 63 74 6f 72 3c 76 65 63 74 6f 72 3c 69 6e 74 3e ctor<vector<int>
05f0: 20 3e 26 20 66 2c 20 69 6e 74 20 4b 29 0d 0a 09 >& f, int K)...
0600: 7b 0d 0a 09 09 6d 65 6d 6f 20 3d 20 44 50 32 3c {....memo = DP2<
0610: 64 6f 75 62 6c 65 3e 28 66 2e 73 69 7a 65 28 29 double>(f.size()
0620: 2c 20 31 3c 3c 66 2e 73 69 7a 65 28 29 2c 20 2d , 1<<f.size(), -
0630: 31 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 72 65 1);....return re
0640: 63 28 66 2c 20 4b 2c 20 30 2c 20 31 29 3b 0d 0a c(f, K, 0, 1);..
0650: 09 7d 0d 0a 0d 0a 09 64 6f 75 62 6c 65 20 43 28 .}.....double C(
0660: 69 6e 74 20 4e 2c 20 69 6e 74 20 4b 29 0d 0a 09 int N, int K)...
0670: 7b 0d 0a 09 09 64 6f 75 62 6c 65 20 70 20 3d 20 {....double p =
0680: 31 2e 30 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 1.0;....for(int
0690: 69 3d 30 3b 20 69 3c 6d 69 6e 28 4b 2c 4e 2d 4b i=0; i<min(K,N-K
06a0: 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 70 20 3d 20 ); ++i).....p =
06b0: 70 20 2a 20 28 4e 2d 69 29 20 2f 20 28 31 2b 69 p * (N-i) / (1+i
06c0: 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 70 3b 0d );....return p;.
06d0: 0a 09 7d 0d 0a 0d 0a 09 44 50 32 3c 64 6f 75 62 ..}.....DP2<doub
06e0: 6c 65 3e 20 6d 65 6d 6f 3b 0d 0a 09 64 6f 75 62 le> memo;...doub
06f0: 6c 65 20 72 65 63 28 76 65 63 74 6f 72 3c 76 65 le rec(vector<ve
0700: 63 74 6f 72 3c 69 6e 74 3e 20 3e 26 20 66 2c 20 ctor<int> >& f,
0710: 69 6e 74 20 4b 2c 20 69 6e 74 20 76 2c 20 69 6e int K, int v, in
0720: 74 20 6d 61 73 6b 29 0d 0a 09 7b 0d 0a 09 09 69 t mask)...{....i
0730: 66 28 20 6d 65 6d 6f 28 76 2c 6d 61 73 6b 29 20 f( memo(v,mask)
0740: 21 3d 20 2d 31 20 29 0d 0a 09 09 09 72 65 74 75 != -1 ).....retu
0750: 72 6e 20 6d 65 6d 6f 28 76 2c 6d 61 73 6b 29 3b rn memo(v,mask);
0760: 0d 0a 0d 0a 09 09 69 66 28 20 6d 61 73 6b 20 3d ......if( mask =
0770: 3d 20 28 31 3c 3c 66 2e 73 69 7a 65 28 29 29 2d = (1<<f.size())-
0780: 31 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 31 1 ).....return 1
0790: 2e 30 3b 0d 0a 0d 0a 09 09 76 65 63 74 6f 72 3c .0;......vector<
07a0: 64 6f 75 62 6c 65 3e 20 6e 78 74 3b 0d 0a 09 09 double> nxt;....
07b0: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 66 for(int i=0; i<f
07c0: 5b 76 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 [v].size(); ++i)
07d0: 0d 0a 09 09 09 69 66 28 20 66 5b 76 5d 5b 69 5d .....if( f[v][i]
07e0: 3d 3d 2d 31 20 7c 7c 20 28 6d 61 73 6b 20 26 20 ==-1 || (mask &
07f0: 28 31 3c 3c 66 5b 76 5d 5b 69 5d 29 29 20 29 0d (1<<f[v][i])) ).
0800: 0a 09 09 09 09 6e 78 74 2e 70 75 73 68 5f 62 61 .....nxt.push_ba
0810: 63 6b 28 30 29 3b 0d 0a 09 09 09 65 6c 73 65 0d ck(0);.....else.
0820: 0a 09 09 09 09 6e 78 74 2e 70 75 73 68 5f 62 61 .....nxt.push_ba
0830: 63 6b 28 20 72 65 63 28 66 2c 4b 2c 66 5b 76 5d ck( rec(f,K,f[v]
0840: 5b 69 5d 2c 6d 61 73 6b 7c 28 31 3c 3c 66 5b 76 [i],mask|(1<<f[v
0850: 5d 5b 69 5d 29 29 20 29 3b 0d 0a 09 09 73 6f 72 ][i])) );....sor
0860: 74 28 6e 78 74 2e 72 62 65 67 69 6e 28 29 2c 20 t(nxt.rbegin(),
0870: 6e 78 74 2e 72 65 6e 64 28 29 29 3b 0d 0a 09 09 nxt.rend());....
0880: 69 6e 74 20 4e 20 3d 20 6e 78 74 2e 73 69 7a 65 int N = nxt.size
0890: 28 29 3b 0d 0a 09 09 69 66 28 20 4e 20 3d 3d 20 ();....if( N ==
08a0: 30 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 6d 0 ).....return m
08b0: 65 6d 6f 28 76 2c 6d 61 73 6b 29 20 3d 20 30 2e emo(v,mask) = 0.
08c0: 30 3b 0d 0a 0d 0a 09 09 69 66 28 20 4e 20 3c 3d 0;......if( N <=
08d0: 20 4b 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 K ).....return
08e0: 6d 65 6d 6f 28 76 2c 6d 61 73 6b 29 20 3d 20 6e memo(v,mask) = n
08f0: 78 74 5b 30 5d 3b 0d 0a 0d 0a 09 09 64 6f 75 62 xt[0];......doub
0900: 6c 65 20 70 20 3d 20 30 2e 30 3b 0d 0a 09 09 66 le p = 0.0;....f
0910: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 78 or(int i=0; i<nx
0920: 74 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b t.size(); ++i) {
0930: 0d 0a 09 09 09 69 66 28 20 4e 2d 31 2d 69 20 3c .....if( N-1-i <
0940: 20 4b 20 29 20 7b 0d 0a 09 09 09 09 70 20 2b 3d K ) {......p +=
0950: 20 43 28 4e 2d 69 2c 4b 29 20 2f 20 43 28 4e 2c C(N-i,K) / C(N,
0960: 4b 29 20 2a 20 6e 78 74 5b 69 5d 3b 0d 0a 09 09 K) * nxt[i];....
0970: 09 09 62 72 65 61 6b 3b 0d 0a 09 09 09 7d 0d 0a ..break;.....}..
0980: 09 09 09 70 20 2b 3d 20 28 43 28 4e 2d 69 2c 4b ...p += (C(N-i,K
0990: 29 20 2d 20 43 28 4e 2d 31 2d 69 2c 4b 29 29 20 ) - C(N-1-i,K))
09a0: 2f 20 43 28 4e 2c 4b 29 20 2a 20 6e 78 74 5b 69 / C(N,K) * nxt[i
09b0: 5d 3b 0d 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 ];....}....retur
09c0: 6e 20 6d 65 6d 6f 28 76 2c 6d 61 73 6b 29 20 3d n memo(v,mask) =
09d0: 20 70 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f p;...}..};..../
09e0: 2f 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 / BEGIN CUT HERE
09f0: 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d ..#include <ctim
0a00: 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 e>..double start
0a10: 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 _time; string ti
0a20: 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e mer().. { ostrin
0a30: 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c gstream os; os <
0a40: 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 < " (" << int((c
0a50: 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d lock()-start_tim
0a60: 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 e)/CLOCKS_PER_SE
0a70: 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 C*1000) << " mse
0a80: 63 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 c)"; return os.s
0a90: 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 tr(); }..templat
0aa0: 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 e<typename T> os
0ab0: 74 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c tream& operator<
0ac0: 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 <(ostream& os, c
0ad0: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 onst vector<T>&
0ae0: 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 v).. { os << "{
0af0: 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e ";.. for(typen
0b00: 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 ame vector<T>::c
0b10: 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 onst_iterator it
0b20: 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d =v.begin(); it!=
0b30: 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a v.end(); ++it)..
0b40: 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c os << '\"' <<
0b50: 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 *it << '\"' <<
0b60: 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f (it+1==v.end() ?
0b70: 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 "" : ", "); os
0b80: 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 << " }"; return
0b90: 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 os; }..void veri
0ba0: 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 64 6f fy_case(const do
0bb0: 75 62 6c 65 26 20 45 78 70 65 63 74 65 64 2c 20 uble& Expected,
0bc0: 63 6f 6e 73 74 20 64 6f 75 62 6c 65 26 20 52 65 const double& Re
0bd0: 63 65 69 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c ceived) {.. bool
0be0: 20 6f 6b 20 3d 20 28 61 62 73 28 45 78 70 65 63 ok = (abs(Expec
0bf0: 74 65 64 20 2d 20 52 65 63 65 69 76 65 64 29 20 ted - Received)
0c00: 3c 20 31 65 2d 39 29 3b 0d 0a 20 69 66 28 6f 6b < 1e-9);.. if(ok
0c10: 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 ) cerr << "PASSE
0c20: 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c D" << timer() <<
0c30: 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 endl; else { c
0c40: 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 err << "FAILED"
0c50: 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e << timer() << en
0c60: 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c dl;.. cerr << "\
0c70: 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 to: \"" << Expec
0c80: 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 ted << '\"' << e
0c90: 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 ndl << "\tx: \""
0ca0: 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 << Received <<
0cb0: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 '\"' << endl; }
0cc0: 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 }..#define CASE(
0cd0: 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 N) {cerr << "Tes
0ce0: 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c t Case #" << N <
0cf0: 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 < "..." << flush
0d00: 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f ; start_time=clo
0d10: 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 ck();..#define E
0d20: 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 ND. verify_case(
0d30: 5f 2c 20 46 72 69 65 6e 64 54 6f 75 72 28 29 2e _, FriendTour().
0d40: 74 6f 75 72 50 72 6f 62 61 62 69 6c 69 74 79 28 tourProbability(
0d50: 66 72 69 65 6e 64 73 2c 20 4b 29 29 3b 7d 0d 0a friends, K));}..
0d60: 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 int main(){....C
0d70: 41 53 45 28 30 29 0d 0a 09 73 74 72 69 6e 67 20 ASE(0)...string
0d80: 66 72 69 65 6e 64 73 5f 5b 5d 20 3d 20 7b 22 32 friends_[] = {"2
0d90: 20 33 20 34 22 2c 0d 0a 20 22 31 20 33 20 34 22 3 4",.. "1 3 4"
0da0: 2c 0d 0a 20 22 31 20 32 20 34 22 2c 0d 0a 20 22 ,.. "1 2 4",.. "
0db0: 31 20 32 20 33 22 7d 3b 0d 0a 09 20 20 76 65 63 1 2 3"};... vec
0dc0: 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 66 72 69 tor <string> fri
0dd0: 65 6e 64 73 28 66 72 69 65 6e 64 73 5f 2c 20 66 ends(friends_, f
0de0: 72 69 65 6e 64 73 5f 2b 73 69 7a 65 6f 66 28 66 riends_+sizeof(f
0df0: 72 69 65 6e 64 73 5f 29 2f 73 69 7a 65 6f 66 28 riends_)/sizeof(
0e00: 2a 66 72 69 65 6e 64 73 5f 29 29 3b 20 0d 0a 09 *friends_)); ...
0e10: 69 6e 74 20 4b 20 3d 20 31 3b 20 0d 0a 09 64 6f int K = 1; ...do
0e20: 75 62 6c 65 20 5f 20 3d 20 30 2e 32 32 32 32 32 uble _ = 0.22222
0e30: 32 32 32 32 32 32 32 32 32 32 32 3b 20 0d 0a 45 22222222222; ..E
0e40: 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 73 74 ND..CASE(1)...st
0e50: 72 69 6e 67 20 66 72 69 65 6e 64 73 5f 5b 5d 20 ring friends_[]
0e60: 3d 20 7b 22 32 20 33 20 34 22 2c 0d 0a 20 22 31 = {"2 3 4",.. "1
0e70: 20 33 20 34 22 2c 0d 0a 20 22 31 20 32 20 34 22 3 4",.. "1 2 4"
0e80: 2c 0d 0a 20 22 31 20 32 20 33 22 7d 3b 0d 0a 09 ,.. "1 2 3"};...
0e90: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
0ea0: 3e 20 66 72 69 65 6e 64 73 28 66 72 69 65 6e 64 > friends(friend
0eb0: 73 5f 2c 20 66 72 69 65 6e 64 73 5f 2b 73 69 7a s_, friends_+siz
0ec0: 65 6f 66 28 66 72 69 65 6e 64 73 5f 29 2f 73 69 eof(friends_)/si
0ed0: 7a 65 6f 66 28 2a 66 72 69 65 6e 64 73 5f 29 29 zeof(*friends_))
0ee0: 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 32 3b 20 ; ...int K = 2;
0ef0: 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e ...double _ = 0.
0f00: 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 6666666666666666
0f10: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 ; ..END..CASE(2)
0f20: 0d 0a 09 73 74 72 69 6e 67 20 66 72 69 65 6e 64 ...string friend
0f30: 73 5f 5b 5d 20 3d 20 7b 22 33 20 32 20 34 22 2c s_[] = {"3 2 4",
0f40: 0d 0a 20 22 33 20 35 20 31 22 2c 0d 0a 20 22 35 .. "3 5 1",.. "5
0f50: 20 32 20 31 20 34 22 2c 0d 0a 20 22 33 20 31 20 2 1 4",.. "3 1
0f60: 35 22 2c 0d 0a 20 22 33 20 32 20 34 22 7d 3b 0d 5",.. "3 2 4"};.
0f70: 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .. vector <stri
0f80: 6e 67 3e 20 66 72 69 65 6e 64 73 28 66 72 69 65 ng> friends(frie
0f90: 6e 64 73 5f 2c 20 66 72 69 65 6e 64 73 5f 2b 73 nds_, friends_+s
0fa0: 69 7a 65 6f 66 28 66 72 69 65 6e 64 73 5f 29 2f izeof(friends_)/
0fb0: 73 69 7a 65 6f 66 28 2a 66 72 69 65 6e 64 73 5f sizeof(*friends_
0fc0: 29 29 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 32 )); ...int K = 2
0fd0: 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 ; ...double _ =
0fe0: 30 2e 33 33 33 33 33 33 33 33 33 33 33 33 33 33 0.33333333333333
0ff0: 33 33 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33; ..END..CASE(
1000: 33 29 0d 0a 09 73 74 72 69 6e 67 20 66 72 69 65 3)...string frie
1010: 6e 64 73 5f 5b 5d 20 3d 20 7b 22 33 20 32 20 34 nds_[] = {"3 2 4
1020: 22 2c 0d 0a 20 22 33 20 35 20 31 22 2c 0d 0a 20 ",.. "3 5 1",..
1030: 22 35 20 32 20 31 20 34 22 2c 0d 0a 20 22 33 20 "5 2 1 4",.. "3
1040: 31 20 35 20 36 22 2c 0d 0a 20 22 33 20 32 20 34 1 5 6",.. "3 2 4
1050: 22 2c 0d 0a 20 22 34 22 7d 0d 0a 3b 0d 0a 09 20 ",.. "4"}..;...
1060: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
1070: 20 66 72 69 65 6e 64 73 28 66 72 69 65 6e 64 73 friends(friends
1080: 5f 2c 20 66 72 69 65 6e 64 73 5f 2b 73 69 7a 65 _, friends_+size
1090: 6f 66 28 66 72 69 65 6e 64 73 5f 29 2f 73 69 7a of(friends_)/siz
10a0: 65 6f 66 28 2a 66 72 69 65 6e 64 73 5f 29 29 3b eof(*friends_));
10b0: 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 32 3b 20 0d ...int K = 2; .
10c0: 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 30 2e 33 ..double _ = 0.3
10d0: 30 35 35 35 35 35 35 35 35 35 35 35 35 35 36 3b 055555555555556;
10e0: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 34 29 0d ..END..CASE(4).
10f0: 0a 09 73 74 72 69 6e 67 20 66 72 69 65 6e 64 73 ..string friends
1100: 5f 5b 5d 20 3d 20 7b 22 36 20 35 20 34 20 32 22 _[] = {"6 5 4 2"
1110: 2c 0d 0a 20 22 31 20 36 20 33 20 35 22 2c 0d 0a ,.. "1 6 3 5",..
1120: 20 22 35 20 34 20 32 22 2c 0d 0a 20 22 33 20 31 "5 4 2",.. "3 1
1130: 20 35 22 2c 0d 0a 20 22 32 20 34 20 33 20 31 20 5",.. "2 4 3 1
1140: 36 22 2c 0d 0a 20 22 31 20 32 20 35 22 7d 3b 0d 6",.. "1 2 5"};.
1150: 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .. vector <stri
1160: 6e 67 3e 20 66 72 69 65 6e 64 73 28 66 72 69 65 ng> friends(frie
1170: 6e 64 73 5f 2c 20 66 72 69 65 6e 64 73 5f 2b 73 nds_, friends_+s
1180: 69 7a 65 6f 66 28 66 72 69 65 6e 64 73 5f 29 2f izeof(friends_)/
1190: 73 69 7a 65 6f 66 28 2a 66 72 69 65 6e 64 73 5f sizeof(*friends_
11a0: 29 29 3b 20 0d 0a 09 69 6e 74 20 4b 20 3d 20 33 )); ...int K = 3
11b0: 3b 20 0d 0a 09 64 6f 75 62 6c 65 20 5f 20 3d 20 ; ...double _ =
11c0: 30 2e 37 33 31 32 35 3b 20 0d 0a 45 4e 44 0d 0a 0.73125; ..END..
11d0: 43 41 53 45 28 35 29 0d 0a 09 73 74 72 69 6e 67 CASE(5)...string
11e0: 20 66 72 69 65 6e 64 73 5f 5b 5d 20 3d 20 7b 22 friends_[] = {"
11f0: 32 20 33 20 34 20 35 20 36 20 37 20 38 20 39 20 2 3 4 5 6 7 8 9
1200: 31 30 20 31 31 20 31 32 20 31 33 20 31 34 20 31 10 11 12 13 14 1
1210: 35 20 31 36 22 2c 20 22 31 20 33 20 34 20 35 20 5 16", "1 3 4 5
1220: 36 20 37 20 38 20 39 20 31 30 20 31 31 20 31 32 6 7 8 9 10 11 12
1230: 20 31 33 20 31 34 20 31 35 20 31 36 22 2c 20 22 13 14 15 16", "
1240: 31 20 32 20 34 20 35 20 36 20 37 20 38 20 39 20 1 2 4 5 6 7 8 9
1250: 31 30 20 31 31 20 31 32 20 31 33 20 31 34 20 31 10 11 12 13 14 1
1260: 35 20 31 36 22 2c 20 22 31 20 32 20 33 20 35 20 5 16", "1 2 3 5
1270: 36 20 37 20 38 20 39 20 31 30 20 31 31 20 31 32 6 7 8 9 10 11 12
1280: 20 31 33 20 31 34 20 31 35 20 31 36 22 2c 20 22 13 14 15 16", "
1290: 31 20 32 20 33 20 34 20 36 20 37 20 38 20 39 20 1 2 3 4 6 7 8 9
12a0: 31 30 20 31 31 20 31 32 20 31 33 20 31 34 20 31 10 11 12 13 14 1
12b0: 35 20 31 36 22 2c 20 22 31 20 32 20 33 20 34 20 5 16", "1 2 3 4
12c0: 35 20 37 20 38 20 39 20 31 30 20 31 31 20 31 32 5 7 8 9 10 11 12
12d0: 20 31 33 20 31 34 20 31 35 20 31 36 22 2c 20 22 13 14 15 16", "
12e0: 31 20 32 20 33 20 34 20 35 20 36 20 38 20 39 20 1 2 3 4 5 6 8 9
12f0: 31 30 20 31 31 20 31 32 20 31 33 20 31 34 20 31 10 11 12 13 14 1
1300: 35 20 31 36 22 2c 20 22 31 20 32 20 33 20 34 20 5 16", "1 2 3 4
1310: 35 20 36 20 37 20 39 20 31 30 20 31 31 20 31 32 5 6 7 9 10 11 12
1320: 20 31 33 20 31 34 20 31 35 20 31 36 22 2c 20 22 13 14 15 16", "
1330: 31 20 32 20 33 20 34 20 35 20 36 20 37 20 38 20 1 2 3 4 5 6 7 8
1340: 31 30 20 31 31 20 31 32 20 31 33 20 31 34 20 31 10 11 12 13 14 1
1350: 35 20 31 36 22 2c 20 22 31 20 32 20 33 20 34 20 5 16", "1 2 3 4
1360: 35 20 36 20 37 20 38 20 39 20 31 31 20 31 32 20 5 6 7 8 9 11 12
1370: 31 33 20 31 34 20 31 35 20 31 36 22 2c 20 22 31 13 14 15 16", "1
1380: 20 32 20 33 20 34 20 35 20 36 20 37 20 38 20 39 2 3 4 5 6 7 8 9
1390: 20 31 30 20 31 32 20 31 33 20 31 34 20 31 35 20 10 12 13 14 15
13a0: 31 36 22 2c 20 22 31 20 32 20 33 20 34 20 35 20 16", "1 2 3 4 5
13b0: 36 20 37 20 38 20 39 20 31 30 20 31 31 20 31 33 6 7 8 9 10 11 13
13c0: 20 31 34 20 31 35 20 31 36 22 2c 20 22 31 20 32 14 15 16", "1 2
13d0: 20 33 20 34 20 35 20 36 20 37 20 38 20 39 20 31 3 4 5 6 7 8 9 1
13e0: 30 20 31 31 20 31 32 20 31 34 20 31 35 20 31 36 0 11 12 14 15 16
13f0: 22 2c 20 22 31 20 32 20 33 20 34 20 35 20 36 20 ", "1 2 3 4 5 6
1400: 37 20 38 20 39 20 31 30 20 31 31 20 31 32 20 31 7 8 9 10 11 12 1
1410: 33 20 31 35 20 31 36 22 2c 20 22 31 20 32 20 33 3 15 16", "1 2 3
1420: 20 34 20 35 20 36 20 37 20 38 20 39 20 31 30 20 4 5 6 7 8 9 10
1430: 31 31 20 31 32 20 31 33 20 31 34 20 31 36 22 2c 11 12 13 14 16",
1440: 20 22 31 20 32 20 33 20 34 20 35 20 36 20 37 20 "1 2 3 4 5 6 7
1450: 38 20 39 20 31 30 20 31 31 20 31 32 20 31 33 20 8 9 10 11 12 13
1460: 31 34 20 31 35 22 7d 3b 0d 0a 09 20 20 76 65 63 14 15"};... vec
1470: 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 66 72 69 tor <string> fri
1480: 65 6e 64 73 28 66 72 69 65 6e 64 73 5f 2c 20 66 ends(friends_, f
1490: 72 69 65 6e 64 73 5f 2b 73 69 7a 65 6f 66 28 66 riends_+sizeof(f
14a0: 72 69 65 6e 64 73 5f 29 2f 73 69 7a 65 6f 66 28 riends_)/sizeof(
14b0: 2a 66 72 69 65 6e 64 73 5f 29 29 3b 20 0d 0a 09 *friends_)); ...
14c0: 69 6e 74 20 4b 20 3d 20 33 3b 20 0d 0a 09 64 6f int K = 3; ...do
14d0: 75 62 6c 65 20 5f 20 3d 20 30 2e 30 31 30 39 38 uble _ = 0.01098
14e0: 39 35 34 36 32 38 38 35 31 38 34 35 38 3b 20 0d 9546288518458; .
14f0: 0a 45 4e 44 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 .END..}..// END
1500: 43 55 54 20 48 45 52 45 0d 0a CUT HERE..