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 73 74 61 74 69 ong LL;....stati
0140: 63 20 63 6f 6e 73 74 20 4c 4c 20 4d 4f 44 56 41 c const LL MODVA
0150: 4c 20 3d 20 38 33 35 34 35 34 39 35 37 3b 0d 0a L = 835454957;..
0160: 69 6e 74 20 6d 65 6d 6f 5b 35 30 2a 31 35 2a 31 int memo[50*15*1
0170: 30 31 2a 32 5d 3b 0d 0a 69 6e 74 20 6d 65 6d 6f 01*2];..int memo
0180: 5f 6b 5b 31 30 31 5d 3b 0d 0a 0d 0a 63 6c 61 73 _k[101];....clas
0190: 73 20 43 6f 75 6e 74 50 61 6c 69 6e 64 72 6f 6d s CountPalindrom
01a0: 65 73 0d 0a 7b 0d 0a 70 75 62 6c 69 63 3a 0d 0a es..{..public:..
01b0: 09 76 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 .vector<string>
01c0: 77 3b 0d 0a 09 69 6e 74 20 63 6f 75 6e 74 28 76 w;...int count(v
01d0: 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 77 6f ector<string> wo
01e0: 72 64 73 2c 20 69 6e 74 20 6b 29 20 0d 0a 09 7b rds, int k) ...{
01f0: 0d 0a 09 09 77 20 3d 20 77 6f 72 64 73 3b 0d 0a ....w = words;..
0200: 09 09 6d 65 6d 73 65 74 28 6d 65 6d 6f 2c 20 30 ..memset(memo, 0
0210: 78 66 66 2c 20 73 69 7a 65 6f 66 28 6d 65 6d 6f xff, sizeof(memo
0220: 29 29 3b 0d 0a 0d 0a 09 09 4c 4c 20 61 6e 73 20 ));......LL ans
0230: 3d 20 30 3b 0d 0a 09 09 6d 65 6d 6f 5f 6b 5b 30 = 0;....memo_k[0
0240: 5d 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 69 6e ] = 0;....for(in
0250: 74 20 6b 6b 3d 31 3b 20 6b 6b 3c 3d 6b 3b 20 2b t kk=1; kk<=k; +
0260: 2b 6b 6b 29 20 7b 0d 0a 09 09 09 4c 4c 20 61 6b +kk) {.....LL ak
0270: 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 28 69 6e = 0;.....for(in
0280: 74 20 69 3d 30 3b 20 69 3c 77 2e 73 69 7a 65 28 t i=0; i<w.size(
0290: 29 3b 20 2b 2b 69 29 0d 0a 09 09 09 09 61 6b 20 ); ++i)......ak
02a0: 2b 3d 20 72 65 63 5f 6c 28 69 2c 20 30 2c 20 6b += rec_l(i, 0, k
02b0: 6b 29 3b 0d 0a 09 09 09 61 6e 73 20 2b 3d 20 28 k);.....ans += (
02c0: 6d 65 6d 6f 5f 6b 5b 6b 6b 5d 20 3d 20 61 6b 25 memo_k[kk] = ak%
02d0: 4d 4f 44 56 41 4c 29 3b 0d 0a 09 09 7d 0d 0a 09 MODVAL);....}...
02e0: 09 72 65 74 75 72 6e 20 69 6e 74 28 61 6e 73 20 .return int(ans
02f0: 25 20 4d 4f 44 56 41 4c 29 3b 0d 0a 0d 0a 09 7d % MODVAL);.....}
0300: 0d 0a 0d 0a 09 69 6e 74 20 72 65 63 5f 6c 28 69 .....int rec_l(i
0310: 6e 74 20 69 2c 20 69 6e 74 20 69 78 2c 20 69 6e nt i, int ix, in
0320: 74 20 6b 29 0d 0a 09 7b 0d 0a 09 09 69 6e 74 20 t k)...{....int
0330: 6b 65 79 20 3d 20 28 28 28 69 2a 31 35 29 2b 69 key = (((i*15)+i
0340: 78 29 2a 31 30 31 2b 6b 29 2a 32 2b 30 3b 0d 0a x)*101+k)*2+0;..
0350: 09 09 69 66 28 20 6d 65 6d 6f 5b 6b 65 79 5d 3e ..if( memo[key]>
0360: 3d 30 20 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 =0 ).....return
0370: 6d 65 6d 6f 5b 6b 65 79 5d 3b 0d 0a 0d 0a 09 09 memo[key];......
0380: 4c 4c 20 61 6e 73 20 3d 20 30 3b 0d 0a 09 09 66 LL ans = 0;....f
0390: 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 77 2e or(int j=0; j<w.
03a0: 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0d 0a 09 09 size(); ++j)....
03b0: 09 61 6e 73 20 2b 3d 20 72 65 63 28 69 2c 20 69 .ans += rec(i, i
03c0: 78 2c 20 6a 2c 20 77 5b 6a 5d 2e 73 69 7a 65 28 x, j, w[j].size(
03d0: 29 2d 31 2c 20 6b 29 3b 0d 0a 09 09 72 65 74 75 )-1, k);....retu
03e0: 72 6e 20 6d 65 6d 6f 5b 6b 65 79 5d 20 3d 20 69 rn memo[key] = i
03f0: 6e 74 28 61 6e 73 20 25 20 4d 4f 44 56 41 4c 29 nt(ans % MODVAL)
0400: 3b 0d 0a 09 7d 0d 0a 0d 0a 09 69 6e 74 20 72 65 ;...}.....int re
0410: 63 5f 72 28 69 6e 74 20 6a 2c 20 69 6e 74 20 6a c_r(int j, int j
0420: 78 2c 20 69 6e 74 20 6b 29 0d 0a 09 7b 0d 0a 09 x, int k)...{...
0430: 09 69 6e 74 20 6b 65 79 20 3d 20 28 28 28 6a 2a .int key = (((j*
0440: 31 35 29 2b 6a 78 29 2a 31 30 31 2b 6b 29 2a 32 15)+jx)*101+k)*2
0450: 2b 31 3b 0d 0a 09 09 69 66 28 20 6d 65 6d 6f 5b +1;....if( memo[
0460: 6b 65 79 5d 3e 3d 30 20 29 0d 0a 09 09 09 72 65 key]>=0 ).....re
0470: 74 75 72 6e 20 6d 65 6d 6f 5b 6b 65 79 5d 3b 0d turn memo[key];.
0480: 0a 0d 0a 09 09 4c 4c 20 61 6e 73 20 3d 20 30 3b .....LL ans = 0;
0490: 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b ....for(int i=0;
04a0: 20 69 3c 77 2e 73 69 7a 65 28 29 3b 20 2b 2b 69 i<w.size(); ++i
04b0: 29 0d 0a 09 09 09 61 6e 73 20 2b 3d 20 72 65 63 ).....ans += rec
04c0: 28 69 2c 20 30 2c 20 6a 2c 20 6a 78 2c 20 6b 29 (i, 0, j, jx, k)
04d0: 3b 0d 0a 09 09 72 65 74 75 72 6e 20 6d 65 6d 6f ;....return memo
04e0: 5b 6b 65 79 5d 20 3d 20 69 6e 74 28 61 6e 73 20 [key] = int(ans
04f0: 25 20 4d 4f 44 56 41 4c 29 3b 0d 0a 09 7d 0d 0a % MODVAL);...}..
0500: 0d 0a 0d 0a 09 69 6e 74 20 72 65 63 28 69 6e 74 .....int rec(int
0510: 20 69 2c 20 69 6e 74 20 69 78 2c 20 69 6e 74 20 i, int ix, int
0520: 6a 2c 20 69 6e 74 20 6a 78 2c 20 69 6e 74 20 6b j, int jx, int k
0530: 29 0d 0a 09 7b 0d 0a 09 09 77 68 69 6c 65 28 20 )...{....while(
0540: 6b 3e 3d 32 20 26 26 20 69 78 3c 77 5b 69 5d 2e k>=2 && ix<w[i].
0550: 73 69 7a 65 28 29 20 26 26 20 30 3c 3d 6a 78 20 size() && 0<=jx
0560: 29 0d 0a 09 09 09 69 66 28 20 77 5b 69 5d 5b 69 ).....if( w[i][i
0570: 78 5d 20 21 3d 20 77 5b 6a 5d 5b 6a 78 5d 20 29 x] != w[j][jx] )
0580: 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 30 3b 0d ......return 0;.
0590: 0a 09 09 09 65 6c 73 65 0d 0a 09 09 09 09 2b 2b ....else......++
05a0: 69 78 2c 20 2d 2d 6a 78 2c 20 6b 2d 3d 32 3b 0d ix, --jx, k-=2;.
05b0: 0a 0d 0a 09 09 69 66 28 20 6b 20 3d 3d 20 30 20 .....if( k == 0
05c0: 29 0d 0a 09 09 09 72 65 74 75 72 6e 20 28 69 3d ).....return (i=
05d0: 3d 6a 20 26 26 20 69 78 3d 3d 6a 78 2b 31 20 3f =j && ix==jx+1 ?
05e0: 20 31 20 3a 20 30 29 3b 0d 0a 09 09 69 66 28 20 1 : 0);....if(
05f0: 6b 20 3d 3d 20 31 20 29 0d 0a 09 09 09 72 65 74 k == 1 ).....ret
0600: 75 72 6e 20 28 69 3d 3d 6a 20 26 26 20 69 78 3d urn (i==j && ix=
0610: 3d 6a 78 20 7c 7c 20 69 78 3d 3d 77 5b 69 5d 2e =jx || ix==w[i].
0620: 73 69 7a 65 28 29 20 26 26 20 6a 78 3d 3d 2d 31 size() && jx==-1
0630: 20 3f 20 31 20 3a 20 30 29 3b 0d 0a 0d 0a 09 09 ? 1 : 0);......
0640: 69 66 28 20 69 78 3d 3d 77 5b 69 5d 2e 73 69 7a if( ix==w[i].siz
0650: 65 28 29 20 26 26 20 6a 78 3d 3d 2d 31 20 29 0d e() && jx==-1 ).
0660: 0a 09 09 09 72 65 74 75 72 6e 20 6d 65 6d 6f 5f ....return memo_
0670: 6b 5b 6b 2d 32 5d 3b 0d 0a 09 09 65 6c 73 65 20 k[k-2];....else
0680: 69 66 28 20 69 78 3d 3d 77 5b 69 5d 2e 73 69 7a if( ix==w[i].siz
0690: 65 28 29 20 29 0d 0a 09 09 09 72 65 74 75 72 6e e() ).....return
06a0: 20 72 65 63 5f 72 28 6a 2c 20 6a 78 2c 20 6b 2d rec_r(j, jx, k-
06b0: 31 29 3b 0d 0a 09 09 65 6c 73 65 20 69 66 28 20 1);....else if(
06c0: 6a 78 3d 3d 2d 31 20 29 0d 0a 09 09 09 72 65 74 jx==-1 ).....ret
06d0: 75 72 6e 20 72 65 63 5f 6c 28 69 2c 20 69 78 2c urn rec_l(i, ix,
06e0: 20 6b 2d 31 29 3b 0d 0a 09 09 65 6c 73 65 0d 0a k-1);....else..
06f0: 09 09 09 72 65 74 75 72 6e 20 30 3b 0d 0a 09 7d ...return 0;...}
0700: 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 ....// BEGIN CUT
0710: 20 48 45 52 45 0d 0a 09 70 75 62 6c 69 63 3a 0d HERE...public:.
0720: 0a 09 76 6f 69 64 20 72 75 6e 5f 74 65 73 74 28 ..void run_test(
0730: 69 6e 74 20 43 61 73 65 29 20 7b 20 69 66 20 28 int Case) { if (
0740: 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 (Case == -1) ||
0750: 28 43 61 73 65 20 3d 3d 20 30 29 29 20 74 65 73 (Case == 0)) tes
0760: 74 5f 63 61 73 65 5f 30 28 29 3b 20 69 66 20 28 t_case_0(); if (
0770: 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 (Case == -1) ||
0780: 28 43 61 73 65 20 3d 3d 20 31 29 29 20 74 65 73 (Case == 1)) tes
0790: 74 5f 63 61 73 65 5f 31 28 29 3b 20 69 66 20 28 t_case_1(); if (
07a0: 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 (Case == -1) ||
07b0: 28 43 61 73 65 20 3d 3d 20 32 29 29 20 74 65 73 (Case == 2)) tes
07c0: 74 5f 63 61 73 65 5f 32 28 29 3b 20 69 66 20 28 t_case_2(); if (
07d0: 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 (Case == -1) ||
07e0: 28 43 61 73 65 20 3d 3d 20 33 29 29 20 74 65 73 (Case == 3)) tes
07f0: 74 5f 63 61 73 65 5f 33 28 29 3b 20 69 66 20 28 t_case_3(); if (
0800: 28 43 61 73 65 20 3d 3d 20 2d 31 29 20 7c 7c 20 (Case == -1) ||
0810: 28 43 61 73 65 20 3d 3d 20 34 29 29 20 74 65 73 (Case == 4)) tes
0820: 74 5f 63 61 73 65 5f 34 28 29 3b 20 7d 0d 0a 09 t_case_4(); }...
0830: 70 72 69 76 61 74 65 3a 0d 0a 09 74 65 6d 70 6c private:...templ
0840: 61 74 65 20 3c 74 79 70 65 6e 61 6d 65 20 54 3e ate <typename T>
0850: 20 73 74 72 69 6e 67 20 70 72 69 6e 74 5f 61 72 string print_ar
0860: 72 61 79 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 ray(const vector
0870: 3c 54 3e 20 26 56 29 20 7b 20 6f 73 74 72 69 6e <T> &V) { ostrin
0880: 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c gstream os; os <
0890: 3c 20 22 7b 20 22 3b 20 66 6f 72 20 28 74 79 70 < "{ "; for (typ
08a0: 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a ename vector<T>:
08b0: 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 :const_iterator
08c0: 69 74 65 72 20 3d 20 56 2e 62 65 67 69 6e 28 29 iter = V.begin()
08d0: 3b 20 69 74 65 72 20 21 3d 20 56 2e 65 6e 64 28 ; iter != V.end(
08e0: 29 3b 20 2b 2b 69 74 65 72 29 20 6f 73 20 3c 3c ); ++iter) os <<
08f0: 20 27 5c 22 27 20 3c 3c 20 2a 69 74 65 72 20 3c '\"' << *iter <
0900: 3c 20 22 5c 22 2c 22 3b 20 6f 73 20 3c 3c 20 22 < "\","; os << "
0910: 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 }"; return os.s
0920: 74 72 28 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 76 tr(); }...void v
0930: 65 72 69 66 79 5f 63 61 73 65 28 69 6e 74 20 43 erify_case(int C
0940: 61 73 65 2c 20 63 6f 6e 73 74 20 69 6e 74 20 26 ase, const int &
0950: 45 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 Expected, const
0960: 69 6e 74 20 26 52 65 63 65 69 76 65 64 29 20 7b int &Received) {
0970: 20 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 43 cerr << "Test C
0980: 61 73 65 20 23 22 20 3c 3c 20 43 61 73 65 20 3c ase #" << Case <
0990: 3c 20 22 2e 2e 2e 22 3b 20 69 66 20 28 45 78 70 < "..."; if (Exp
09a0: 65 63 74 65 64 20 3d 3d 20 52 65 63 65 69 76 65 ected == Receive
09b0: 64 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 53 d) cerr << "PASS
09c0: 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 65 6c 73 ED" << endl; els
09d0: 65 20 7b 20 63 65 72 72 20 3c 3c 20 22 46 41 49 e { cerr << "FAI
09e0: 4c 45 44 22 20 3c 3c 20 65 6e 64 6c 3b 20 63 65 LED" << endl; ce
09f0: 72 72 20 3c 3c 20 22 5c 74 45 78 70 65 63 74 65 rr << "\tExpecte
0a00: 64 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 d: \"" << Expect
0a10: 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e ed << '\"' << en
0a20: 64 6c 3b 20 63 65 72 72 20 3c 3c 20 22 5c 74 52 dl; cerr << "\tR
0a30: 65 63 65 69 76 65 64 3a 20 5c 22 22 20 3c 3c 20 eceived: \"" <<
0a40: 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c 22 27 Received << '\"'
0a50: 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d 0a 09 << endl; } }...
0a60: 76 6f 69 64 20 74 65 73 74 5f 63 61 73 65 5f 30 void test_case_0
0a70: 28 29 20 7b 20 73 74 72 69 6e 67 20 41 72 72 30 () { string Arr0
0a80: 5b 5d 20 3d 20 7b 22 74 72 61 67 69 63 22 2c 22 [] = {"tragic","
0a90: 63 69 67 61 72 22 7d 3b 20 76 65 63 74 6f 72 20 cigar"}; vector
0aa0: 3c 73 74 72 69 6e 67 3e 20 41 72 67 30 28 41 72 <string> Arg0(Ar
0ab0: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
0ac0: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
0ad0: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e f(Arr0[0]))); in
0ae0: 74 20 41 72 67 31 20 3d 20 32 34 3b 20 69 6e 74 t Arg1 = 24; int
0af0: 20 41 72 67 32 20 3d 20 31 3b 20 76 65 72 69 66 Arg2 = 1; verif
0b00: 79 5f 63 61 73 65 28 30 2c 20 41 72 67 32 2c 20 y_case(0, Arg2,
0b10: 63 6f 75 6e 74 28 41 72 67 30 2c 20 41 72 67 31 count(Arg0, Arg1
0b20: 29 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 )); }...void tes
0b30: 74 5f 63 61 73 65 5f 31 28 29 20 7b 20 73 74 72 t_case_1() { str
0b40: 69 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 7a ing Arr0[] = {"z
0b50: 22 2c 22 7a 7a 22 7d 3b 20 76 65 63 74 6f 72 20 ","zz"}; vector
0b60: 3c 73 74 72 69 6e 67 3e 20 41 72 67 30 28 41 72 <string> Arg0(Ar
0b70: 72 30 2c 20 41 72 72 30 20 2b 20 28 73 69 7a 65 r0, Arr0 + (size
0b80: 6f 66 28 41 72 72 30 29 20 2f 20 73 69 7a 65 6f of(Arr0) / sizeo
0b90: 66 28 41 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e f(Arr0[0]))); in
0ba0: 74 20 41 72 67 31 20 3d 20 34 3b 20 69 6e 74 20 t Arg1 = 4; int
0bb0: 41 72 67 32 20 3d 20 35 3b 20 76 65 72 69 66 79 Arg2 = 5; verify
0bc0: 5f 63 61 73 65 28 31 2c 20 41 72 67 32 2c 20 63 _case(1, Arg2, c
0bd0: 6f 75 6e 74 28 41 72 67 30 2c 20 41 72 67 31 29 ount(Arg0, Arg1)
0be0: 29 3b 20 7d 0d 0a 09 76 6f 69 64 20 74 65 73 74 ); }...void test
0bf0: 5f 63 61 73 65 5f 32 28 29 20 7b 20 73 74 72 69 _case_2() { stri
0c00: 6e 67 20 41 72 72 30 5b 5d 20 3d 20 7b 22 61 62 ng Arr0[] = {"ab
0c10: 61 22 2c 22 61 63 61 62 61 22 2c 22 62 61 63 61 a","acaba","baca
0c20: 22 2c 22 63 61 63 22 2c 22 62 22 2c 22 63 22 2c ","cac","b","c",
0c30: 22 61 22 7d 3b 20 76 65 63 74 6f 72 20 3c 73 74 "a"}; vector <st
0c40: 72 69 6e 67 3e 20 41 72 67 30 28 41 72 72 30 2c ring> Arg0(Arr0,
0c50: 20 41 72 72 30 20 2b 20 28 73 69 7a 65 6f 66 28 Arr0 + (sizeof(
0c60: 41 72 72 30 29 20 2f 20 73 69 7a 65 6f 66 28 41 Arr0) / sizeof(A
0c70: 72 72 30 5b 30 5d 29 29 29 3b 20 69 6e 74 20 41 rr0[0]))); int A
0c80: 72 67 31 20 3d 20 37 30 3b 20 69 6e 74 20 41 72 rg1 = 70; int Ar
0c90: 67 32 20 3d 20 33 37 30 37 38 36 39 36 36 3b 20 g2 = 370786966;
0ca0: 76 65 72 69 66 79 5f 63 61 73 65 28 32 2c 20 41 verify_case(2, A
0cb0: 72 67 32 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c rg2, count(Arg0,
0cc0: 20 41 72 67 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 Arg1)); }...voi
0cd0: 64 20 74 65 73 74 5f 63 61 73 65 5f 33 28 29 20 d test_case_3()
0ce0: 7b 20 73 74 72 69 6e 67 20 41 72 72 30 5b 5d 20 { string Arr0[]
0cf0: 3d 20 7b 22 68 65 6c 6c 6f 22 7d 3b 20 76 65 63 = {"hello"}; vec
0d00: 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 41 72 67 tor <string> Arg
0d10: 30 28 41 72 72 30 2c 20 41 72 72 30 20 2b 20 28 0(Arr0, Arr0 + (
0d20: 73 69 7a 65 6f 66 28 41 72 72 30 29 20 2f 20 73 sizeof(Arr0) / s
0d30: 69 7a 65 6f 66 28 41 72 72 30 5b 30 5d 29 29 29 izeof(Arr0[0])))
0d40: 3b 20 69 6e 74 20 41 72 67 31 20 3d 20 31 30 30 ; int Arg1 = 100
0d50: 3b 20 69 6e 74 20 41 72 67 32 20 3d 20 30 3b 20 ; int Arg2 = 0;
0d60: 76 65 72 69 66 79 5f 63 61 73 65 28 33 2c 20 41 verify_case(3, A
0d70: 72 67 32 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c rg2, count(Arg0,
0d80: 20 41 72 67 31 29 29 3b 20 7d 0d 0a 09 76 6f 69 Arg1)); }...voi
0d90: 64 20 74 65 73 74 5f 63 61 73 65 5f 34 28 29 20 d test_case_4()
0da0: 7b 20 73 74 72 69 6e 67 20 41 72 72 30 5b 5d 20 { string Arr0[]
0db0: 3d 20 7b 22 61 22 2c 20 22 61 61 61 61 61 61 61 = {"a", "aaaaaaa
0dc0: 61 61 62 22 2c 20 22 61 61 61 22 2c 20 22 61 61 aab", "aaa", "aa
0dd0: 61 61 61 61 61 61 61 61 61 61 22 2c 20 22 61 61 aaaaaaaaaa", "aa
0de0: 62 62 61 61 61 22 2c 20 22 62 61 62 61 61 61 61 bbaaa", "babaaaa
0df0: 61 61 61 61 22 2c 20 22 61 61 61 61 61 61 62 61 aaaa", "aaaaaaba
0e00: 61 61 62 61 22 2c 20 22 61 61 61 61 22 2c 20 22 aaba", "aaaa", "
0e10: 61 61 61 61 61 61 61 61 61 22 2c 20 22 61 61 61 aaaaaaaaa", "aaa
0e20: 61 61 61 61 61 61 61 22 2c 20 22 61 61 62 22 2c aaaaaaa", "aab",
0e30: 20 22 61 61 61 61 61 61 62 61 62 61 61 61 61 61 "aaaaaababaaaaa
0e40: 22 2c 20 22 61 61 61 61 61 61 61 61 61 61 61 62 ", "aaaaaaaaaaab
0e50: 62 61 22 2c 20 22 61 61 61 61 61 61 62 61 61 22 ba", "aaaaaabaa"
0e60: 2c 20 22 61 61 61 62 61 61 61 61 61 61 22 2c 20 , "aaabaaaaaa",
0e70: 22 61 62 61 61 61 61 61 61 61 61 22 2c 20 22 61 "abaaaaaaaa", "a
0e80: 61 61 61 61 61 22 2c 20 22 61 61 62 61 61 61 61 aaaaa", "aabaaaa
0e90: 61 61 61 61 61 62 61 22 2c 20 22 61 62 22 2c 20 aaaaaba", "ab",
0ea0: 22 62 62 62 61 61 62 61 61 61 61 62 22 2c 20 22 "bbbaabaaaab", "
0eb0: 61 61 61 61 62 61 61 61 61 61 22 2c 20 22 61 61 aaaabaaaaa", "aa
0ec0: 22 2c 20 22 62 61 61 61 61 61 61 61 61 61 61 61 ", "baaaaaaaaaaa
0ed0: 61 22 2c 20 22 61 61 62 61 61 22 2c 20 22 61 61 a", "aabaa", "aa
0ee0: 62 61 61 61 61 61 61 61 61 62 62 61 61 22 2c 20 baaaaaaaabbaa",
0ef0: 22 61 61 61 61 61 61 61 61 62 61 61 61 61 61 61 "aaaaaaaabaaaaaa
0f00: 22 2c 20 22 61 61 61 61 61 61 61 61 22 2c 20 22 ", "aaaaaaaa", "
0f10: 61 61 61 61 61 22 2c 20 22 61 61 61 61 61 61 61 aaaaa", "aaaaaaa
0f20: 61 61 61 61 22 2c 20 22 61 61 62 61 61 61 61 61 aaaa", "aabaaaaa
0f30: 22 2c 20 22 62 61 61 62 61 61 61 61 61 61 61 61 ", "baabaaaaaaaa
0f40: 61 22 2c 20 22 62 61 61 61 61 61 22 2c 20 22 61 a", "baaaaa", "a
0f50: 61 61 61 61 61 61 61 62 61 61 61 61 61 22 2c 20 aaaaaaabaaaaa",
0f60: 22 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 "aaaaaaaaaaaaaaa
0f70: 22 2c 20 22 61 62 61 61 61 61 61 61 61 61 61 61 ", "abaaaaaaaaaa
0f80: 61 22 2c 20 22 61 61 61 62 61 62 61 62 61 61 61 a", "aaabababaaa
0f90: 61 22 2c 20 22 61 61 61 61 61 61 61 61 61 61 62 a", "aaaaaaaaaab
0fa0: 61 61 61 61 22 2c 20 22 61 62 61 61 61 22 2c 20 aaaa", "abaaa",
0fb0: 22 61 61 61 61 61 62 61 61 61 61 62 22 2c 20 22 "aaaaabaaaab", "
0fc0: 61 61 61 61 62 61 61 61 61 61 61 61 22 2c 20 22 aaaabaaaaaaa", "
0fd0: 61 61 61 61 61 61 61 62 61 22 2c 20 22 62 61 62 aaaaaaaba", "bab
0fe0: 62 62 61 61 61 61 61 62 61 22 2c 20 22 61 61 61 bbaaaaaba", "aaa
0ff0: 61 61 61 61 61 61 61 61 61 61 22 2c 20 22 61 61 aaaaaaaaaa", "aa
1000: 61 62 61 62 61 61 62 61 61 62 22 2c 20 22 61 61 ababaabaab", "aa
1010: 61 62 61 61 62 61 61 61 62 22 2c 20 22 61 61 61 abaabaaab", "aaa
1020: 61 62 62 61 61 61 62 61 61 61 61 61 22 2c 20 22 abbaaabaaaaa", "
1030: 61 62 61 61 61 61 61 61 61 61 61 61 61 61 61 22 abaaaaaaaaaaaaa"
1040: 2c 20 22 61 61 61 61 61 61 61 22 2c 20 22 61 62 , "aaaaaaa", "ab
1050: 61 61 61 61 61 62 61 61 61 61 61 61 61 22 2c 20 aaaaabaaaaaaa",
1060: 22 61 61 61 62 61 61 61 61 61 61 61 61 61 22 7d "aaabaaaaaaaaa"}
1070: 3b 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 ; vector <string
1080: 3e 20 41 72 67 30 28 41 72 72 30 2c 20 41 72 72 > Arg0(Arr0, Arr
1090: 30 20 2b 20 28 73 69 7a 65 6f 66 28 41 72 72 30 0 + (sizeof(Arr0
10a0: 29 20 2f 20 73 69 7a 65 6f 66 28 41 72 72 30 5b ) / sizeof(Arr0[
10b0: 30 5d 29 29 29 3b 20 69 6e 74 20 41 72 67 31 20 0]))); int Arg1
10c0: 3d 20 31 30 30 3b 20 69 6e 74 20 41 72 67 32 20 = 100; int Arg2
10d0: 3d 20 35 37 30 32 37 37 33 35 37 3b 20 76 65 72 = 570277357; ver
10e0: 69 66 79 5f 63 61 73 65 28 34 2c 20 41 72 67 32 ify_case(4, Arg2
10f0: 2c 20 63 6f 75 6e 74 28 41 72 67 30 2c 20 41 72 , count(Arg0, Ar
1100: 67 31 29 29 3b 20 7d 0d 0a 2f 2f 20 45 4e 44 20 g1)); }..// END
1110: 43 55 54 20 48 45 52 45 0d 0a 7d 3b 0d 0a 2f 2f CUT HERE..};..//
1120: 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 20 BEGIN CUT HERE
1130: 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 20 7b 20 43 ..int main() { C
1140: 6f 75 6e 74 50 61 6c 69 6e 64 72 6f 6d 65 73 28 ountPalindromes(
1150: 29 2e 72 75 6e 5f 74 65 73 74 28 2d 31 29 3b 20 ).run_test(-1);
1160: 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 }..// END CUT HE
1170: 52 45 0d 0a RE..