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 69 6e 74 20 67 63 64 28 CMP;....int gcd(
01a0: 69 6e 74 20 61 2c 20 69 6e 74 20 62 29 20 7b 0d int a, int b) {.
01b0: 0a 09 77 68 69 6c 65 28 61 29 20 73 77 61 70 28 ..while(a) swap(
01c0: 61 2c 62 25 3d 61 29 3b 20 72 65 74 75 72 6e 20 a,b%=a); return
01d0: 62 3b 0d 0a 7d 0d 0a 0d 0a 63 6c 61 73 73 20 46 b;..}....class F
01e0: 72 61 63 74 69 6f 6e 61 6c 69 7a 61 74 69 6f 6e ractionalization
01f0: 20 7b 0d 0a 70 75 62 6c 69 63 3a 0d 0a 09 76 65 {..public:...ve
0200: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 70 61 ctor <string> pa
0210: 72 74 69 61 6c 28 76 65 63 74 6f 72 20 3c 73 74 rtial(vector <st
0220: 72 69 6e 67 3e 20 64 65 66 69 6e 69 74 69 6f 6e ring> definition
0230: 73 2c 20 69 6e 74 20 6d 2c 20 69 6e 74 20 6e 2c s, int m, int n,
0240: 20 73 74 72 69 6e 67 20 64 61 6e 63 65 43 61 6c string danceCal
0250: 6c 29 20 0d 0a 09 7b 0d 0a 09 09 2f 2f 20 69 6e l) ...{....// in
0260: 70 75 74 0d 0a 09 09 6d 61 70 3c 20 73 74 72 69 put....map< stri
0270: 6e 67 2c 20 76 65 63 74 6f 72 3c 73 74 72 69 6e ng, vector<strin
0280: 67 3e 20 3e 20 44 3b 0d 0a 09 09 66 6f 72 28 69 g> > D;....for(i
0290: 6e 74 20 69 3d 30 3b 20 69 3c 64 65 66 69 6e 69 nt i=0; i<defini
02a0: 74 69 6f 6e 73 2e 73 69 7a 65 28 29 3b 20 2b 2b tions.size(); ++
02b0: 69 29 20 7b 0d 0a 09 09 09 73 74 72 69 6e 67 73 i) {.....strings
02c0: 74 72 65 61 6d 20 73 69 6e 28 64 65 66 69 6e 69 tream sin(defini
02d0: 74 69 6f 6e 73 5b 69 5d 29 3b 0d 0a 09 09 09 73 tions[i]);.....s
02e0: 74 72 69 6e 67 20 6e 61 6d 65 3b 20 73 69 6e 3e tring name; sin>
02f0: 3e 6e 61 6d 65 3b 20 6e 61 6d 65 3d 6e 61 6d 65 >name; name=name
0300: 2e 73 75 62 73 74 72 28 30 2c 20 6e 61 6d 65 2e .substr(0, name.
0310: 73 69 7a 65 28 29 2d 31 29 3b 0d 0a 09 09 09 76 size()-1);.....v
0320: 65 63 74 6f 72 3c 73 74 72 69 6e 67 3e 20 64 73 ector<string> ds
0330: 3b 0d 0a 09 09 09 66 6f 72 28 73 74 72 69 6e 67 ;.....for(string
0340: 20 64 3b 20 73 69 6e 3e 3e 64 3b 29 0d 0a 09 09 d; sin>>d;)....
0350: 09 09 64 73 2e 70 75 73 68 5f 62 61 63 6b 28 64 ..ds.push_back(d
0360: 29 3b 0d 0a 09 09 09 44 5b 6e 61 6d 65 5d 20 3d );.....D[name] =
0370: 20 64 73 3b 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 2f ds;....}....../
0380: 2f 20 73 6f 6c 76 65 0d 0a 09 09 76 65 63 74 6f / solve....vecto
0390: 72 3c 73 74 72 69 6e 67 3e 20 72 65 73 75 6c 74 r<string> result
03a0: 3b 0d 0a 09 09 77 68 69 6c 65 28 6d 29 20 7b 0d ;....while(m) {.
03b0: 0a 09 09 09 69 66 28 20 21 44 2e 63 6f 75 6e 74 ....if( !D.count
03c0: 28 64 61 6e 63 65 43 61 6c 6c 29 20 29 0d 0a 09 (danceCall) )...
03d0: 09 09 09 72 65 74 75 72 6e 20 76 65 63 74 6f 72 ...return vector
03e0: 3c 73 74 72 69 6e 67 3e 28 31 2c 20 22 49 4c 4c <string>(1, "ILL
03f0: 45 47 41 4c 22 29 3b 0d 0a 09 09 09 76 65 63 74 EGAL");.....vect
0400: 6f 72 3c 73 74 72 69 6e 67 3e 26 20 64 20 3d 20 or<string>& d =
0410: 44 5b 64 61 6e 63 65 43 61 6c 6c 5d 3b 0d 0a 09 D[danceCall];...
0420: 09 09 69 6e 74 20 71 20 3d 20 64 2e 73 69 7a 65 ..int q = d.size
0430: 28 29 3b 0d 0a 09 09 09 69 6e 74 20 7a 20 3d 20 ();.....int z =
0440: 6d 2a 71 2f 6e 3b 0d 0a 09 09 09 66 6f 72 28 69 m*q/n;.....for(i
0450: 6e 74 20 69 3d 30 3b 20 69 3c 7a 3b 20 2b 2b 69 nt i=0; i<z; ++i
0460: 29 0d 0a 09 09 09 09 72 65 73 75 6c 74 2e 70 75 )......result.pu
0470: 73 68 5f 62 61 63 6b 28 64 5b 69 5d 29 3b 0d 0a sh_back(d[i]);..
0480: 09 09 09 6d 20 3d 20 6d 2a 71 20 2d 20 7a 2a 6e ...m = m*q - z*n
0490: 3b 0d 0a 09 09 09 64 61 6e 63 65 43 61 6c 6c 20 ;.....danceCall
04a0: 3d 20 64 5b 7a 5d 3b 0d 0a 09 09 7d 0d 0a 09 09 = d[z];....}....
04b0: 72 65 74 75 72 6e 20 72 65 73 75 6c 74 3b 0d 0a return result;..
04c0: 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 .}..};....// BEG
04d0: 49 4e 20 43 55 54 20 48 45 52 45 0d 0a 23 69 6e IN CUT HERE..#in
04e0: 63 6c 75 64 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 clude <ctime>..d
04f0: 6f 75 62 6c 65 20 73 74 61 72 74 5f 74 69 6d 65 ouble start_time
0500: 3b 73 74 72 69 6e 67 20 74 69 6d 65 72 28 29 20 ;string timer()
0510: 7b 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 { ostringstream
0520: 6f 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c os; os << " (" <
0530: 3c 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 < int((clock()-s
0540: 74 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b tart_time)/CLOCK
0550: 53 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 29 20 S_PER_SEC*1000)
0560: 3c 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 65 74 << " msec)"; ret
0570: 75 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d urn os.str(); }.
0580: 0a 0d 0a 74 65 6d 70 6c 61 74 65 20 3c 74 79 70 ...template <typ
0590: 65 6e 61 6d 65 20 54 3e 20 73 74 72 69 6e 67 20 ename T> string
05a0: 70 72 69 6e 74 5f 61 72 72 61 79 28 63 6f 6e 73 print_array(cons
05b0: 74 20 76 65 63 74 6f 72 3c 54 3e 20 26 56 29 20 t vector<T> &V)
05c0: 7b 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 { ostringstream
05d0: 6f 73 3b 20 6f 73 20 3c 3c 20 22 7b 20 22 3b 20 os; os << "{ ";
05e0: 66 6f 72 20 28 74 79 70 65 6e 61 6d 65 20 76 65 for (typename ve
05f0: 63 74 6f 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 ctor<T>::const_i
0600: 74 65 72 61 74 6f 72 20 69 74 65 72 20 3d 20 56 terator iter = V
0610: 2e 62 65 67 69 6e 28 29 3b 20 69 74 65 72 20 21 .begin(); iter !
0620: 3d 20 56 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 65 = V.end(); ++ite
0630: 72 29 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c r) os << '\"' <<
0640: 20 2a 69 74 65 72 20 3c 3c 20 22 5c 22 2c 22 3b *iter << "\",";
0650: 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 os << " }"; ret
0660: 75 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d urn os.str(); }.
0670: 0a 69 6e 74 20 76 65 72 69 66 79 5f 63 61 73 65 .int verify_case
0680: 28 63 6f 6e 73 74 20 76 65 63 74 6f 72 20 3c 73 (const vector <s
0690: 74 72 69 6e 67 3e 20 26 45 78 70 65 63 74 65 64 tring> &Expected
06a0: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 20 3c , const vector <
06b0: 73 74 72 69 6e 67 3e 20 26 52 65 63 65 69 76 65 string> &Receive
06c0: 64 29 20 7b 20 69 66 20 28 45 78 70 65 63 74 65 d) { if (Expecte
06d0: 64 20 3d 3d 20 52 65 63 65 69 76 65 64 29 20 63 d == Received) c
06e0: 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 20 err << "PASSED"
06f0: 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e << timer() << en
0700: 64 6c 3b 20 65 6c 73 65 20 7b 20 63 65 72 72 20 dl; else { cerr
0710: 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c 20 74 << "FAILED" << t
0720: 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c 3b 20 imer() << endl;
0730: 63 65 72 72 20 3c 3c 20 22 5c 74 45 78 70 65 63 cerr << "\tExpec
0740: 74 65 64 3a 20 22 20 3c 3c 20 70 72 69 6e 74 5f ted: " << print_
0750: 61 72 72 61 79 28 45 78 70 65 63 74 65 64 29 20 array(Expected)
0760: 3c 3c 20 65 6e 64 6c 3b 20 63 65 72 72 20 3c 3c << endl; cerr <<
0770: 20 22 5c 74 52 65 63 65 69 76 65 64 3a 20 22 20 "\tReceived: "
0780: 3c 3c 20 70 72 69 6e 74 5f 61 72 72 61 79 28 52 << print_array(R
0790: 65 63 65 69 76 65 64 29 20 3c 3c 20 65 6e 64 6c eceived) << endl
07a0: 3b 20 7d 20 72 65 74 75 72 6e 20 30 3b 7d 0d 0a ; } return 0;}..
07b0: 0d 0a 74 65 6d 70 6c 61 74 65 3c 69 6e 74 20 4e ..template<int N
07c0: 3e 20 73 74 72 75 63 74 20 43 61 73 65 5f 20 7b > struct Case_ {
07d0: 20 43 61 73 65 5f 28 29 7b 73 74 61 72 74 5f 74 Case_(){start_t
07e0: 69 6d 65 3d 63 6c 6f 63 6b 28 29 3b 7d 20 7d 3b ime=clock();} };
07f0: 0d 0a 63 68 61 72 20 54 65 73 74 5f 28 2e 2e 2e ..char Test_(...
0800: 29 3b 0d 0a 69 6e 74 20 54 65 73 74 5f 28 43 61 );..int Test_(Ca
0810: 73 65 5f 3c 30 3e 29 20 7b 0d 0a 09 73 74 72 69 se_<0>) {...stri
0820: 6e 67 20 64 65 66 69 6e 69 74 69 6f 6e 73 5f 5b ng definitions_[
0830: 5d 20 3d 20 7b 20 22 46 69 76 65 50 61 72 74 73 ] = { "FiveParts
0840: 3a 20 4f 6e 65 20 54 77 6f 20 54 68 72 65 65 20 : One Two Three
0850: 46 6f 75 72 20 46 69 76 65 22 20 7d 3b 0d 0a 09 Four Five" };...
0860: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
0870: 3e 20 64 65 66 69 6e 69 74 69 6f 6e 73 28 64 65 > definitions(de
0880: 66 69 6e 69 74 69 6f 6e 73 5f 2c 20 64 65 66 69 finitions_, defi
0890: 6e 69 74 69 6f 6e 73 5f 2b 73 69 7a 65 6f 66 28 nitions_+sizeof(
08a0: 64 65 66 69 6e 69 74 69 6f 6e 73 5f 29 2f 73 69 definitions_)/si
08b0: 7a 65 6f 66 28 2a 64 65 66 69 6e 69 74 69 6f 6e zeof(*definition
08c0: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 6d 20 3d s_)); ...int m =
08d0: 20 32 3b 20 0d 0a 09 69 6e 74 20 6e 20 3d 20 35 2; ...int n = 5
08e0: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 64 61 6e 63 ; ...string danc
08f0: 65 43 61 6c 6c 20 3d 20 22 46 69 76 65 50 61 72 eCall = "FivePar
0900: 74 73 22 3b 20 0d 0a 09 73 74 72 69 6e 67 20 52 ts"; ...string R
0910: 65 74 56 61 6c 5f 5b 5d 20 3d 20 7b 22 4f 6e 65 etVal_[] = {"One
0920: 22 2c 20 22 54 77 6f 22 20 7d 3b 0d 0a 09 20 20 ", "Two" };...
0930: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
0940: 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c 20 RetVal(RetVal_,
0950: 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 52 RetVal_+sizeof(R
0960: 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a etVal_)/sizeof(*
0970: 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 65 RetVal_)); ...re
0980: 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 turn verify_case
0990: 28 52 65 74 56 61 6c 2c 20 46 72 61 63 74 69 6f (RetVal, Fractio
09a0: 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 2e 70 61 72 nalization().par
09b0: 74 69 61 6c 28 64 65 66 69 6e 69 74 69 6f 6e 73 tial(definitions
09c0: 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 65 43 61 6c , m, n, danceCal
09d0: 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 74 l)); }..int Test
09e0: 5f 28 43 61 73 65 5f 3c 31 3e 29 20 7b 0d 0a 09 _(Case_<1>) {...
09f0: 73 74 72 69 6e 67 20 64 65 66 69 6e 69 74 69 6f string definitio
0a00: 6e 73 5f 5b 5d 20 3d 20 7b 20 22 54 72 61 64 65 ns_[] = { "Trade
0a10: 3a 20 48 69 6e 67 65 20 48 69 6e 67 65 22 2c 0d : Hinge Hinge",.
0a20: 0a 20 20 22 54 72 61 64 65 54 68 72 65 65 54 69 . "TradeThreeTi
0a30: 6d 65 73 3a 20 54 72 61 64 65 20 54 72 61 64 65 mes: Trade Trade
0a40: 20 54 72 61 64 65 22 20 7d 3b 0d 0a 09 20 20 76 Trade" };... v
0a50: 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 64 ector <string> d
0a60: 65 66 69 6e 69 74 69 6f 6e 73 28 64 65 66 69 6e efinitions(defin
0a70: 69 74 69 6f 6e 73 5f 2c 20 64 65 66 69 6e 69 74 itions_, definit
0a80: 69 6f 6e 73 5f 2b 73 69 7a 65 6f 66 28 64 65 66 ions_+sizeof(def
0a90: 69 6e 69 74 69 6f 6e 73 5f 29 2f 73 69 7a 65 6f initions_)/sizeo
0aa0: 66 28 2a 64 65 66 69 6e 69 74 69 6f 6e 73 5f 29 f(*definitions_)
0ab0: 29 3b 20 0d 0a 09 69 6e 74 20 6d 20 3d 20 35 3b ); ...int m = 5;
0ac0: 20 0d 0a 09 69 6e 74 20 6e 20 3d 20 36 3b 20 0d ...int n = 6; .
0ad0: 0a 09 73 74 72 69 6e 67 20 64 61 6e 63 65 43 61 ..string danceCa
0ae0: 6c 6c 20 3d 20 22 54 72 61 64 65 54 68 72 65 65 ll = "TradeThree
0af0: 54 69 6d 65 73 22 3b 20 0d 0a 09 73 74 72 69 6e Times"; ...strin
0b00: 67 20 52 65 74 56 61 6c 5f 5b 5d 20 3d 20 7b 22 g RetVal_[] = {"
0b10: 54 72 61 64 65 22 2c 20 22 54 72 61 64 65 22 2c Trade", "Trade",
0b20: 20 22 48 69 6e 67 65 22 20 7d 3b 0d 0a 09 20 20 "Hinge" };...
0b30: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
0b40: 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c 20 RetVal(RetVal_,
0b50: 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 52 RetVal_+sizeof(R
0b60: 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a etVal_)/sizeof(*
0b70: 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 65 RetVal_)); ...re
0b80: 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 turn verify_case
0b90: 28 52 65 74 56 61 6c 2c 20 46 72 61 63 74 69 6f (RetVal, Fractio
0ba0: 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 2e 70 61 72 nalization().par
0bb0: 74 69 61 6c 28 64 65 66 69 6e 69 74 69 6f 6e 73 tial(definitions
0bc0: 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 65 43 61 6c , m, n, danceCal
0bd0: 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 74 l)); }..int Test
0be0: 5f 28 43 61 73 65 5f 3c 32 3e 29 20 7b 0d 0a 09 _(Case_<2>) {...
0bf0: 73 74 72 69 6e 67 20 64 65 66 69 6e 69 74 69 6f string definitio
0c00: 6e 73 5f 5b 5d 20 3d 20 7b 20 22 54 72 61 64 65 ns_[] = { "Trade
0c10: 3a 20 48 69 6e 67 65 20 48 69 6e 67 65 22 2c 0d : Hinge Hinge",.
0c20: 0a 20 20 22 43 65 6e 74 65 72 54 77 6f 54 72 61 . "CenterTwoTra
0c30: 64 65 3a 20 43 65 6e 74 65 72 54 77 6f 48 69 6e de: CenterTwoHin
0c40: 67 65 20 43 65 6e 74 65 72 54 77 6f 48 69 6e 67 ge CenterTwoHing
0c50: 65 22 2c 0d 0a 20 20 22 53 70 69 6e 54 68 65 54 e",.. "SpinTheT
0c60: 6f 70 3a 20 54 72 61 64 65 20 46 61 6e 54 68 65 op: Trade FanThe
0c70: 54 6f 70 22 2c 0d 0a 20 20 22 48 6f 74 46 6f 6f Top",.. "HotFoo
0c80: 74 53 70 69 6e 3a 20 46 61 6e 54 68 65 54 6f 70 tSpin: FanTheTop
0c90: 20 43 65 6e 74 65 72 54 77 6f 54 72 61 64 65 20 CenterTwoTrade
0ca0: 53 70 69 6e 54 68 65 54 6f 70 22 20 7d 3b 0d 0a SpinTheTop" };..
0cb0: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
0cc0: 67 3e 20 64 65 66 69 6e 69 74 69 6f 6e 73 28 64 g> definitions(d
0cd0: 65 66 69 6e 69 74 69 6f 6e 73 5f 2c 20 64 65 66 efinitions_, def
0ce0: 69 6e 69 74 69 6f 6e 73 5f 2b 73 69 7a 65 6f 66 initions_+sizeof
0cf0: 28 64 65 66 69 6e 69 74 69 6f 6e 73 5f 29 2f 73 (definitions_)/s
0d00: 69 7a 65 6f 66 28 2a 64 65 66 69 6e 69 74 69 6f izeof(*definitio
0d10: 6e 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 6d 20 ns_)); ...int m
0d20: 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 6e 20 3d 20 = 1; ...int n =
0d30: 32 3b 20 0d 0a 09 73 74 72 69 6e 67 20 64 61 6e 2; ...string dan
0d40: 63 65 43 61 6c 6c 20 3d 20 22 48 6f 74 46 6f 6f ceCall = "HotFoo
0d50: 74 53 70 69 6e 22 3b 20 0d 0a 09 73 74 72 69 6e tSpin"; ...strin
0d60: 67 20 52 65 74 56 61 6c 5f 5b 5d 20 3d 20 7b 22 g RetVal_[] = {"
0d70: 46 61 6e 54 68 65 54 6f 70 22 2c 20 22 43 65 6e FanTheTop", "Cen
0d80: 74 65 72 54 77 6f 48 69 6e 67 65 22 20 7d 3b 0d terTwoHinge" };.
0d90: 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 .. vector <stri
0da0: 6e 67 3e 20 52 65 74 56 61 6c 28 52 65 74 56 61 ng> RetVal(RetVa
0db0: 6c 5f 2c 20 52 65 74 56 61 6c 5f 2b 73 69 7a 65 l_, RetVal_+size
0dc0: 6f 66 28 52 65 74 56 61 6c 5f 29 2f 73 69 7a 65 of(RetVal_)/size
0dd0: 6f 66 28 2a 52 65 74 56 61 6c 5f 29 29 3b 20 0d of(*RetVal_)); .
0de0: 0a 09 72 65 74 75 72 6e 20 76 65 72 69 66 79 5f ..return verify_
0df0: 63 61 73 65 28 52 65 74 56 61 6c 2c 20 46 72 61 case(RetVal, Fra
0e00: 63 74 69 6f 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 ctionalization()
0e10: 2e 70 61 72 74 69 61 6c 28 64 65 66 69 6e 69 74 .partial(definit
0e20: 69 6f 6e 73 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 ions, m, n, danc
0e30: 65 43 61 6c 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 eCall)); }..int
0e40: 54 65 73 74 5f 28 43 61 73 65 5f 3c 33 3e 29 20 Test_(Case_<3>)
0e50: 7b 0d 0a 09 73 74 72 69 6e 67 20 64 65 66 69 6e {...string defin
0e60: 69 74 69 6f 6e 73 5f 5b 5d 20 3d 20 7b 20 22 54 itions_[] = { "T
0e70: 72 61 64 65 3a 20 48 69 6e 67 65 20 48 69 6e 67 rade: Hinge Hing
0e80: 65 22 2c 0d 0a 20 20 22 43 65 6e 74 65 72 54 77 e",.. "CenterTw
0e90: 6f 54 72 61 64 65 3a 20 43 65 6e 74 65 72 54 77 oTrade: CenterTw
0ea0: 6f 48 69 6e 67 65 20 43 65 6e 74 65 72 54 77 6f oHinge CenterTwo
0eb0: 48 69 6e 67 65 22 2c 0d 0a 20 20 22 53 70 69 6e Hinge",.. "Spin
0ec0: 54 68 65 54 6f 70 3a 20 54 72 61 64 65 20 46 61 TheTop: Trade Fa
0ed0: 6e 54 68 65 54 6f 70 22 2c 0d 0a 20 20 22 48 6f nTheTop",.. "Ho
0ee0: 74 46 6f 6f 74 53 70 69 6e 3a 20 46 61 6e 54 68 tFootSpin: FanTh
0ef0: 65 54 6f 70 20 43 65 6e 74 65 72 54 77 6f 54 72 eTop CenterTwoTr
0f00: 61 64 65 20 53 70 69 6e 54 68 65 54 6f 70 22 20 ade SpinTheTop"
0f10: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
0f20: 74 72 69 6e 67 3e 20 64 65 66 69 6e 69 74 69 6f tring> definitio
0f30: 6e 73 28 64 65 66 69 6e 69 74 69 6f 6e 73 5f 2c ns(definitions_,
0f40: 20 64 65 66 69 6e 69 74 69 6f 6e 73 5f 2b 73 69 definitions_+si
0f50: 7a 65 6f 66 28 64 65 66 69 6e 69 74 69 6f 6e 73 zeof(definitions
0f60: 5f 29 2f 73 69 7a 65 6f 66 28 2a 64 65 66 69 6e _)/sizeof(*defin
0f70: 69 74 69 6f 6e 73 5f 29 29 3b 20 0d 0a 09 69 6e itions_)); ...in
0f80: 74 20 6d 20 3d 20 33 3b 20 0d 0a 09 69 6e 74 20 t m = 3; ...int
0f90: 6e 20 3d 20 34 3b 20 0d 0a 09 73 74 72 69 6e 67 n = 4; ...string
0fa0: 20 64 61 6e 63 65 43 61 6c 6c 20 3d 20 22 48 6f danceCall = "Ho
0fb0: 74 46 6f 6f 74 53 70 69 6e 22 3b 20 0d 0a 09 73 tFootSpin"; ...s
0fc0: 74 72 69 6e 67 20 52 65 74 56 61 6c 5f 5b 5d 20 tring RetVal_[]
0fd0: 3d 20 7b 22 46 61 6e 54 68 65 54 6f 70 22 2c 20 = {"FanTheTop",
0fe0: 22 43 65 6e 74 65 72 54 77 6f 54 72 61 64 65 22 "CenterTwoTrade"
0ff0: 2c 20 22 48 69 6e 67 65 22 20 7d 3b 0d 0a 09 20 , "Hinge" };...
1000: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
1010: 20 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c RetVal(RetVal_,
1020: 20 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 RetVal_+sizeof(
1030: 52 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 RetVal_)/sizeof(
1040: 2a 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 *RetVal_)); ...r
1050: 65 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 eturn verify_cas
1060: 65 28 52 65 74 56 61 6c 2c 20 46 72 61 63 74 69 e(RetVal, Fracti
1070: 6f 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 2e 70 61 onalization().pa
1080: 72 74 69 61 6c 28 64 65 66 69 6e 69 74 69 6f 6e rtial(definition
1090: 73 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 65 43 61 s, m, n, danceCa
10a0: 6c 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 ll)); }..int Tes
10b0: 74 5f 28 43 61 73 65 5f 3c 34 3e 29 20 7b 0d 0a t_(Case_<4>) {..
10c0: 09 73 74 72 69 6e 67 20 64 65 66 69 6e 69 74 69 .string definiti
10d0: 6f 6e 73 5f 5b 5d 20 3d 20 7b 20 22 41 3a 20 4f ons_[] = { "A: O
10e0: 6e 65 20 54 77 6f 22 2c 0d 0a 20 20 22 42 3a 20 ne Two",.. "B:
10f0: 4f 6e 65 20 54 77 6f 20 54 68 72 65 65 22 2c 0d One Two Three",.
1100: 0a 20 20 22 43 3a 20 4f 6e 65 20 54 77 6f 20 54 . "C: One Two T
1110: 68 72 65 65 20 46 6f 75 72 22 20 7d 3b 0d 0a 09 hree Four" };...
1120: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
1130: 3e 20 64 65 66 69 6e 69 74 69 6f 6e 73 28 64 65 > definitions(de
1140: 66 69 6e 69 74 69 6f 6e 73 5f 2c 20 64 65 66 69 finitions_, defi
1150: 6e 69 74 69 6f 6e 73 5f 2b 73 69 7a 65 6f 66 28 nitions_+sizeof(
1160: 64 65 66 69 6e 69 74 69 6f 6e 73 5f 29 2f 73 69 definitions_)/si
1170: 7a 65 6f 66 28 2a 64 65 66 69 6e 69 74 69 6f 6e zeof(*definition
1180: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 6d 20 3d s_)); ...int m =
1190: 20 33 3b 20 0d 0a 09 69 6e 74 20 6e 20 3d 20 34 3; ...int n = 4
11a0: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 64 61 6e 63 ; ...string danc
11b0: 65 43 61 6c 6c 20 3d 20 22 43 22 3b 20 0d 0a 09 eCall = "C"; ...
11c0: 73 74 72 69 6e 67 20 52 65 74 56 61 6c 5f 5b 5d string RetVal_[]
11d0: 20 3d 20 7b 22 4f 6e 65 22 2c 20 22 54 77 6f 22 = {"One", "Two"
11e0: 2c 20 22 54 68 72 65 65 22 20 7d 3b 0d 0a 09 20 , "Three" };...
11f0: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
1200: 20 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c RetVal(RetVal_,
1210: 20 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 RetVal_+sizeof(
1220: 52 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 RetVal_)/sizeof(
1230: 2a 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 *RetVal_)); ...r
1240: 65 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 eturn verify_cas
1250: 65 28 52 65 74 56 61 6c 2c 20 46 72 61 63 74 69 e(RetVal, Fracti
1260: 6f 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 2e 70 61 onalization().pa
1270: 72 74 69 61 6c 28 64 65 66 69 6e 69 74 69 6f 6e rtial(definition
1280: 73 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 65 43 61 s, m, n, danceCa
1290: 6c 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 ll)); }..int Tes
12a0: 74 5f 28 43 61 73 65 5f 3c 35 3e 29 20 7b 0d 0a t_(Case_<5>) {..
12b0: 09 73 74 72 69 6e 67 20 64 65 66 69 6e 69 74 69 .string definiti
12c0: 6f 6e 73 5f 5b 5d 20 3d 20 7b 20 22 41 3a 20 58 ons_[] = { "A: X
12d0: 20 59 20 5a 22 2c 0d 0a 20 20 22 42 3a 20 41 20 Y Z",.. "B: A
12e0: 41 20 41 22 20 7d 3b 0d 0a 09 20 20 76 65 63 74 A A" };... vect
12f0: 6f 72 20 3c 73 74 72 69 6e 67 3e 20 64 65 66 69 or <string> defi
1300: 6e 69 74 69 6f 6e 73 28 64 65 66 69 6e 69 74 69 nitions(definiti
1310: 6f 6e 73 5f 2c 20 64 65 66 69 6e 69 74 69 6f 6e ons_, definition
1320: 73 5f 2b 73 69 7a 65 6f 66 28 64 65 66 69 6e 69 s_+sizeof(defini
1330: 74 69 6f 6e 73 5f 29 2f 73 69 7a 65 6f 66 28 2a tions_)/sizeof(*
1340: 64 65 66 69 6e 69 74 69 6f 6e 73 5f 29 29 3b 20 definitions_));
1350: 0d 0a 09 69 6e 74 20 6d 20 3d 20 37 3b 20 0d 0a ...int m = 7; ..
1360: 09 69 6e 74 20 6e 20 3d 20 32 33 3b 20 0d 0a 09 .int n = 23; ...
1370: 73 74 72 69 6e 67 20 64 61 6e 63 65 43 61 6c 6c string danceCall
1380: 20 3d 20 22 42 22 3b 20 0d 0a 09 73 74 72 69 6e = "B"; ...strin
1390: 67 20 52 65 74 56 61 6c 5f 5b 5d 20 3d 20 7b 22 g RetVal_[] = {"
13a0: 49 4c 4c 45 47 41 4c 22 20 7d 3b 0d 0a 09 20 20 ILLEGAL" };...
13b0: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
13c0: 52 65 74 56 61 6c 28 52 65 74 56 61 6c 5f 2c 20 RetVal(RetVal_,
13d0: 52 65 74 56 61 6c 5f 2b 73 69 7a 65 6f 66 28 52 RetVal_+sizeof(R
13e0: 65 74 56 61 6c 5f 29 2f 73 69 7a 65 6f 66 28 2a etVal_)/sizeof(*
13f0: 52 65 74 56 61 6c 5f 29 29 3b 20 0d 0a 09 72 65 RetVal_)); ...re
1400: 74 75 72 6e 20 76 65 72 69 66 79 5f 63 61 73 65 turn verify_case
1410: 28 52 65 74 56 61 6c 2c 20 46 72 61 63 74 69 6f (RetVal, Fractio
1420: 6e 61 6c 69 7a 61 74 69 6f 6e 28 29 2e 70 61 72 nalization().par
1430: 74 69 61 6c 28 64 65 66 69 6e 69 74 69 6f 6e 73 tial(definitions
1440: 2c 20 6d 2c 20 6e 2c 20 64 61 6e 63 65 43 61 6c , m, n, danceCal
1450: 6c 29 29 3b 20 7d 0d 0a 69 6e 74 20 54 65 73 74 l)); }..int Test
1460: 5f 28 43 61 73 65 5f 3c 36 3e 29 20 7b 0d 0a 09 _(Case_<6>) {...
1470: 73 74 72 69 6e 67 20 64 65 66 69 6e 69 74 69 6f string definitio
1480: 6e 73 5f 5b 5d 20 3d 20 7b 20 22 41 3a 20 42 20 ns_[] = { "A: B
1490: 43 22 2c 0d 0a 20 20 22 44 3a 20 45 20 46 22 20 C",.. "D: E F"
14a0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
14b0: 74 72 69 6e 67 3e 20 64 65 66 69 6e 69 74 69 6f tring> definitio
14c0: 6e 73 28 64 65 66 69 6e 69 74 69 6f 6e 73 5f 2c ns(definitions_,
14d0: 20 64 65 66 69 6e 69 74 69 6f 6e 73 5f 2b 73 69 definitions_+si
14e0: 7a 65 6f 66 28 64 65 66 69 6e 69 74 69 6f 6e 73 zeof(definitions
14f0: 5f 29 2f 73 69 7a 65 6f 66 28 2a 64 65 66 69 6e _)/sizeof(*defin
1500: 69 74 69 6f 6e 73 5f 29 29 3b 20 0d 0a 09 69 6e itions_)); ...in
1510: 74 20 6d 20 3d 20 31 3b 20 0d 0a 09 69 6e 74 20 t m = 1; ...int
1520: 6e 20 3d 20 32 3b 20 0d 0a 09 73 74 72 69 6e 67 n = 2; ...string
1530: 20 64 61 6e 63 65 43 61 6c 6c 20 3d 20 22 47 22 danceCall = "G"
1540: 3b 20 0d 0a 09 73 74 72 69 6e 67 20 52 65 74 56 ; ...string RetV
1550: 61 6c 5f 5b 5d 20 3d 20 7b 22 49 4c 4c 45 47 41 al_[] = {"ILLEGA
1560: 4c 22 20 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 L" };... vector
1570: 20 3c 73 74 72 69 6e 67 3e 20 52 65 74 56 61 6c <string> RetVal
1580: 28 52 65 74 56 61 6c 5f 2c 20 52 65 74 56 61 6c (RetVal_, RetVal
1590: 5f 2b 73 69 7a 65 6f 66 28 52 65 74 56 61 6c 5f _+sizeof(RetVal_
15a0: 29 2f 73 69 7a 65 6f 66 28 2a 52 65 74 56 61 6c )/sizeof(*RetVal
15b0: 5f 29 29 3b 20 0d 0a 09 72 65 74 75 72 6e 20 76 _)); ...return v
15c0: 65 72 69 66 79 5f 63 61 73 65 28 52 65 74 56 61 erify_case(RetVa
15d0: 6c 2c 20 46 72 61 63 74 69 6f 6e 61 6c 69 7a 61 l, Fractionaliza
15e0: 74 69 6f 6e 28 29 2e 70 61 72 74 69 61 6c 28 64 tion().partial(d
15f0: 65 66 69 6e 69 74 69 6f 6e 73 2c 20 6d 2c 20 6e efinitions, m, n
1600: 2c 20 64 61 6e 63 65 43 61 6c 6c 29 29 3b 20 7d , danceCall)); }
1610: 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 3c 69 6e 74 ....template<int
1620: 20 4e 3e 20 76 6f 69 64 20 52 75 6e 5f 28 29 20 N> void Run_()
1630: 7b 20 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 { cerr << "Test
1640: 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 Case #" << N <<
1650: 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 "..." << flush;
1660: 54 65 73 74 5f 28 43 61 73 65 5f 3c 4e 3e 28 29 Test_(Case_<N>()
1670: 29 3b 20 52 75 6e 5f 3c 73 69 7a 65 6f 66 28 54 ); Run_<sizeof(T
1680: 65 73 74 5f 28 43 61 73 65 5f 3c 4e 2b 31 3e 28 est_(Case_<N+1>(
1690: 29 29 29 3d 3d 31 20 3f 20 2d 31 20 3a 20 4e 2b )))==1 ? -1 : N+
16a0: 31 3e 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 1>(); }..templat
16b0: 65 3c 3e 20 20 20 20 20 20 76 6f 69 64 20 52 75 e<> void Ru
16c0: 6e 5f 3c 2d 31 3e 28 29 20 7b 7d 0d 0a 69 6e 74 n_<-1>() {}..int
16d0: 20 6d 61 69 6e 28 29 20 7b 20 52 75 6e 5f 3c 30 main() { Run_<0
16e0: 3e 28 29 3b 20 7d 0d 0a 2f 2f 20 45 4e 44 20 43 >(); }..// END C
16f0: 55 54 20 48 45 52 45 0d 0a 0d 0a UT HERE....