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 43 61 72 64 53 74 72 61 69 67 68 74 73 0d 0a CardStraights..
0150: 7b 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 69 6e 74 {..public:...int
0160: 20 6c 6f 6e 67 65 73 74 53 74 72 61 69 67 68 74 longestStraight
0170: 28 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 61 (vector <int> ca
0180: 72 64 73 29 20 0d 0a 09 7b 0d 0a 09 09 69 6e 74 rds) ...{....int
0190: 20 6a 6f 6b 20 3d 20 63 6f 75 6e 74 28 63 61 72 jok = count(car
01a0: 64 73 2e 62 65 67 69 6e 28 29 2c 20 63 61 72 64 ds.begin(), card
01b0: 73 2e 65 6e 64 28 29 2c 20 30 29 3b 0d 0a 0d 0a s.end(), 0);....
01c0: 09 09 73 65 74 3c 69 6e 74 3e 20 63 73 28 63 61 ..set<int> cs(ca
01d0: 72 64 73 2e 62 65 67 69 6e 28 29 2c 20 63 61 72 rds.begin(), car
01e0: 64 73 2e 65 6e 64 28 29 29 3b 0d 0a 09 09 63 73 ds.end());....cs
01f0: 2e 65 72 61 73 65 28 30 29 3b 0d 0a 09 09 69 66 .erase(0);....if
0200: 28 20 63 73 2e 65 6d 70 74 79 28 29 20 29 0d 0a ( cs.empty() )..
0210: 09 09 09 72 65 74 75 72 6e 20 6a 6f 6b 3b 20 2f ...return jok; /
0220: 2f 20 4f 75 67 67 67 67 67 67 67 67 67 0d 0a 0d / Ouggggggggg...
0230: 0a 09 09 69 6e 74 20 61 6e 73 20 3d 20 30 3b 0d ...int ans = 0;.
0240: 0a 09 09 66 6f 72 28 73 65 74 3c 69 6e 74 3e 3a ...for(set<int>:
0250: 3a 69 74 65 72 61 74 6f 72 20 69 74 3d 63 73 2e :iterator it=cs.
0260: 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 63 73 2e begin(); it!=cs.
0270: 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 09 09 end(); ++it)....
0280: 09 61 6e 73 20 3d 20 6d 61 78 28 61 6e 73 2c 20 .ans = max(ans,
0290: 61 73 4c 6f 6e 67 41 73 50 6f 73 73 69 62 6c 65 asLongAsPossible
02a0: 28 69 74 2c 20 63 73 2e 65 6e 64 28 29 2c 20 6a (it, cs.end(), j
02b0: 6f 6b 29 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 ok));....return
02c0: 61 6e 73 3b 0d 0a 09 7d 0d 0a 0d 0a 09 69 6e 74 ans;...}.....int
02d0: 20 61 73 4c 6f 6e 67 41 73 50 6f 73 73 69 62 6c asLongAsPossibl
02e0: 65 28 73 65 74 3c 69 6e 74 3e 3a 3a 69 74 65 72 e(set<int>::iter
02f0: 61 74 6f 72 20 69 74 2c 20 73 65 74 3c 69 6e 74 ator it, set<int
0300: 3e 3a 3a 69 74 65 72 61 74 6f 72 20 65 6e 64 2c >::iterator end,
0310: 20 69 6e 74 20 6a 6f 6b 29 0d 0a 09 7b 0d 0a 09 int jok)...{...
0320: 09 69 6e 74 20 62 20 3d 20 2a 69 74 3b 0d 0a 09 .int b = *it;...
0330: 09 69 6e 74 20 65 20 3d 20 2a 69 74 3b 0d 0a 09 .int e = *it;...
0340: 09 66 6f 72 28 2b 2b 69 74 3b 20 69 74 21 3d 65 .for(++it; it!=e
0350: 6e 64 3b 20 65 3d 2a 69 74 2b 2b 29 0d 0a 09 09 nd; e=*it++)....
0360: 09 69 66 28 20 2a 69 74 2d 65 2d 31 20 3c 3d 20 .if( *it-e-1 <=
0370: 6a 6f 6b 20 29 0d 0a 09 09 09 09 6a 6f 6b 20 2d jok )......jok -
0380: 3d 20 2a 69 74 2d 65 2d 31 3b 0d 0a 09 09 09 65 = *it-e-1;.....e
0390: 6c 73 65 0d 0a 09 09 09 09 62 72 65 61 6b 3b 0d lse......break;.
03a0: 0a 09 09 69 6e 74 20 6e 41 66 74 65 72 20 3d 20 ...int nAfter =
03b0: 6d 69 6e 28 31 30 30 30 30 30 30 2d 65 2c 20 6a min(1000000-e, j
03c0: 6f 6b 29 3b 0d 0a 09 09 65 20 2b 3d 20 6e 41 66 ok);....e += nAf
03d0: 74 65 72 3b 0d 0a 09 09 62 20 2d 3d 20 6d 69 6e ter;....b -= min
03e0: 28 62 2d 31 2c 20 6a 6f 6b 2d 6e 41 66 74 65 72 (b-1, jok-nAfter
03f0: 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 65 2d 62 );....return e-b
0400: 2b 31 3b 0d 0a 09 7d 0d 0a 0d 0a 2f 2f 20 42 45 +1;...}....// BE
0410: 47 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 09 70 GIN CUT HERE...p
0420: 75 62 6c 69 63 3a 0d 0a 09 76 6f 69 64 20 72 75 ublic:...void ru
0430: 6e 5f 74 65 73 74 28 69 6e 74 20 43 61 73 65 29 n_test(int Case)
0440: 20 7b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 { if ((Case ==
0450: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
0460: 30 29 29 20 74 65 73 74 5f 63 61 73 65 5f 30 28 0)) test_case_0(
0470: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
0480: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
0490: 31 29 29 20 74 65 73 74 5f 63 61 73 65 5f 31 28 1)) test_case_1(
04a0: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
04b0: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
04c0: 32 29 29 20 74 65 73 74 5f 63 61 73 65 5f 32 28 2)) test_case_2(
04d0: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
04e0: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
04f0: 33 29 29 20 74 65 73 74 5f 63 61 73 65 5f 33 28 3)) test_case_3(
0500: 29 3b 20 69 66 20 28 28 43 61 73 65 20 3d 3d 20 ); if ((Case ==
0510: 2d 31 29 20 7c 7c 20 28 43 61 73 65 20 3d 3d 20 -1) || (Case ==
0520: 34 29 29 20 74 65 73 74 5f 63 61 73 65 5f 34 28 4)) test_case_4(
0530: 29 3b 20 7d 0d 0a 09 70 72 69 76 61 74 65 3a 0d ); }...private:.
0540: 0a 09 74 65 6d 70 6c 61 74 65 20 3c 74 79 70 65 ..template <type
0550: 6e 61 6d 65 20 54 3e 20 73 74 72 69 6e 67 20 70 name T> string p
0560: 72 69 6e 74 5f 61 72 72 61 79 28 63 6f 6e 73 74 rint_array(const
0570: 20 76 65 63 74 6f 72 3c 54 3e 20 26 56 29 20 7b vector<T> &V) {
0580: 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f ostringstream o
0590: 73 3b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 20 66 s; os << "{ "; f
05a0: 6f 72 20 28 74 79 70 65 6e 61 6d 65 20 76 65 63 or (typename vec
05b0: 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 tor<T>::const_it
05c0: 65 72 61 74 6f 72 20 69 74 65 72 20 3d 20 56 2e erator iter = V.
05d0: 62 65 67 69 6e 28 29 3b 20 69 74 65 72 20 21 3d begin(); iter !=
05e0: 20 56 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 65 72 V.end(); ++iter
05f0: 29 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 ) os << '\"' <<
0600: 2a 69 74 65 72 20 3c 3c 20 22 5c 22 2c 22 3b 20 *iter << "\",";
0610: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
0620: 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a rn os.str(); }..
0630: 09 76 6f 69 64 20 76 65 72 69 66 79 5f 63 61 73 .void verify_cas
0640: 65 28 69 6e 74 20 43 61 73 65 2c 20 63 6f 6e 73 e(int Case, cons
0650: 74 20 69 6e 74 20 26 45 78 70 65 63 74 65 64 2c t int &Expected,
0660: 20 63 6f 6e 73 74 20 69 6e 74 20 26 52 65 63 65 const int &Rece
0670: 69 76 65 64 29 20 7b 20 63 65 72 72 20 3c 3c 20 ived) { cerr <<
0680: 22 54 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c "Test Case #" <<
0690: 20 43 61 73 65 20 3c 3c 20 22 2e 2e 2e 22 3b 20 Case << "...";
06a0: 69 66 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 if (Expected ==
06b0: 52 65 63 65 69 76 65 64 29 20 63 65 72 72 20 3c Received) cerr <
06c0: 3c 20 22 50 41 53 53 45 44 22 20 3c 3c 20 65 6e < "PASSED" << en
06d0: 64 6c 3b 20 65 6c 73 65 20 7b 20 63 65 72 72 20 dl; else { cerr
06e0: 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 65 << "FAILED" << e
06f0: 6e 64 6c 3b 20 63 65 72 72 20 3c 3c 20 22 5c 74 ndl; cerr << "\t
0700: 45 78 70 65 63 74 65 64 3a 20 5c 22 22 20 3c 3c Expected: \"" <<
0710: 20 45 78 70 65 63 74 65 64 20 3c 3c 20 27 5c 22 Expected << '\"
0720: 27 20 3c 3c 20 65 6e 64 6c 3b 20 63 65 72 72 20 ' << endl; cerr
0730: 3c 3c 20 22 5c 74 52 65 63 65 69 76 65 64 3a 20 << "\tReceived:
0740: 5c 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 \"" << Received
0750: 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b << '\"' << endl;
0760: 20 7d 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 } }...void test
0770: 5f 63 61 73 65 5f 30 28 29 20 7b 20 69 6e 74 20 _case_0() { int
0780: 41 72 72 30 5b 5d 20 3d 20 7b 30 2c 36 2c 35 2c Arr0[] = {0,6,5,
0790: 31 30 2c 33 2c 30 2c 31 31 7d 3b 20 76 65 63 74 10,3,0,11}; vect
07a0: 6f 72 20 3c 69 6e 74 3e 20 41 72 67 30 28 41 72 or <int> Arg0(Ar
07b0: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
07c0: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
07d0: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e f(Arr0[0]))); in
07e0: 74 20 41 72 67 31 20 3d 20 35 3b 20 76 65 72 69 t Arg1 = 5; veri
07f0: 66 79 5f 63 61 73 65 28 30 2c 20 41 72 67 31 2c fy_case(0, Arg1,
0800: 20 6c 6f 6e 67 65 73 74 53 74 72 61 69 67 68 74 longestStraight
0810: 28 41 72 67 30 29 29 3b 20 7d 0d 0a 09 76 6f 69 (Arg0)); }...voi
0820: 64 20 74 65 73 74 5f 63 61 73 65 5f 31 28 29 20 d test_case_1()
0830: 7b 20 69 6e 74 20 41 72 72 30 5b 5d 20 3d 20 7b { int Arr0[] = {
0840: 31 30 30 2c 31 30 30 2c 31 30 30 2c 31 30 31 2c 100,100,100,101,
0850: 31 30 30 2c 39 39 2c 39 37 2c 31 30 33 7d 3b 20 100,99,97,103};
0860: 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 41 72 67 vector <int> Arg
0870: 30 28 41 72 72 30 2c 20 41 72 72 30 20 2b 20 28 0(Arr0, Arr0 + (
0880: 73 69 7a 65 6f 66 28 41 72 72 30 29 20 2f 20 73 sizeof(Arr0) / s
0890: 69 7a 65 6f 66 28 41 72 72 30 5b 30 5d 29 29 29 izeof(Arr0[0])))
08a0: 3b 20 69 6e 74 20 41 72 67 31 20 3d 20 33 3b 20 ; int Arg1 = 3;
08b0: 76 65 72 69 66 79 5f 63 61 73 65 28 31 2c 20 41 verify_case(1, A
08c0: 72 67 31 2c 20 6c 6f 6e 67 65 73 74 53 74 72 61 rg1, longestStra
08d0: 69 67 68 74 28 41 72 67 30 29 29 3b 20 7d 0d 0a ight(Arg0)); }..
08e0: 09 76 6f 69 64 20 74 65 73 74 5f 63 61 73 65 5f .void test_case_
08f0: 32 28 29 20 7b 20 69 6e 74 20 41 72 72 30 5b 5d 2() { int Arr0[]
0900: 20 3d 20 7b 30 2c 30 2c 30 2c 31 2c 32 2c 36 2c = {0,0,0,1,2,6,
0910: 38 2c 31 30 30 30 7d 3b 20 76 65 63 74 6f 72 20 8,1000}; vector
0920: 3c 69 6e 74 3e 20 41 72 67 30 28 41 72 72 30 2c <int> Arg0(Arr0,
0930: 20 41 72 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 Arr0 + (sizeof(
0940: 41 72 72 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 Arr0) / sizeof(A
0950: 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 rr0[0]))); int A
0960: 72 67 31 20 3d 20 36 3b 20 76 65 72 69 66 79 5f rg1 = 6; verify_
0970: 63 61 73 65 28 32 2c 20 41 72 67 31 2c 20 6c 6f case(2, Arg1, lo
0980: 6e 67 65 73 74 53 74 72 61 69 67 68 74 28 41 72 ngestStraight(Ar
0990: 67 30 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 g0)); }...void t
09a0: 65 73 74 5f 63 61 73 65 5f 33 28 29 20 7b 20 69 est_case_3() { i
09b0: 6e 74 20 41 72 72 30 5b 5d 20 3d 20 7b 31 2c 39 nt Arr0[] = {1,9
09c0: 2c 35 2c 37 2c 33 2c 34 2c 30 2c 30 2c 30 2c 31 ,5,7,3,4,0,0,0,1
09d0: 30 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 0}; vector <int>
09e0: 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 72 30 Arg0(Arr0, Arr0
09f0: 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 30 29 + (sizeof(Arr0)
0a00: 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 5b 30 / sizeof(Arr0[0
0a10: 5d 29 29 29 3b 20 69 6e 74 20 41 72 67 31 20 3d ]))); int Arg1 =
0a20: 20 31 30 3b 20 76 65 72 69 66 79 5f 63 61 73 65 10; verify_case
0a30: 28 33 2c 20 41 72 67 31 2c 20 6c 6f 6e 67 65 73 (3, Arg1, longes
0a40: 74 53 74 72 61 69 67 68 74 28 41 72 67 30 29 29 tStraight(Arg0))
0a50: 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 5f ; }...void test_
0a60: 63 61 73 65 5f 34 28 29 20 7b 20 69 6e 74 20 41 case_4() { int A
0a70: 72 72 30 5b 5d 20 3d 20 7b 30 2c 30 2c 39 39 39 rr0[] = {0,0,999
0a80: 39 39 39 7d 3b 20 76 65 63 74 6f 72 20 3c 69 6e 999}; vector <in
0a90: 74 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 t> Arg0(Arr0, Ar
0aa0: 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 r0 + (sizeof(Arr
0ab0: 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 0) / sizeof(Arr0
0ac0: 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 67 31 [0]))); int Arg1
0ad0: 20 3d 20 33 3b 20 76 65 72 69 66 79 5f 63 61 73 = 3; verify_cas
0ae0: 65 28 34 2c 20 41 72 67 31 2c 20 6c 6f 6e 67 65 e(4, Arg1, longe
0af0: 73 74 53 74 72 61 69 67 68 74 28 41 72 67 30 29 stStraight(Arg0)
0b00: 29 3b 20 7d 0d 0a 0d 0a 2f 2f 20 45 4e 44 20 43 ); }....// END C
0b10: 55 54 20 48 45 52 45 0d 0a 7d 3b 0d 0a 2f 2f 20 UT HERE..};..//
0b20: 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 20 0d BEGIN CUT HERE .
0b30: 0a 69 6e 74 20 6d 61 69 6e 28 29 20 7b 20 43 61 .int main() { Ca
0b40: 72 64 53 74 72 61 69 67 68 74 73 28 29 2e 72 75 rdStraights().ru
0b50: 6e 5f 74 65 73 74 28 2d 31 29 3b 20 7d 0d 0a 2f n_test(-1); }../
0b60: 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a / END CUT HERE..