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 4c 4c 20 63 6f 6d 62 CMP;....LL comb
01a0: 28 4c 4c 20 6e 2c 20 4c 4c 20 6b 29 0d 0a 7b 0d (LL n, LL k)..{.
01b0: 0a 09 6b 20 3d 20 6d 69 6e 28 6b 2c 20 6e 2d 6b ..k = min(k, n-k
01c0: 29 3b 0d 0a 0d 0a 09 4c 4c 20 63 20 3d 20 31 3b );.....LL c = 1;
01d0: 0d 0a 09 66 6f 72 28 4c 4c 20 69 3d 30 3b 20 69 ...for(LL i=0; i
01e0: 3c 6b 3b 20 2b 2b 69 29 0d 0a 09 09 63 20 2a 3d <k; ++i)....c *=
01f0: 20 6e 2d 69 2c 20 63 20 2f 3d 20 69 2b 31 3b 0d n-i, c /= i+1;.
0200: 0a 09 72 65 74 75 72 6e 20 63 3b 0d 0a 7d 0d 0a ..return c;..}..
0210: 0d 0a 63 6c 61 73 73 20 50 65 6e 67 75 69 6e 53 ..class PenguinS
0220: 6c 65 64 64 69 6e 67 20 7b 20 70 75 62 6c 69 63 ledding { public
0230: 3a 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 63 6f :...long long co
0240: 75 6e 74 44 65 73 69 67 6e 73 28 69 6e 74 20 6e untDesigns(int n
0250: 75 6d 43 68 65 63 6b 70 6f 69 6e 74 73 2c 20 76 umCheckpoints, v
0260: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 68 65 63 ector <int> chec
0270: 6b 70 6f 69 6e 74 31 2c 20 76 65 63 74 6f 72 20 kpoint1, vector
0280: 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f 69 6e 74 <int> checkpoint
0290: 32 29 0d 0a 09 7b 0d 0a 09 09 4c 4c 20 7a 65 72 2)...{....LL zer
02a0: 6f 20 3d 20 31 3b 0d 0a 09 09 4c 4c 20 6f 6e 65 o = 1;....LL one
02b0: 20 3d 20 63 68 65 63 6b 70 6f 69 6e 74 31 2e 73 = checkpoint1.s
02c0: 69 7a 65 28 29 3b 0d 0a 09 09 4c 4c 20 73 74 61 ize();....LL sta
02d0: 72 20 3d 20 30 3b 0d 0a 09 09 4c 4c 20 74 72 69 r = 0;....LL tri
02e0: 61 6e 67 6c 65 20 3d 20 30 3b 0d 0a 0d 0a 09 09 angle = 0;......
02f0: 66 6f 72 28 69 6e 74 20 63 65 6e 74 65 72 3d 31 for(int center=1
0300: 3b 20 63 65 6e 74 65 72 3c 3d 6e 75 6d 43 68 65 ; center<=numChe
0310: 63 6b 70 6f 69 6e 74 73 3b 20 2b 2b 63 65 6e 74 ckpoints; ++cent
0320: 65 72 29 20 7b 0d 0a 09 09 09 69 6e 74 20 6c 65 er) {.....int le
0330: 61 66 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 28 af = 0;.....for(
0340: 69 6e 74 20 69 3d 30 3b 20 69 3c 63 68 65 63 6b int i=0; i<check
0350: 70 6f 69 6e 74 31 2e 73 69 7a 65 28 29 3b 20 2b point1.size(); +
0360: 2b 69 29 0d 0a 09 09 09 09 69 66 28 63 68 65 63 +i)......if(chec
0370: 6b 70 6f 69 6e 74 31 5b 69 5d 20 3d 3d 20 63 65 kpoint1[i] == ce
0380: 6e 74 65 72 29 0d 0a 09 09 09 09 09 2b 2b 6c 65 nter).......++le
0390: 61 66 3b 0d 0a 09 09 09 09 65 6c 73 65 20 69 66 af;......else if
03a0: 28 63 68 65 63 6b 70 6f 69 6e 74 32 5b 69 5d 20 (checkpoint2[i]
03b0: 3d 3d 20 63 65 6e 74 65 72 29 0d 0a 09 09 09 09 == center)......
03c0: 09 2b 2b 6c 65 61 66 3b 0d 0a 09 09 09 66 6f 72 .++leaf;.....for
03d0: 28 69 6e 74 20 6b 3d 32 3b 20 6b 3c 3d 6c 65 61 (int k=2; k<=lea
03e0: 66 3b 20 2b 2b 6b 29 0d 0a 09 09 09 09 73 74 61 f; ++k)......sta
03f0: 72 20 2b 3d 20 63 6f 6d 62 28 6c 65 61 66 2c 20 r += comb(leaf,
0400: 6b 29 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 73 65 k);....}......se
0410: 74 3c 20 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e t< pair<int,int>
0420: 20 3e 20 63 6f 6e 6e 3b 0d 0a 09 09 66 6f 72 28 > conn;....for(
0430: 69 6e 74 20 69 3d 30 3b 20 69 3c 63 68 65 63 6b int i=0; i<check
0440: 70 6f 69 6e 74 31 2e 73 69 7a 65 28 29 3b 20 2b point1.size(); +
0450: 2b 69 29 20 7b 0d 0a 09 09 09 63 6f 6e 6e 2e 69 +i) {.....conn.i
0460: 6e 73 65 72 74 28 6d 61 6b 65 5f 70 61 69 72 28 nsert(make_pair(
0470: 63 68 65 63 6b 70 6f 69 6e 74 31 5b 69 5d 2c 20 checkpoint1[i],
0480: 63 68 65 63 6b 70 6f 69 6e 74 32 5b 69 5d 29 29 checkpoint2[i]))
0490: 3b 0d 0a 09 09 09 63 6f 6e 6e 2e 69 6e 73 65 72 ;.....conn.inser
04a0: 74 28 6d 61 6b 65 5f 70 61 69 72 28 63 68 65 63 t(make_pair(chec
04b0: 6b 70 6f 69 6e 74 32 5b 69 5d 2c 20 63 68 65 63 kpoint2[i], chec
04c0: 6b 70 6f 69 6e 74 31 5b 69 5d 29 29 3b 0d 0a 09 kpoint1[i]));...
04d0: 09 7d 0d 0a 09 09 66 6f 72 28 69 6e 74 20 61 3d .}....for(int a=
04e0: 31 3b 20 61 3c 3d 6e 75 6d 43 68 65 63 6b 70 6f 1; a<=numCheckpo
04f0: 69 6e 74 73 3b 20 2b 2b 61 29 0d 0a 09 09 66 6f ints; ++a)....fo
0500: 72 28 69 6e 74 20 62 3d 61 2b 31 3b 20 62 3c 3d r(int b=a+1; b<=
0510: 6e 75 6d 43 68 65 63 6b 70 6f 69 6e 74 73 3b 20 numCheckpoints;
0520: 2b 2b 62 29 0d 0a 09 09 66 6f 72 28 69 6e 74 20 ++b)....for(int
0530: 63 3d 62 2b 31 3b 20 63 3c 3d 6e 75 6d 43 68 65 c=b+1; c<=numChe
0540: 63 6b 70 6f 69 6e 74 73 3b 20 2b 2b 63 29 0d 0a ckpoints; ++c)..
0550: 09 09 09 69 66 28 63 6f 6e 6e 2e 63 6f 75 6e 74 ...if(conn.count
0560: 28 6d 61 6b 65 5f 70 61 69 72 28 61 2c 62 29 29 (make_pair(a,b))
0570: 20 26 26 20 63 6f 6e 6e 2e 63 6f 75 6e 74 28 6d && conn.count(m
0580: 61 6b 65 5f 70 61 69 72 28 62 2c 63 29 29 20 26 ake_pair(b,c)) &
0590: 26 20 63 6f 6e 6e 2e 63 6f 75 6e 74 28 6d 61 6b & conn.count(mak
05a0: 65 5f 70 61 69 72 28 63 2c 61 29 29 29 0d 0a 09 e_pair(c,a)))...
05b0: 09 09 09 2b 2b 74 72 69 61 6e 67 6c 65 3b 0d 0a ...++triangle;..
05c0: 0d 0a 09 09 72 65 74 75 72 6e 20 7a 65 72 6f 20 ....return zero
05d0: 2b 20 6f 6e 65 20 2b 20 73 74 61 72 20 2b 20 74 + one + star + t
05e0: 72 69 61 6e 67 6c 65 3b 0d 0a 09 7d 0d 0a 7d 3b riangle;...}..};
05f0: 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 ....// BEGIN CUT
0600: 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 HERE..#include
0610: 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 <ctime>..double
0620: 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 start_time; stri
0630: 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f ng timer().. { o
0640: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b stringstream os;
0650: 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 os << " (" << i
0660: 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 nt((clock()-star
0670: 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 t_time)/CLOCKS_P
0680: 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 ER_SEC*1000) <<
0690: 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e " msec)"; return
06a0: 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 os.str(); }..te
06b0: 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 mplate<typename
06c0: 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 T> ostream& oper
06d0: 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 ator<<(ostream&
06e0: 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 os, const vector
06f0: 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c <T>& v).. { os <
0700: 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 < "{ ";.. for(
0710: 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c typename vector<
0720: 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 T>::const_iterat
0730: 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b or it=v.begin();
0740: 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b it!=v.end(); ++
0750: 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c it).. os << '\
0760: 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 "' << *it << '\"
0770: 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e ' << (it+1==v.en
0780: 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 d() ? "" : ", ")
0790: 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 ; os << " }"; re
07a0: 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 turn os; }..void
07b0: 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e verify_case(con
07c0: 73 74 20 6c 6f 6e 67 20 6c 6f 6e 67 26 20 45 78 st long long& Ex
07d0: 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 6c 6f pected, const lo
07e0: 6e 67 20 6c 6f 6e 67 26 20 52 65 63 65 69 76 65 ng long& Receive
07f0: 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d d) {.. bool ok =
0800: 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 (Expected == Re
0810: 63 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b ceived);.. if(ok
0820: 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 ) cerr << "PASSE
0830: 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c D" << timer() <<
0840: 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 endl; else { c
0850: 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 err << "FAILED"
0860: 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e << timer() << en
0870: 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c dl;.. cerr << "\
0880: 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 to: \"" << Expec
0890: 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 ted << '\"' << e
08a0: 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 ndl << "\tx: \""
08b0: 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 << Received <<
08c0: 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 '\"' << endl; }
08d0: 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 }..#define CASE(
08e0: 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 N) {cerr << "Tes
08f0: 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c t Case #" << N <
0900: 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 < "..." << flush
0910: 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f ; start_time=clo
0920: 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 ck();..#define E
0930: 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 ND. verify_case(
0940: 5f 2c 20 50 65 6e 67 75 69 6e 53 6c 65 64 64 69 _, PenguinSleddi
0950: 6e 67 28 29 2e 63 6f 75 6e 74 44 65 73 69 67 6e ng().countDesign
0960: 73 28 6e 75 6d 43 68 65 63 6b 70 6f 69 6e 74 73 s(numCheckpoints
0970: 2c 20 63 68 65 63 6b 70 6f 69 6e 74 31 2c 20 63 , checkpoint1, c
0980: 68 65 63 6b 70 6f 69 6e 74 32 29 29 3b 7d 0d 0a heckpoint2));}..
0990: 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a 43 int main(){....C
09a0: 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 6e 75 6d ASE(0)...int num
09b0: 43 68 65 63 6b 70 6f 69 6e 74 73 20 3d 20 32 3b Checkpoints = 2;
09c0: 20 0d 0a 09 69 6e 74 20 63 68 65 63 6b 70 6f 69 ...int checkpoi
09d0: 6e 74 31 5f 5b 5d 20 3d 20 7b 31 7d 3b 0d 0a 09 nt1_[] = {1};...
09e0: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 vector <int> c
09f0: 68 65 63 6b 70 6f 69 6e 74 31 28 63 68 65 63 6b heckpoint1(check
0a00: 70 6f 69 6e 74 31 5f 2c 20 63 68 65 63 6b 70 6f point1_, checkpo
0a10: 69 6e 74 31 5f 2b 73 69 7a 65 6f 66 28 63 68 65 int1_+sizeof(che
0a20: 63 6b 70 6f 69 6e 74 31 5f 29 2f 73 69 7a 65 6f ckpoint1_)/sizeo
0a30: 66 28 2a 63 68 65 63 6b 70 6f 69 6e 74 31 5f 29 f(*checkpoint1_)
0a40: 29 3b 20 0d 0a 09 69 6e 74 20 63 68 65 63 6b 70 ); ...int checkp
0a50: 6f 69 6e 74 32 5f 5b 5d 20 3d 20 7b 32 7d 3b 0d oint2_[] = {2};.
0a60: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0a70: 20 63 68 65 63 6b 70 6f 69 6e 74 32 28 63 68 65 checkpoint2(che
0a80: 63 6b 70 6f 69 6e 74 32 5f 2c 20 63 68 65 63 6b ckpoint2_, check
0a90: 70 6f 69 6e 74 32 5f 2b 73 69 7a 65 6f 66 28 63 point2_+sizeof(c
0aa0: 68 65 63 6b 70 6f 69 6e 74 32 5f 29 2f 73 69 7a heckpoint2_)/siz
0ab0: 65 6f 66 28 2a 63 68 65 63 6b 70 6f 69 6e 74 32 eof(*checkpoint2
0ac0: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
0ad0: 67 20 5f 20 3d 20 32 4c 4c 3b 20 0d 0a 45 4e 44 g _ = 2LL; ..END
0ae0: 0d 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e 74 20 ..CASE(1)...int
0af0: 6e 75 6d 43 68 65 63 6b 70 6f 69 6e 74 73 20 3d numCheckpoints =
0b00: 20 34 3b 20 0d 0a 09 69 6e 74 20 63 68 65 63 6b 4; ...int check
0b10: 70 6f 69 6e 74 31 5f 5b 5d 20 3d 20 7b 31 2c 32 point1_[] = {1,2
0b20: 2c 33 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 ,3};... vector
0b30: 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f 69 6e 74 <int> checkpoint
0b40: 31 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2c 20 1(checkpoint1_,
0b50: 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2b 73 69 7a checkpoint1_+siz
0b60: 65 6f 66 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f eof(checkpoint1_
0b70: 29 2f 73 69 7a 65 6f 66 28 2a 63 68 65 63 6b 70 )/sizeof(*checkp
0b80: 6f 69 6e 74 31 5f 29 29 3b 20 0d 0a 09 69 6e 74 oint1_)); ...int
0b90: 20 63 68 65 63 6b 70 6f 69 6e 74 32 5f 5b 5d 20 checkpoint2_[]
0ba0: 3d 20 7b 32 2c 33 2c 34 7d 3b 0d 0a 09 20 20 76 = {2,3,4};... v
0bb0: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 68 65 63 ector <int> chec
0bc0: 6b 70 6f 69 6e 74 32 28 63 68 65 63 6b 70 6f 69 kpoint2(checkpoi
0bd0: 6e 74 32 5f 2c 20 63 68 65 63 6b 70 6f 69 6e 74 nt2_, checkpoint
0be0: 32 5f 2b 73 69 7a 65 6f 66 28 63 68 65 63 6b 70 2_+sizeof(checkp
0bf0: 6f 69 6e 74 32 5f 29 2f 73 69 7a 65 6f 66 28 2a oint2_)/sizeof(*
0c00: 63 68 65 63 6b 70 6f 69 6e 74 32 5f 29 29 3b 20 checkpoint2_));
0c10: 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d ...long long _ =
0c20: 20 36 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 6LL; ..END..CAS
0c30: 45 28 32 29 0d 0a 09 69 6e 74 20 6e 75 6d 43 68 E(2)...int numCh
0c40: 65 63 6b 70 6f 69 6e 74 73 20 3d 20 36 3b 20 0d eckpoints = 6; .
0c50: 0a 09 69 6e 74 20 63 68 65 63 6b 70 6f 69 6e 74 ..int checkpoint
0c60: 31 5f 5b 5d 20 3d 20 7b 31 2c 33 2c 36 7d 3b 0d 1_[] = {1,3,6};.
0c70: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0c80: 20 63 68 65 63 6b 70 6f 69 6e 74 31 28 63 68 65 checkpoint1(che
0c90: 63 6b 70 6f 69 6e 74 31 5f 2c 20 63 68 65 63 6b ckpoint1_, check
0ca0: 70 6f 69 6e 74 31 5f 2b 73 69 7a 65 6f 66 28 63 point1_+sizeof(c
0cb0: 68 65 63 6b 70 6f 69 6e 74 31 5f 29 2f 73 69 7a heckpoint1_)/siz
0cc0: 65 6f 66 28 2a 63 68 65 63 6b 70 6f 69 6e 74 31 eof(*checkpoint1
0cd0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 68 65 63 _)); ...int chec
0ce0: 6b 70 6f 69 6e 74 32 5f 5b 5d 20 3d 20 7b 32 2c kpoint2_[] = {2,
0cf0: 34 2c 34 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 4,4};... vector
0d00: 20 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f 69 6e <int> checkpoin
0d10: 74 32 28 63 68 65 63 6b 70 6f 69 6e 74 32 5f 2c t2(checkpoint2_,
0d20: 20 63 68 65 63 6b 70 6f 69 6e 74 32 5f 2b 73 69 checkpoint2_+si
0d30: 7a 65 6f 66 28 63 68 65 63 6b 70 6f 69 6e 74 32 zeof(checkpoint2
0d40: 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 68 65 63 6b _)/sizeof(*check
0d50: 70 6f 69 6e 74 32 5f 29 29 3b 20 0d 0a 09 6c 6f point2_)); ...lo
0d60: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 35 4c 4c 3b ng long _ = 5LL;
0d70: 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d ..END..CASE(3).
0d80: 0a 09 69 6e 74 20 6e 75 6d 43 68 65 63 6b 70 6f ..int numCheckpo
0d90: 69 6e 74 73 20 3d 20 35 30 3b 20 0d 0a 09 69 6e ints = 50; ...in
0da0: 74 20 63 68 65 63 6b 70 6f 69 6e 74 31 5f 5b 5d t checkpoint1_[]
0db0: 20 3d 20 7b 34 30 2c 20 34 30 2c 20 34 30 2c 20 = {40, 40, 40,
0dc0: 34 30 2c 20 34 30 2c 20 34 30 2c 20 34 30 2c 20 40, 40, 40, 40,
0dd0: 34 30 2c 20 0d 0a 20 34 30 2c 20 34 30 2c 20 34 40, .. 40, 40, 4
0de0: 30 2c 20 34 30 2c 20 35 30 2c 20 34 30 2c 20 34 0, 40, 50, 40, 4
0df0: 30 2c 20 34 30 2c 20 0d 0a 20 32 33 2c 20 34 2c 0, 40, .. 23, 4,
0e00: 20 32 34 2c 20 34 30 2c 20 32 32 2c 20 34 30 2c 24, 40, 22, 40,
0e10: 20 38 2c 20 34 30 2c 20 34 30 2c 0d 0a 20 34 30 8, 40, 40,.. 40
0e20: 2c 20 33 34 2c 20 32 31 2c 20 34 30 2c 20 34 30 , 34, 21, 40, 40
0e30: 2c 20 33 38 2c 20 34 30 2c 20 34 30 2c 20 0d 0a , 38, 40, 40, ..
0e40: 20 34 30 2c 20 34 30 2c 20 34 30 2c 20 32 38 2c 40, 40, 40, 28,
0e50: 20 34 30 2c 20 34 30 2c 20 34 30 2c 20 34 30 2c 40, 40, 40, 40,
0e60: 20 0d 0a 20 34 36 2c 20 31 33 2c 20 34 30 2c 20 .. 46, 13, 40,
0e70: 34 30 2c 20 34 30 2c 20 34 37 2c 20 34 30 2c 20 40, 40, 47, 40,
0e80: 34 30 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 40};... vector
0e90: 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f 69 6e 74 <int> checkpoint
0ea0: 31 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2c 20 1(checkpoint1_,
0eb0: 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2b 73 69 7a checkpoint1_+siz
0ec0: 65 6f 66 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f eof(checkpoint1_
0ed0: 29 2f 73 69 7a 65 6f 66 28 2a 63 68 65 63 6b 70 )/sizeof(*checkp
0ee0: 6f 69 6e 74 31 5f 29 29 3b 20 0d 0a 09 69 6e 74 oint1_)); ...int
0ef0: 20 63 68 65 63 6b 70 6f 69 6e 74 32 5f 5b 5d 20 checkpoint2_[]
0f00: 3d 20 7b 34 35 2c 20 34 32 2c 20 32 30 2c 20 34 = {45, 42, 20, 4
0f10: 38 2c 20 31 32 2c 20 33 32 2c 20 32 35 2c 20 31 8, 12, 32, 25, 1
0f20: 30 2c 20 0d 0a 20 32 36 2c 20 33 39 2c 20 31 36 0, .. 26, 39, 16
0f30: 2c 20 32 2c 20 31 39 2c 20 34 33 2c 20 33 37 2c , 2, 19, 43, 37,
0f40: 20 31 37 2c 20 0d 0a 20 31 39 2c 20 31 39 2c 20 17, .. 19, 19,
0f50: 31 39 2c 20 31 38 2c 20 31 39 2c 20 32 37 2c 20 19, 18, 19, 27,
0f60: 31 39 2c 20 32 39 2c 20 0d 0a 20 31 31 2c 20 33 19, 29, .. 11, 3
0f70: 36 2c 20 31 39 2c 20 31 39 2c 20 31 2c 20 34 31 6, 19, 19, 1, 41
0f80: 2c 20 31 39 2c 20 33 35 2c 20 0d 0a 20 31 34 2c , 19, 35, .. 14,
0f90: 20 33 33 2c 20 34 39 2c 20 33 2c 20 31 39 2c 20 33, 49, 3, 19,
0fa0: 37 2c 20 35 2c 20 31 39 2c 20 33 31 2c 20 0d 0a 7, 5, 19, 31, ..
0fb0: 20 31 39 2c 20 31 39 2c 20 36 2c 20 39 2c 20 31 19, 19, 6, 9, 1
0fc0: 35 2c 20 31 39 2c 20 34 34 2c 20 33 30 7d 3b 0d 5, 19, 44, 30};.
0fd0: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0fe0: 20 63 68 65 63 6b 70 6f 69 6e 74 32 28 63 68 65 checkpoint2(che
0ff0: 63 6b 70 6f 69 6e 74 32 5f 2c 20 63 68 65 63 6b ckpoint2_, check
1000: 70 6f 69 6e 74 32 5f 2b 73 69 7a 65 6f 66 28 63 point2_+sizeof(c
1010: 68 65 63 6b 70 6f 69 6e 74 32 5f 29 2f 73 69 7a heckpoint2_)/siz
1020: 65 6f 66 28 2a 63 68 65 63 6b 70 6f 69 6e 74 32 eof(*checkpoint2
1030: 5f 29 29 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e _)); ...long lon
1040: 67 20 5f 20 3d 20 36 38 37 31 39 34 39 33 31 31 g _ = 6871949311
1050: 38 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 8LL; ..END..CASE
1060: 28 34 29 0d 0a 09 69 6e 74 20 6e 75 6d 43 68 65 (4)...int numChe
1070: 63 6b 70 6f 69 6e 74 73 20 3d 20 33 36 3b 20 0d ckpoints = 36; .
1080: 0a 09 69 6e 74 20 63 68 65 63 6b 70 6f 69 6e 74 ..int checkpoint
1090: 31 5f 5b 5d 20 3d 20 7b 31 33 2c 20 32 34 2c 20 1_[] = {13, 24,
10a0: 32 34 2c 20 32 30 2c 20 33 31 2c 20 31 36 2c 20 24, 20, 31, 16,
10b0: 31 30 2c 20 33 36 2c 20 33 34 2c 20 33 32 2c 20 10, 36, 34, 32,
10c0: 0d 0a 20 32 38 2c 20 35 2c 20 32 30 2c 20 32 39 .. 28, 5, 20, 29
10d0: 2c 20 32 33 2c 20 32 2c 20 31 34 2c 20 34 2c 20 , 23, 2, 14, 4,
10e0: 39 2c 20 35 2c 20 31 39 2c 20 0d 0a 20 32 31 2c 9, 5, 19, .. 21,
10f0: 20 38 2c 20 31 2c 20 32 36 2c 20 32 37 2c 20 32 8, 1, 26, 27, 2
1100: 35 2c 20 31 35 2c 20 32 32 2c 20 33 30 2c 20 33 5, 15, 22, 30, 3
1110: 30 2c 20 0d 0a 20 36 2c 20 31 31 2c 20 37 2c 20 0, .. 6, 11, 7,
1120: 32 2c 20 33 35 2c 20 31 33 2c 20 32 39 2c 20 34 2, 35, 13, 29, 4
1130: 2c 20 31 32 2c 20 33 33 2c 20 31 38 2c 20 0d 0a , 12, 33, 18, ..
1140: 20 31 33 2c 20 31 34 2c 20 31 37 2c 20 33 35 2c 13, 14, 17, 35,
1150: 20 33 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3};... vector
1160: 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f 69 6e 74 <int> checkpoint
1170: 31 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2c 20 1(checkpoint1_,
1180: 63 68 65 63 6b 70 6f 69 6e 74 31 5f 2b 73 69 7a checkpoint1_+siz
1190: 65 6f 66 28 63 68 65 63 6b 70 6f 69 6e 74 31 5f eof(checkpoint1_
11a0: 29 2f 73 69 7a 65 6f 66 28 2a 63 68 65 63 6b 70 )/sizeof(*checkp
11b0: 6f 69 6e 74 31 5f 29 29 3b 20 0d 0a 09 69 6e 74 oint1_)); ...int
11c0: 20 63 68 65 63 6b 70 6f 69 6e 74 32 5f 5b 5d 20 checkpoint2_[]
11d0: 3d 20 7b 31 30 2c 20 31 35 2c 20 32 37 2c 20 31 = {10, 15, 27, 1
11e0: 2c 20 32 39 2c 20 31 31 2c 20 35 2c 20 31 38 2c , 29, 11, 5, 18,
11f0: 20 33 33 2c 20 31 2c 20 39 2c 0d 0a 20 32 2c 20 33, 1, 9,.. 2,
1200: 33 31 2c 20 36 2c 20 31 39 2c 20 31 30 2c 20 33 31, 6, 19, 10, 3
1210: 33 2c 20 31 38 2c 20 36 2c 20 32 37 2c 20 33 2c 3, 18, 6, 27, 3,
1220: 20 32 32 2c 0d 0a 20 34 2c 20 31 32 2c 20 33 31 22,.. 4, 12, 31
1230: 2c 20 33 30 2c 20 33 34 2c 20 31 36 2c 20 37 2c , 30, 34, 16, 7,
1240: 20 32 34 2c 20 33 2c 20 32 38 2c 20 31 35 2c 0d 24, 3, 28, 15,.
1250: 0a 20 32 31 2c 20 32 32 2c 20 38 2c 20 32 36 2c . 21, 22, 8, 26,
1260: 20 32 30 2c 20 31 34 2c 20 33 32 2c 20 32 35 2c 20, 14, 32, 25,
1270: 20 31 37 2c 20 33 35 2c 0d 0a 20 38 2c 20 33 36 17, 35,.. 8, 36
1280: 2c 20 32 36 2c 20 32 33 7d 3b 0d 0a 09 20 20 76 , 26, 23};... v
1290: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 68 65 63 ector <int> chec
12a0: 6b 70 6f 69 6e 74 32 28 63 68 65 63 6b 70 6f 69 kpoint2(checkpoi
12b0: 6e 74 32 5f 2c 20 63 68 65 63 6b 70 6f 69 6e 74 nt2_, checkpoint
12c0: 32 5f 2b 73 69 7a 65 6f 66 28 63 68 65 63 6b 70 2_+sizeof(checkp
12d0: 6f 69 6e 74 32 5f 29 2f 73 69 7a 65 6f 66 28 2a oint2_)/sizeof(*
12e0: 63 68 65 63 6b 70 6f 69 6e 74 32 5f 29 29 3b 20 checkpoint2_));
12f0: 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d ...long long _ =
1300: 20 31 36 32 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2f 162LL; ..END../
1310: 2a 0d 0a 43 41 53 45 28 35 29 0d 0a 09 69 6e 74 *..CASE(5)...int
1320: 20 6e 75 6d 43 68 65 63 6b 70 6f 69 6e 74 73 20 numCheckpoints
1330: 3d 20 3b 20 0d 0a 09 69 6e 74 20 63 68 65 63 6b = ; ...int check
1340: 70 6f 69 6e 74 31 5f 5b 5d 20 3d 20 3b 0d 0a 09 point1_[] = ;...
1350: 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 vector <int> c
1360: 68 65 63 6b 70 6f 69 6e 74 31 28 63 68 65 63 6b heckpoint1(check
1370: 70 6f 69 6e 74 31 5f 2c 20 63 68 65 63 6b 70 6f point1_, checkpo
1380: 69 6e 74 31 5f 2b 73 69 7a 65 6f 66 28 63 68 65 int1_+sizeof(che
1390: 63 6b 70 6f 69 6e 74 31 5f 29 2f 73 69 7a 65 6f ckpoint1_)/sizeo
13a0: 66 28 2a 63 68 65 63 6b 70 6f 69 6e 74 31 5f 29 f(*checkpoint1_)
13b0: 29 3b 20 0d 0a 09 69 6e 74 20 63 68 65 63 6b 70 ); ...int checkp
13c0: 6f 69 6e 74 32 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 oint2_[] = ;...
13d0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 68 vector <int> ch
13e0: 65 63 6b 70 6f 69 6e 74 32 28 63 68 65 63 6b 70 eckpoint2(checkp
13f0: 6f 69 6e 74 32 5f 2c 20 63 68 65 63 6b 70 6f 69 oint2_, checkpoi
1400: 6e 74 32 5f 2b 73 69 7a 65 6f 66 28 63 68 65 63 nt2_+sizeof(chec
1410: 6b 70 6f 69 6e 74 32 5f 29 2f 73 69 7a 65 6f 66 kpoint2_)/sizeof
1420: 28 2a 63 68 65 63 6b 70 6f 69 6e 74 32 5f 29 29 (*checkpoint2_))
1430: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f ; ...long long _
1440: 20 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 = LL; ..END..CA
1450: 53 45 28 36 29 0d 0a 09 69 6e 74 20 6e 75 6d 43 SE(6)...int numC
1460: 68 65 63 6b 70 6f 69 6e 74 73 20 3d 20 3b 20 0d heckpoints = ; .
1470: 0a 09 69 6e 74 20 63 68 65 63 6b 70 6f 69 6e 74 ..int checkpoint
1480: 31 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 1_[] = ;... vec
1490: 74 6f 72 20 3c 69 6e 74 3e 20 63 68 65 63 6b 70 tor <int> checkp
14a0: 6f 69 6e 74 31 28 63 68 65 63 6b 70 6f 69 6e 74 oint1(checkpoint
14b0: 31 5f 2c 20 63 68 65 63 6b 70 6f 69 6e 74 31 5f 1_, checkpoint1_
14c0: 2b 73 69 7a 65 6f 66 28 63 68 65 63 6b 70 6f 69 +sizeof(checkpoi
14d0: 6e 74 31 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 68 nt1_)/sizeof(*ch
14e0: 65 63 6b 70 6f 69 6e 74 31 5f 29 29 3b 20 0d 0a eckpoint1_)); ..
14f0: 09 69 6e 74 20 63 68 65 63 6b 70 6f 69 6e 74 32 .int checkpoint2
1500: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
1510: 6f 72 20 3c 69 6e 74 3e 20 63 68 65 63 6b 70 6f or <int> checkpo
1520: 69 6e 74 32 28 63 68 65 63 6b 70 6f 69 6e 74 32 int2(checkpoint2
1530: 5f 2c 20 63 68 65 63 6b 70 6f 69 6e 74 32 5f 2b _, checkpoint2_+
1540: 73 69 7a 65 6f 66 28 63 68 65 63 6b 70 6f 69 6e sizeof(checkpoin
1550: 74 32 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 68 65 t2_)/sizeof(*che
1560: 63 6b 70 6f 69 6e 74 32 5f 29 29 3b 20 0d 0a 09 ckpoint2_)); ...
1570: 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 4c 4c long long _ = LL
1580: 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a ; ..END..*/..}..
1590: 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d // END CUT HERE.
15a0: 0a .