Artifact 8458c6f3c3bb106e6ed964b90ab84e200462b7ee:
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 63 6f 6d 70 ..#include <comp
00d0: 6c 65 78 3e 0d 0a 23 69 6e 63 6c 75 64 65 20 3c lex>..#include <
00e0: 71 75 65 75 65 3e 0d 0a 23 69 6e 63 6c 75 64 65 queue>..#include
00f0: 20 3c 73 74 61 63 6b 3e 0d 0a 23 69 6e 63 6c 75 <stack>..#inclu
0100: 64 65 20 3c 63 6d 61 74 68 3e 0d 0a 75 73 69 6e de <cmath>..usin
0110: 67 20 6e 61 6d 65 73 70 61 63 65 20 73 74 64 3b g namespace std;
0120: 0d 0a 74 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c ..typedef long l
0130: 6f 6e 67 20 4c 4c 3b 0d 0a 0d 0a 63 6c 61 73 73 ong LL;....class
0140: 20 46 61 69 72 54 6f 75 72 6e 61 6d 65 6e 74 0d FairTournament.
0150: 0a 7b 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 76 65 .{..public:...ve
0160: 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 6d 65 6d ctor<string> mem
0170: 6f 3b 0d 0a 0d 0a 09 73 74 72 69 6e 67 20 61 64 o;.....string ad
0180: 64 28 63 6f 6e 73 74 20 73 74 72 69 6e 67 26 20 d(const string&
0190: 61 2c 20 63 6f 6e 73 74 20 73 74 72 69 6e 67 26 a, const string&
01a0: 20 62 29 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 6e b)...{....int n
01b0: 20 3d 20 6d 61 78 28 61 2e 73 69 7a 65 28 29 2c = max(a.size(),
01c0: 20 62 2e 73 69 7a 65 28 29 29 2c 20 63 61 72 72 b.size()), carr
01d0: 79 3d 30 3b 0d 0a 09 09 73 74 72 69 6e 67 20 63 y=0;....string c
01e0: 28 6e 2c 20 27 30 27 29 3b 0d 0a 09 09 66 6f 72 (n, '0');....for
01f0: 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b 20 2b (int i=0; i<n; +
0200: 2b 69 29 20 7b 0d 0a 09 09 09 69 6e 74 20 78 20 +i) {.....int x
0210: 3d 20 28 61 2e 73 69 7a 65 28 29 3c 3d 69 20 3f = (a.size()<=i ?
0220: 20 30 20 3a 20 61 5b 61 2e 73 69 7a 65 28 29 2d 0 : a[a.size()-
0230: 31 2d 69 5d 2d 27 30 27 29 0d 0a 09 09 09 20 20 1-i]-'0').....
0240: 20 20 20 20 2b 20 28 62 2e 73 69 7a 65 28 29 3c + (b.size()<
0250: 3d 69 20 3f 20 30 20 3a 20 62 5b 62 2e 73 69 7a =i ? 0 : b[b.siz
0260: 65 28 29 2d 31 2d 69 5d 2d 27 30 27 29 20 2b 20 e()-1-i]-'0') +
0270: 63 61 72 72 79 3b 0d 0a 09 09 09 63 5b 6e 2d 31 carry;.....c[n-1
0280: 2d 69 5d 20 3d 20 63 68 61 72 28 27 30 27 2b 78 -i] = char('0'+x
0290: 25 31 30 29 3b 0d 0a 09 09 09 63 61 72 72 79 20 %10);.....carry
02a0: 3d 20 78 2f 31 30 3b 0d 0a 09 09 7d 0d 0a 09 09 = x/10;....}....
02b0: 69 66 28 20 63 61 72 72 79 20 29 20 63 20 3d 20 if( carry ) c =
02c0: 63 68 61 72 28 27 30 27 2b 63 61 72 72 79 29 2b char('0'+carry)+
02d0: 63 3b 0d 0a 09 09 72 65 74 75 72 6e 20 63 3b 0d c;....return c;.
02e0: 0a 09 7d 0d 0a 0d 0a 09 73 74 72 69 6e 67 20 63 ..}.....string c
02f0: 6f 75 6e 74 50 65 72 6d 75 74 61 74 69 6f 6e 73 ountPermutations
0300: 28 69 6e 74 20 6e 2c 20 69 6e 74 20 6b 29 20 0d (int n, int k) .
0310: 0a 09 7b 0d 0a 09 09 6d 65 6d 6f 2e 63 6c 65 61 ..{....memo.clea
0320: 72 28 29 3b 0d 0a 09 09 6d 65 6d 6f 2e 72 65 73 r();....memo.res
0330: 69 7a 65 28 6e 3c 3c 6b 2b 31 2b 6b 2c 20 22 58 ize(n<<k+1+k, "X
0340: 22 29 3b 0d 0a 0d 0a 09 09 69 6e 74 20 70 65 6e ");......int pen
0350: 64 69 6e 67 20 3d 20 28 31 3c 3c 6b 2b 31 29 20 ding = (1<<k+1)
0360: 2d 20 31 3b 20 2f 2f 20 30 62 30 30 31 31 31 20 - 1; // 0b00111
0370: 28 63 61 73 65 20 6b 3d 32 29 0d 0a 09 09 72 65 (case k=2)....re
0380: 74 75 72 6e 20 72 65 63 28 70 65 6e 64 69 6e 67 turn rec(pending
0390: 2c 20 30 2c 20 6e 2c 20 6b 29 3b 0d 0a 09 7d 0d , 0, n, k);...}.
03a0: 0a 0d 0a 09 73 74 72 69 6e 67 20 72 65 63 28 69 ....string rec(i
03b0: 6e 74 20 70 65 6e 64 69 6e 67 2c 20 69 6e 74 20 nt pending, int
03c0: 69 2c 20 69 6e 74 20 6e 2c 20 69 6e 74 20 6b 29 i, int n, int k)
03d0: 0d 0a 09 7b 0d 0a 09 09 69 66 28 20 69 20 3d 3d ...{....if( i ==
03e0: 20 6e 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 n ).....return
03f0: 22 31 22 3b 0d 0a 0d 0a 09 09 69 6e 74 20 6b 65 "1";......int ke
0400: 79 20 3d 20 28 69 3c 3c 6b 2b 31 2b 6b 29 20 7c y = (i<<k+1+k) |
0410: 20 70 65 6e 64 69 6e 67 3b 0d 0a 09 09 69 66 28 pending;....if(
0420: 20 6d 65 6d 6f 5b 6b 65 79 5d 21 3d 22 58 22 20 memo[key]!="X"
0430: 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 6d 65 6d ).....return mem
0440: 6f 5b 6b 65 79 5d 3b 0d 0a 0d 0a 09 09 73 74 72 o[key];......str
0450: 69 6e 67 20 73 75 6d 20 3d 20 22 22 3b 0d 0a 09 ing sum = "";...
0460: 09 66 6f 72 28 69 6e 74 20 6d 3d 31 2c 6a 3d 6b .for(int m=1,j=k
0470: 3b 20 6d 3c 3d 70 65 6e 64 69 6e 67 3b 20 6d 3c ; m<=pending; m<
0480: 3c 3d 31 2c 6a 2d 2d 29 0d 0a 09 09 09 69 66 28 <=1,j--).....if(
0490: 20 28 70 65 6e 64 69 6e 67 20 26 20 6d 29 20 26 (pending & m) &
04a0: 26 20 69 2b 6a 3c 6e 20 29 0d 0a 09 09 09 7b 0d & i+j<n ).....{.
04b0: 0a 09 09 09 09 69 6e 74 20 70 32 20 3d 20 28 28 .....int p2 = ((
04c0: 70 65 6e 64 69 6e 67 5e 6d 29 3c 3c 31 29 20 7c pending^m)<<1) |
04d0: 20 31 3b 0d 0a 09 09 09 09 69 66 28 20 70 32 20 1;......if( p2
04e0: 3e 3d 20 28 31 3c 3c 6b 2b 31 2b 6b 29 20 29 20 >= (1<<k+1+k) )
04f0: 2f 2f 20 30 62 31 30 30 30 30 30 0d 0a 09 09 09 // 0b100000.....
0500: 09 09 63 6f 6e 74 69 6e 75 65 3b 0d 0a 09 09 09 ..continue;.....
0510: 09 73 75 6d 20 3d 20 61 64 64 28 73 75 6d 2c 20 .sum = add(sum,
0520: 72 65 63 28 70 32 2c 20 69 2b 31 2c 20 6e 2c 20 rec(p2, i+1, n,
0530: 6b 29 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 72 65 k));.....}....re
0540: 74 75 72 6e 20 6d 65 6d 6f 5b 6b 65 79 5d 3d 73 turn memo[key]=s
0550: 75 6d 3b 0d 0a 09 7d 0d 0a 0d 0a 2f 2f 20 42 45 um;...}....// BE
0560: 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 09 70 GIN CUT HERE...p
0570: 75 62 6c 69 63 3a 0d 0a 09 76 6f 69 64 20 72 75 ublic:...void ru
0580: 6e 5f 74 65 73 74 28 69 6e 74 20 43 61 73 65 29 n_test(int Case)
0590: 20 7b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 { if ((Case ==
05a0: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
05b0: 30 29 29 20 74 65 73 74 5f 63 61 73 65 5f 30 28 0)) test_case_0(
05c0: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
05d0: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
05e0: 31 29 29 20 74 65 73 74 5f 63 61 73 65 5f 31 28 1)) test_case_1(
05f0: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
0600: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
0610: 32 29 29 20 74 65 73 74 5f 63 61 73 65 5f 32 28 2)) test_case_2(
0620: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
0630: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
0640: 33 29 29 20 74 65 73 74 5f 63 61 73 65 5f 33 28 3)) test_case_3(
0650: 29 3b 20 7d 0d 0a 09 70 72 69 76 61 74 65 3a 0d ); }...private:.
0660: 0a 09 74 65 6d 70 6c 61 74 65 20 3c 74 79 70 65 ..template <type
0670: 6e 61 6d 65 20 54 3e 20 73 74 72 69 6e 67 20 70 name T> string p
0680: 72 69 6e 74 5f 61 72 72 61 79 28 63 6f 6e 73 74 rint_array(const
0690: 20 76 65 63 74 6f 72 3c 54 3e 20 26 56 29 20 7b vector<T> &V) {
06a0: 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f ostringstream o
06b0: 73 3b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 20 66 s; os << "{ "; f
06c0: 6f 72 20 28 74 79 70 65 6e 61 6d 65 20 76 65 63 or (typename vec
06d0: 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 tor<T>::const_it
06e0: 65 72 61 74 6f 72 20 69 74 65 72 20 3d 20 56 2e erator iter = V.
06f0: 62 65 67 69 6e 28 29 3b 20 69 74 65 72 20 21 3d begin(); iter !=
0700: 20 56 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 65 72 V.end(); ++iter
0710: 29 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 ) os << '\"' <<
0720: 2a 69 74 65 72 20 3c 3c 20 22 5c 22 2c 22 3b 20 *iter << "\",";
0730: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
0740: 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a rn os.str(); }..
0750: 09 76 6f 69 64 20 76 65 72 69 66 79 5f 63 61 73 .void verify_cas
0760: 65 28 69 6e 74 20 43 61 73 65 2c 20 63 6f 6e 73 e(int Case, cons
0770: 74 20 73 74 72 69 6e 67 20 26 45 78 70 65 63 74 t string &Expect
0780: 65 64 2c 20 63 6f 6e 73 74 20 73 74 72 69 6e 67 ed, const string
0790: 20 26 52 65 63 65 69 76 65 64 29 20 7b 20 63 65 &Received) { ce
07a0: 72 72 20 3c 3c 20 22 54 65 73 74 20 43 61 73 65 rr << "Test Case
07b0: 20 23 22 20 3c 3c 20 43 61 73 65 20 3c 3c 20 22 #" << Case << "
07c0: 2e 2e 2e 22 3b 20 69 66 20 28 45 78 70 65 63 74 ..."; if (Expect
07d0: 65 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 20 ed == Received)
07e0: 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 cerr << "PASSED"
07f0: 20 3c 3c 20 65 6e 64 6c 3b 20 65 6c 73 65 20 7b << endl; else {
0800: 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 cerr << "FAILED
0810: 22 20 3c 3c 20 65 6e 64 6c 3b 20 63 65 72 72 20 " << endl; cerr
0820: 3c 3c 20 22 5c 74 45 78 70 65 63 74 65 64 3a 20 << "\tExpected:
0830: 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 64 20 \"" << Expected
0840: 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b << '\"' << endl;
0850: 20 63 65 72 72 20 3c 3c 20 22 5c 74 52 65 63 65 cerr << "\tRece
0860: 69 76 65 64 3a 20 5c 22 22 20 3c 3c 20 52 65 63 ived: \"" << Rec
0870: 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c eived << '\"' <<
0880: 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 09 76 6f 69 endl; } }...voi
0890: 64 20 74 65 73 74 5f 63 61 73 65 5f 30 28 29 20 d test_case_0()
08a0: 7b 20 69 6e 74 20 41 72 67 30 20 3d 20 33 3b 20 { int Arg0 = 3;
08b0: 69 6e 74 20 41 72 67 31 20 3d 20 31 3b 20 73 74 int Arg1 = 1; st
08c0: 72 69 6e 67 20 41 72 67 32 20 3d 20 22 33 22 3b ring Arg2 = "3";
08d0: 20 76 65 72 69 66 79 5f 63 61 73 65 28 30 2c 20 verify_case(0,
08e0: 41 72 67 32 2c 20 63 6f 75 6e 74 50 65 72 6d 75 Arg2, countPermu
08f0: 74 61 74 69 6f 6e 73 28 41 72 67 30 2c 20 41 72 tations(Arg0, Ar
0900: 67 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 g1)); }...void t
0910: 65 73 74 5f 63 61 73 65 5f 31 28 29 20 7b 20 69 est_case_1() { i
0920: 6e 74 20 41 72 67 30 20 3d 20 33 3b 20 69 6e 74 nt Arg0 = 3; int
0930: 20 41 72 67 31 20 3d 20 32 3b 20 73 74 72 69 6e Arg1 = 2; strin
0940: 67 20 41 72 67 32 20 3d 20 22 36 22 3b 20 76 65 g Arg2 = "6"; ve
0950: 72 69 66 79 5f 63 61 73 65 28 31 2c 20 41 72 67 rify_case(1, Arg
0960: 32 2c 20 63 6f 75 6e 74 50 65 72 6d 75 74 61 74 2, countPermutat
0970: 69 6f 6e 73 28 41 72 67 30 2c 20 41 72 67 31 29 ions(Arg0, Arg1)
0980: 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 ); }...void test
0990: 5f 63 61 73 65 5f 32 28 29 20 7b 20 69 6e 74 20 _case_2() { int
09a0: 41 72 67 30 20 3d 20 31 30 3b 20 69 6e 74 20 41 Arg0 = 10; int A
09b0: 72 67 31 20 3d 20 33 3b 20 73 74 72 69 6e 67 20 rg1 = 3; string
09c0: 41 72 67 32 20 3d 20 22 31 39 37 30 38 22 3b 20 Arg2 = "19708";
09d0: 76 65 72 69 66 79 5f 63 61 73 65 28 32 2c 20 41 verify_case(2, A
09e0: 72 67 32 2c 20 63 6f 75 6e 74 50 65 72 6d 75 74 rg2, countPermut
09f0: 61 74 69 6f 6e 73 28 41 72 67 30 2c 20 41 72 67 ations(Arg0, Arg
0a00: 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 1)); }...void te
0a10: 73 74 5f 63 61 73 65 5f 33 28 29 20 7b 20 69 6e st_case_3() { in
0a20: 74 20 41 72 67 30 20 3d 20 31 30 30 3b 20 69 6e t Arg0 = 100; in
0a30: 74 20 41 72 67 31 20 3d 20 31 3b 20 73 74 72 69 t Arg1 = 1; stri
0a40: 6e 67 20 41 72 67 32 20 3d 20 22 35 37 33 31 34 ng Arg2 = "57314
0a50: 37 38 34 34 30 31 33 38 31 37 30 38 34 31 30 31 7844013817084101
0a60: 22 3b 20 76 65 72 69 66 79 5f 63 61 73 65 28 33 "; verify_case(3
0a70: 2c 20 41 72 67 32 2c 20 63 6f 75 6e 74 50 65 72 , Arg2, countPer
0a80: 6d 75 74 61 74 69 6f 6e 73 28 41 72 67 30 2c 20 mutations(Arg0,
0a90: 41 72 67 31 29 29 3b 20 7d 0d 0a 0d 0a 2f 2f 20 Arg1)); }....//
0aa0: 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a 7d 3b END CUT HERE..};
0ab0: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0ac0: 45 52 45 20 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 ERE ..int main()
0ad0: 20 7b 0d 0a 09 46 61 69 72 54 6f 75 72 6e 61 6d {...FairTournam
0ae0: 65 6e 74 28 29 2e 72 75 6e 5f 74 65 73 74 28 2d ent().run_test(-
0af0: 31 29 3b 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 1);..}..// END C
0b00: 55 54 20 48 45 52 45 0d 0a UT HERE..