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 74 79 70 65 64 65 66 20 CMP;....typedef
01a0: 69 6e 74 20 20 20 20 20 20 20 20 20 20 20 76 65 int ve
01b0: 72 74 3b 0d 0a 74 79 70 65 64 65 66 20 76 65 72 rt;..typedef ver
01c0: 74 20 20 20 20 20 20 20 20 20 20 65 64 67 65 3b t edge;
01d0: 0d 0a 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 ..typedef vector
01e0: 3c 65 64 67 65 3e 20 20 65 64 67 65 73 3b 0d 0a <edge> edges;..
01f0: 74 79 70 65 64 65 66 20 76 65 63 74 6f 72 3c 65 typedef vector<e
0200: 64 67 65 73 3e 20 67 72 61 70 68 3b 0d 0a 0d 0a dges> graph;....
0210: 62 6f 6f 6c 20 61 75 67 6d 65 6e 74 28 20 67 72 bool augment( gr
0220: 61 70 68 26 20 47 2c 20 69 6e 74 20 76 2c 20 76 aph& G, int v, v
0230: 65 63 74 6f 72 3c 76 65 72 74 3e 26 20 6d 61 74 ector<vert>& mat
0240: 63 68 54 6f 2c 20 62 6f 6f 6c 20 76 69 73 69 74 chTo, bool visit
0250: 65 64 5b 5d 20 29 0d 0a 7b 0d 0a 09 66 6f 72 28 ed[] )..{...for(
0260: 69 6e 74 20 69 3d 30 3b 20 69 3c 47 5b 76 5d 2e int i=0; i<G[v].
0270: 73 69 7a 65 28 29 3b 20 2b 2b 69 29 20 7b 0d 0a size(); ++i) {..
0280: 09 09 76 65 72 74 20 75 20 3d 20 47 5b 76 5d 5b ..vert u = G[v][
0290: 69 5d 3b 0d 0a 09 09 69 66 28 20 76 69 73 69 74 i];....if( visit
02a0: 65 64 5b 75 5d 20 29 20 63 6f 6e 74 69 6e 75 65 ed[u] ) continue
02b0: 3b 0d 0a 09 09 76 69 73 69 74 65 64 5b 75 5d 20 ;....visited[u]
02c0: 3d 20 74 72 75 65 3b 0d 0a 0d 0a 09 09 69 66 28 = true;......if(
02d0: 20 6d 61 74 63 68 54 6f 5b 75 5d 3c 30 20 7c 7c matchTo[u]<0 ||
02e0: 20 61 75 67 6d 65 6e 74 28 47 2c 20 6d 61 74 63 augment(G, matc
02f0: 68 54 6f 5b 75 5d 2c 20 6d 61 74 63 68 54 6f 2c hTo[u], matchTo,
0300: 20 76 69 73 69 74 65 64 29 20 29 0d 0a 09 09 09 visited) ).....
0310: 7b 20 6d 61 74 63 68 54 6f 5b 76 5d 3d 75 2c 20 { matchTo[v]=u,
0320: 6d 61 74 63 68 54 6f 5b 75 5d 3d 76 3b 20 72 65 matchTo[u]=v; re
0330: 74 75 72 6e 20 74 72 75 65 3b 20 7d 0d 0a 09 7d turn true; }...}
0340: 0d 0a 09 72 65 74 75 72 6e 20 66 61 6c 73 65 3b ...return false;
0350: 0d 0a 7d 0d 0a 0d 0a 74 65 6d 70 6c 61 74 65 3c ..}....template<
0360: 69 6e 74 20 4e 56 3e 0d 0a 69 6e 74 20 62 69 4d int NV>..int biM
0370: 61 74 63 68 28 20 67 72 61 70 68 26 20 47 2c 20 atch( graph& G,
0380: 69 6e 74 20 4c 20 29 20 2f 2f 20 5b 30 2c 4c 29 int L ) // [0,L)
0390: 3a 6c 65 66 74 2c 20 5b 4c 2c 3f 29 3a 72 69 67 :left, [L,?):rig
03a0: 68 74 0d 0a 7b 0d 0a 09 76 65 63 74 6f 72 3c 76 ht..{...vector<v
03b0: 65 72 74 3e 20 6d 61 74 63 68 54 6f 28 47 2e 73 ert> matchTo(G.s
03c0: 69 7a 65 28 29 2c 20 2d 31 29 3b 0d 0a 09 69 6e ize(), -1);...in
03d0: 74 20 61 6e 73 20 3d 20 30 3b 0d 0a 09 66 6f 72 t ans = 0;...for
03e0: 28 76 65 72 74 20 76 3d 30 3b 20 76 3c 4c 3b 20 (vert v=0; v<L;
03f0: 2b 2b 76 29 20 7b 0d 0a 09 09 62 6f 6f 6c 20 76 ++v) {....bool v
0400: 69 73 69 74 65 64 5b 4e 56 5d 20 3d 20 7b 7d 3b isited[NV] = {};
0410: 0d 0a 09 09 69 66 28 20 61 75 67 6d 65 6e 74 28 ....if( augment(
0420: 47 2c 20 76 2c 20 6d 61 74 63 68 54 6f 2c 20 76 G, v, matchTo, v
0430: 69 73 69 74 65 64 29 20 29 0d 0a 09 09 09 2b 2b isited) ).....++
0440: 61 6e 73 3b 0d 0a 09 7d 0d 0a 09 72 65 74 75 72 ans;...}...retur
0450: 6e 20 61 6e 73 3b 0d 0a 7d 0d 0a 0d 0a 69 6e 74 n ans;..}....int
0460: 20 62 69 74 63 6e 74 28 4c 4c 20 78 29 0d 0a 7b bitcnt(LL x)..{
0470: 0d 0a 09 69 6e 74 20 63 20 3d 20 30 3b 0d 0a 09 ...int c = 0;...
0480: 66 6f 72 28 3b 20 78 3b 20 78 3e 3e 3d 31 29 0d for(; x; x>>=1).
0490: 0a 09 09 63 20 2b 3d 20 78 26 31 3b 0d 0a 09 72 ...c += x&1;...r
04a0: 65 74 75 72 6e 20 63 3b 0d 0a 7d 0d 0a 0d 0a 63 eturn c;..}....c
04b0: 6c 61 73 73 20 4d 61 6c 6c 53 65 63 75 72 69 74 lass MallSecurit
04c0: 79 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 70 61 y { public:...pa
04d0: 69 72 3c 67 72 61 70 68 2c 20 69 6e 74 3e 20 67 ir<graph, int> g
04e0: 65 6e 65 72 61 74 65 42 69 70 61 72 74 69 74 65 enerateBipartite
04f0: 47 72 61 70 68 28 0d 0a 09 09 63 6f 6e 73 74 20 Graph(....const
0500: 76 65 63 74 6f 72 3c 69 6e 74 3e 26 20 41 73 2c vector<int>& As,
0510: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e const vector<in
0520: 74 3e 26 20 42 73 2c 20 63 6f 6e 73 74 20 76 65 t>& Bs, const ve
0530: 63 74 6f 72 3c 69 6e 74 3e 26 20 43 73 2c 20 63 ctor<int>& Cs, c
0540: 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e 74 3e onst vector<int>
0550: 26 20 44 73 2c 0d 0a 09 09 63 6f 6e 73 74 20 76 & Ds,....const v
0560: 65 63 74 6f 72 3c 69 6e 74 3e 26 20 4b 73 2c 20 ector<int>& Ks,
0570: 69 6e 74 20 6d 73 66 2c 20 69 6e 74 20 6d 61 73 int msf, int mas
0580: 6b 20 29 0d 0a 09 7b 0d 0a 09 09 2f 2f 20 63 6f k )...{....// co
0590: 6e 73 74 72 75 63 74 20 61 20 62 69 70 61 72 74 nstruct a bipart
05a0: 69 74 65 20 67 72 61 70 68 20 72 65 70 72 65 73 ite graph repres
05b0: 65 6e 74 61 74 69 6f 6e 2c 20 69 6e 20 77 68 69 entation, in whi
05c0: 63 68 0d 0a 09 09 2f 2f 20 20 20 2d 20 22 65 76 ch....// - "ev
05d0: 65 6e 22 2d 66 6c 6f 6f 72 20 73 74 61 74 69 6f en"-floor statio
05e0: 6e 73 20 67 6f 20 74 6f 20 74 68 65 20 6c 65 66 ns go to the lef
05f0: 74 0d 0a 09 09 2f 2f 20 20 20 2d 20 22 6f 64 64 t....// - "odd
0600: 22 2d 66 6c 6f 6f 72 20 73 74 61 74 69 6f 6e 73 "-floor stations
0610: 20 67 6f 20 74 6f 20 74 68 65 20 72 69 67 68 74 go to the right
0620: 0d 0a 09 09 2f 2f 20 68 65 72 65 20 66 6c 6f 6f ....// here floo
0630: 72 20 6e 75 6d 62 65 72 20 69 73 20 6e 6f 72 6d r number is norm
0640: 61 6c 69 7a 65 64 20 62 79 20 72 6f 74 61 74 69 alized by rotati
0650: 6e 67 20 74 68 65 20 6d 73 66 2d 74 68 20 66 6c ng the msf-th fl
0660: 6f 6f 72 20 74 6f 20 7a 65 72 6f 0d 0a 09 09 23 oor to zero....#
0670: 64 65 66 69 6e 65 20 4c 52 28 66 29 20 28 28 28 define LR(f) (((
0680: 66 29 3e 6d 73 66 20 3f 20 28 66 29 2d 6d 73 66 f)>msf ? (f)-msf
0690: 20 3a 20 4b 73 2e 73 69 7a 65 28 29 2d 6d 73 66 : Ks.size()-msf
06a0: 2b 28 66 29 29 25 32 29 0d 0a 0d 0a 09 09 2f 2f +(f))%2)......//
06b0: 20 61 73 73 69 67 6e 20 69 6e 74 65 72 67 65 72 assign interger
06c0: 2d 49 44 20 66 6f 72 20 65 61 63 68 20 22 63 68 -ID for each "ch
06d0: 6f 6f 73 61 62 6c 65 22 20 73 74 61 74 69 6f 6e oosable" station
06e0: 2c 20 69 2e 65 2e 2c 0d 0a 09 09 2f 2f 20 61 20 , i.e.,....// a
06f0: 73 74 61 74 69 6f 6e 20 77 68 69 63 68 20 69 73 station which is
0700: 20 6e 6f 74 20 61 74 20 6d 73 66 20 61 6e 64 20 not at msf and
0710: 69 73 20 6e 6f 74 20 63 6f 6e 6e 65 63 74 65 64 is not connected
0720: 20 74 6f 20 61 20 27 6d 61 73 6b 27 65 64 20 73 to a 'mask'ed s
0730: 74 61 74 69 6f 6e 20 6f 6e 20 6d 73 66 0d 0a 09 tation on msf...
0740: 09 6d 61 70 3c 70 61 69 72 3c 69 6e 74 2c 69 6e .map<pair<int,in
0750: 74 3e 2c 69 6e 74 3e 20 49 44 3b 0d 0a 09 09 69 t>,int> ID;....i
0760: 6e 74 20 6e 65 78 74 49 44 5b 32 5d 20 3d 20 7b nt nextID[2] = {
0770: 30 2c 30 7d 3b 20 2f 2f 20 75 73 65 20 64 69 66 0,0}; // use dif
0780: 66 65 72 65 6e 74 20 73 65 74 73 20 6f 66 20 49 ferent sets of I
0790: 44 73 20 66 6f 72 20 65 76 65 6e 2f 6f 64 64 20 Ds for even/odd
07a0: 66 6c 6f 6f 72 73 0d 0a 09 09 7b 0d 0a 09 09 09 floors....{.....
07b0: 66 6f 72 28 69 6e 74 20 66 3d 30 3b 20 66 3c 4b for(int f=0; f<K
07c0: 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 66 29 20 69 s.size(); ++f) i
07d0: 66 28 20 66 20 21 3d 20 6d 73 66 20 29 0d 0a 09 f( f != msf )...
07e0: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
07f0: 3c 4b 73 5b 66 5d 3b 20 2b 2b 69 29 0d 0a 09 09 <Ks[f]; ++i)....
0800: 09 7b 0d 0a 09 09 09 09 62 6f 6f 6c 20 63 61 6e .{......bool can
0810: 5f 75 73 65 20 3d 20 74 72 75 65 3b 0d 0a 09 09 _use = true;....
0820: 09 09 66 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a ..for(int j=0; j
0830: 3c 41 73 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 <As.size(); ++j)
0840: 0d 0a 09 09 09 09 09 69 66 28 20 43 73 5b 6a 5d .......if( Cs[j]
0850: 3d 3d 66 20 26 26 20 41 73 5b 6a 5d 3d 3d 69 20 ==f && As[j]==i
0860: 26 26 20 44 73 5b 6a 5d 3d 3d 6d 73 66 20 26 26 && Ds[j]==msf &&
0870: 20 28 6d 61 73 6b 20 26 20 31 3c 3c 42 73 5b 6a (mask & 1<<Bs[j
0880: 5d 29 0d 0a 09 09 09 09 09 20 7c 7c 20 44 73 5b ])....... || Ds[
0890: 6a 5d 3d 3d 66 20 26 26 20 42 73 5b 6a 5d 3d 3d j]==f && Bs[j]==
08a0: 69 20 26 26 20 43 73 5b 6a 5d 3d 3d 6d 73 66 20 i && Cs[j]==msf
08b0: 26 26 20 28 6d 61 73 6b 20 26 20 31 3c 3c 41 73 && (mask & 1<<As
08c0: 5b 6a 5d 29 20 29 0d 0a 09 09 09 09 09 20 63 61 [j]) )....... ca
08d0: 6e 5f 75 73 65 20 3d 20 66 61 6c 73 65 3b 0d 0a n_use = false;..
08e0: 09 09 09 09 69 66 28 20 63 61 6e 5f 75 73 65 20 ....if( can_use
08f0: 29 0d 0a 09 09 09 09 09 49 44 5b 6d 61 6b 65 5f ).......ID[make_
0900: 70 61 69 72 28 66 2c 69 29 5d 20 3d 20 6e 65 78 pair(f,i)] = nex
0910: 74 49 44 5b 4c 52 28 66 29 5d 2b 2b 3b 0d 0a 09 tID[LR(f)]++;...
0920: 09 09 7d 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 2f 2f ..}....}......//
0930: 20 74 68 65 6e 20 63 72 65 61 74 65 20 74 68 65 then create the
0940: 20 67 72 61 70 68 0d 0a 09 09 67 72 61 70 68 20 graph....graph
0950: 47 28 20 6e 65 78 74 49 44 5b 30 5d 20 2b 20 6e G( nextID[0] + n
0960: 65 78 74 49 44 5b 31 5d 20 29 3b 0d 0a 09 09 66 extID[1] );....f
0970: 6f 72 28 69 6e 74 20 6a 3d 30 3b 20 6a 3c 41 73 or(int j=0; j<As
0980: 2e 73 69 7a 65 28 29 3b 20 2b 2b 6a 29 0d 0a 09 .size(); ++j)...
0990: 09 7b 0d 0a 09 09 09 70 61 69 72 3c 69 6e 74 2c .{.....pair<int,
09a0: 69 6e 74 3e 20 70 28 43 73 5b 6a 5d 2c 20 41 73 int> p(Cs[j], As
09b0: 5b 6a 5d 29 3b 0d 0a 09 09 09 70 61 69 72 3c 69 [j]);.....pair<i
09c0: 6e 74 2c 69 6e 74 3e 20 71 28 44 73 5b 6a 5d 2c nt,int> q(Ds[j],
09d0: 20 42 73 5b 6a 5d 29 3b 0d 0a 09 09 09 69 66 28 Bs[j]);.....if(
09e0: 20 49 44 2e 63 6f 75 6e 74 28 70 29 20 26 26 20 ID.count(p) &&
09f0: 49 44 2e 63 6f 75 6e 74 28 71 29 20 29 0d 0a 09 ID.count(q) )...
0a00: 09 09 7b 0d 0a 09 09 09 09 69 6e 74 20 70 69 64 ..{......int pid
0a10: 20 3d 20 49 44 5b 70 5d 20 2b 20 28 4c 52 28 43 = ID[p] + (LR(C
0a20: 73 5b 6a 5d 29 20 3f 20 6e 65 78 74 49 44 5b 30 s[j]) ? nextID[0
0a30: 5d 20 3a 20 30 29 3b 0d 0a 09 09 09 09 69 6e 74 ] : 0);......int
0a40: 20 71 69 64 20 3d 20 49 44 5b 71 5d 20 2b 20 28 qid = ID[q] + (
0a50: 4c 52 28 44 73 5b 6a 5d 29 20 3f 20 6e 65 78 74 LR(Ds[j]) ? next
0a60: 49 44 5b 30 5d 20 3a 20 30 29 3b 0d 0a 09 09 09 ID[0] : 0);.....
0a70: 09 47 5b 70 69 64 5d 2e 70 75 73 68 5f 62 61 63 .G[pid].push_bac
0a80: 6b 28 71 69 64 29 3b 0d 0a 09 09 09 09 47 5b 71 k(qid);......G[q
0a90: 69 64 5d 2e 70 75 73 68 5f 62 61 63 6b 28 70 69 id].push_back(pi
0aa0: 64 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d 0d 0a d);.....}....}..
0ab0: 09 09 72 65 74 75 72 6e 20 6d 61 6b 65 5f 70 61 ..return make_pa
0ac0: 69 72 28 47 2c 20 6e 65 78 74 49 44 5b 30 5d 29 ir(G, nextID[0])
0ad0: 3b 0d 0a 09 7d 0d 0a 0d 0a 09 69 6e 74 20 6d 61 ;...}.....int ma
0ae0: 78 47 75 61 72 64 73 28 69 6e 74 20 4e 2c 20 76 xGuards(int N, v
0af0: 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 65 ector <string> e
0b00: 73 63 44 65 73 63 72 69 70 74 69 6f 6e 29 20 0d scDescription) .
0b10: 0a 09 7b 0d 0a 09 09 2f 2f 20 70 61 72 73 65 20 ..{....// parse
0b20: 74 68 65 20 69 6e 70 75 74 0d 0a 09 09 76 65 63 the input....vec
0b30: 74 6f 72 3c 69 6e 74 3e 20 41 73 2c 20 42 73 2c tor<int> As, Bs,
0b40: 20 43 73 2c 20 44 73 2c 20 4b 73 28 4e 29 3b 0d Cs, Ds, Ks(N);.
0b50: 0a 09 09 7b 0d 0a 09 09 09 73 74 72 69 6e 67 73 ...{.....strings
0b60: 74 72 65 61 6d 20 73 69 6e 3b 0d 0a 09 09 09 63 tream sin;.....c
0b70: 6f 70 79 28 20 65 73 63 44 65 73 63 72 69 70 74 opy( escDescript
0b80: 69 6f 6e 2e 62 65 67 69 6e 28 29 2c 20 65 73 63 ion.begin(), esc
0b90: 44 65 73 63 72 69 70 74 69 6f 6e 2e 65 6e 64 28 Description.end(
0ba0: 29 2c 20 6f 73 74 72 65 61 6d 5f 69 74 65 72 61 ), ostream_itera
0bb0: 74 6f 72 3c 73 74 72 69 6e 67 3e 28 73 69 6e 2c tor<string>(sin,
0bc0: 22 22 29 20 29 3b 0d 0a 0d 0a 09 09 09 66 6f 72 "") );.......for
0bd0: 28 69 6e 74 20 41 2c 42 2c 43 3b 20 73 69 6e 3e (int A,B,C; sin>
0be0: 3e 41 3e 3e 42 3e 3e 43 3b 20 29 0d 0a 09 09 09 >A>>B>>C; ).....
0bf0: 7b 0d 0a 09 09 09 09 7b 63 68 61 72 20 63 6f 6d {......{char com
0c00: 6d 61 3b 20 73 69 6e 3e 3e 63 6f 6d 6d 61 3b 7d ma; sin>>comma;}
0c10: 0d 0a 09 09 09 09 2d 2d 41 2c 20 2d 2d 42 2c 20 ......--A, --B,
0c20: 2d 2d 43 3b 20 69 6e 74 20 44 3d 28 43 2b 31 29 --C; int D=(C+1)
0c30: 25 4e 3b 20 2f 2f 20 74 6f 20 30 2d 6f 72 69 67 %N; // to 0-orig
0c40: 6e 0d 0a 09 09 09 09 41 73 2e 70 75 73 68 5f 62 n......As.push_b
0c50: 61 63 6b 28 41 29 3b 0d 0a 09 09 09 09 42 73 2e ack(A);......Bs.
0c60: 70 75 73 68 5f 62 61 63 6b 28 42 29 3b 0d 0a 09 push_back(B);...
0c70: 09 09 09 43 73 2e 70 75 73 68 5f 62 61 63 6b 28 ...Cs.push_back(
0c80: 43 29 3b 0d 0a 09 09 09 09 44 73 2e 70 75 73 68 C);......Ds.push
0c90: 5f 62 61 63 6b 28 44 29 3b 0d 0a 09 09 09 09 4b _back(D);......K
0ca0: 73 5b 43 5d 20 3d 20 6d 61 78 28 4b 73 5b 43 5d s[C] = max(Ks[C]
0cb0: 2c 20 41 2b 31 29 3b 0d 0a 09 09 09 09 4b 73 5b , A+1);......Ks[
0cc0: 44 5d 20 3d 20 6d 61 78 28 4b 73 5b 44 5d 2c 20 D] = max(Ks[D],
0cd0: 42 2b 31 29 3b 0d 0a 09 09 09 7d 0d 0a 09 09 7d B+1);.....}....}
0ce0: 0d 0a 0d 0a 09 09 2f 2f 20 74 68 65 20 6d 6f 73 ......// the mos
0cf0: 74 20 73 69 6d 70 6c 65 20 66 6c 6f 6f 72 2c 20 t simple floor,
0d00: 77 68 65 72 65 20 74 68 65 20 6e 75 6d 62 65 72 where the number
0d10: 20 4b 73 5b 6d 73 66 5d 20 6f 66 20 73 74 61 74 Ks[msf] of stat
0d20: 69 6f 6e 73 20 69 73 20 74 68 65 20 6c 65 61 73 ions is the leas
0d30: 74 0d 0a 09 09 69 6e 74 20 6d 73 66 20 3d 20 6d t....int msf = m
0d40: 69 6e 5f 65 6c 65 6d 65 6e 74 28 4b 73 2e 62 65 in_element(Ks.be
0d50: 67 69 6e 28 29 2c 20 4b 73 2e 65 6e 64 28 29 29 gin(), Ks.end())
0d60: 20 2d 20 4b 73 2e 62 65 67 69 6e 28 29 3b 0d 0a - Ks.begin();..
0d70: 0d 0a 09 09 2f 2f 20 74 72 79 20 61 6c 6c 20 70 ....// try all p
0d80: 6f 73 73 69 62 69 6c 69 74 69 65 73 20 61 74 20 ossibilities at
0d90: 74 68 65 20 6d 73 66 2d 74 68 20 66 6c 6f 6f 72 the msf-th floor
0da0: 0d 0a 09 09 73 69 7a 65 5f 74 20 61 6e 73 77 65 ....size_t answe
0db0: 72 20 3d 20 30 3b 0d 0a 09 09 66 6f 72 28 69 6e r = 0;....for(in
0dc0: 74 20 6d 61 73 6b 3d 30 3b 20 6d 61 73 6b 3c 28 t mask=0; mask<(
0dd0: 31 3c 3c 4b 73 5b 6d 73 66 5d 29 3b 20 2b 2b 6d 1<<Ks[msf]); ++m
0de0: 61 73 6b 29 0d 0a 09 09 7b 0d 0a 09 09 09 2f 2f ask)....{.....//
0df0: 20 74 68 65 6e 20 74 68 65 20 72 65 73 74 20 6f then the rest o
0e00: 66 20 74 68 65 20 70 61 72 74 20 62 65 63 6f 6d f the part becom
0e10: 65 73 20 61 20 62 69 70 61 72 74 69 74 65 20 67 es a bipartite g
0e20: 72 61 70 68 0d 0a 09 09 09 70 61 69 72 3c 67 72 raph.....pair<gr
0e30: 61 70 68 2c 20 69 6e 74 3e 20 47 20 3d 20 67 65 aph, int> G = ge
0e40: 6e 65 72 61 74 65 42 69 70 61 72 74 69 74 65 47 nerateBipartiteG
0e50: 72 61 70 68 28 41 73 2c 42 73 2c 43 73 2c 44 73 raph(As,Bs,Cs,Ds
0e60: 2c 4b 73 2c 6d 73 66 2c 6d 61 73 6b 29 3b 0d 0a ,Ks,msf,mask);..
0e70: 0d 0a 09 09 09 2f 2f 20 7c 4d 61 78 49 6e 64 65 .....// |MaxInde
0e80: 6e 65 70 64 65 6e 74 53 65 74 7c 20 3d 3d 20 7c nepdentSet| == |
0e90: 56 7c 2d 7c 4d 69 6e 43 6f 76 65 72 7c 20 3d 28 V|-|MinCover| =(
0ea0: 66 6f 72 20 62 69 70 61 72 74 69 74 65 20 67 72 for bipartite gr
0eb0: 61 70 68 73 29 3d 20 7c 56 7c 2d 7c 4d 61 78 4d aphs)= |V|-|MaxM
0ec0: 61 74 63 68 7c 0d 0a 09 09 09 61 6e 73 77 65 72 atch|.....answer
0ed0: 20 3d 20 6d 61 78 28 61 6e 73 77 65 72 2c 20 47 = max(answer, G
0ee0: 2e 66 69 72 73 74 2e 73 69 7a 65 28 29 20 2d 20 .first.size() -
0ef0: 62 69 4d 61 74 63 68 3c 31 30 30 3e 28 47 2e 66 biMatch<100>(G.f
0f00: 69 72 73 74 2c 47 2e 73 65 63 6f 6e 64 29 20 2b irst,G.second) +
0f10: 20 62 69 74 63 6e 74 28 6d 61 73 6b 29 29 3b 0d bitcnt(mask));.
0f20: 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 61 ...}....return a
0f30: 6e 73 77 65 72 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a nswer;...}..};..
0f40: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0f50: 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 ERE..#include <c
0f60: 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 time>..double st
0f70: 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 art_time; string
0f80: 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 timer().. { ost
0f90: 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f ringstream os; o
0fa0: 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 s << " (" << int
0fb0: 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f ((clock()-start_
0fc0: 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 time)/CLOCKS_PER
0fd0: 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 _SEC*1000) << "
0fe0: 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f msec)"; return o
0ff0: 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 s.str(); }..temp
1000: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e late<typename T>
1010: 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 ostream& operat
1020: 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 or<<(ostream& os
1030: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
1040: 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 >& v).. { os <<
1050: 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 "{ ";.. for(ty
1060: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e pename vector<T>
1070: 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 ::const_iterator
1080: 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 it=v.begin(); i
1090: 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 t!=v.end(); ++it
10a0: 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 ).. os << '\"'
10b0: 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 << *it << '\"'
10c0: 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 << (it+1==v.end(
10d0: 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 ) ? "" : ", ");
10e0: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
10f0: 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 rn os; }..void v
1100: 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 erify_case(const
1110: 20 69 6e 74 26 20 45 78 70 65 63 74 65 64 2c 20 int& Expected,
1120: 63 6f 6e 73 74 20 69 6e 74 26 20 52 65 63 65 69 const int& Recei
1130: 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b ved) {.. bool ok
1140: 20 3d 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 = (Expected ==
1150: 52 65 63 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 Received);.. if(
1160: 6f 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 ok) cerr << "PAS
1170: 53 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 SED" << timer()
1180: 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b << endl; else {
1190: 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 cerr << "FAILED
11a0: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
11b0: 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 endl;.. cerr <<
11c0: 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 "\to: \"" << Exp
11d0: 65 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c ected << '\"' <<
11e0: 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c endl << "\tx: \
11f0: 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c "" << Received <
1200: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 < '\"' << endl;
1210: 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 } }..#define CAS
1220: 45 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 E(N) {cerr << "T
1230: 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e est Case #" << N
1240: 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 << "..." << flu
1250: 73 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 sh; start_time=c
1260: 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 lock();..#define
1270: 20 45 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 END. verify_cas
1280: 65 28 5f 2c 20 4d 61 6c 6c 53 65 63 75 72 69 74 e(_, MallSecurit
1290: 79 28 29 2e 6d 61 78 47 75 61 72 64 73 28 4e 2c y().maxGuards(N,
12a0: 20 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e 29 escDescription)
12b0: 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b );}..int main(){
12c0: 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e ....CASE(0)...in
12d0: 74 20 4e 20 3d 20 31 30 3b 20 0d 0a 09 73 74 72 t N = 10; ...str
12e0: 69 6e 67 20 65 73 63 44 65 73 63 72 69 70 74 69 ing escDescripti
12f0: 6f 6e 5f 5b 5d 20 3d 20 7b 22 31 20 31 20 31 2c on_[] = {"1 1 1,
1300: 31 20 31 20 32 2c 31 20 31 20 33 2c 31 20 31 20 1 1 2,1 1 3,1 1
1310: 34 2c 31 20 31 20 35 2c 31 20 31 20 36 2c 31 20 4,1 1 5,1 1 6,1
1320: 31 20 37 2c 31 20 31 20 38 2c 31 20 22 2c 20 0d 1 7,1 1 8,1 ", .
1330: 0a 20 22 31 20 39 2c 31 20 31 20 31 30 22 7d 3b . "1 9,1 1 10"};
1340: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1350: 69 6e 67 3e 20 65 73 63 44 65 73 63 72 69 70 74 ing> escDescript
1360: 69 6f 6e 28 65 73 63 44 65 73 63 72 69 70 74 69 ion(escDescripti
1370: 6f 6e 5f 2c 20 65 73 63 44 65 73 63 72 69 70 74 on_, escDescript
1380: 69 6f 6e 5f 2b 73 69 7a 65 6f 66 28 65 73 63 44 ion_+sizeof(escD
1390: 65 73 63 72 69 70 74 69 6f 6e 5f 29 2f 73 69 7a escription_)/siz
13a0: 65 6f 66 28 2a 65 73 63 44 65 73 63 72 69 70 74 eof(*escDescript
13b0: 69 6f 6e 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f ion_)); ...int _
13c0: 20 3d 20 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 = 5; ..END..CAS
13d0: 45 28 31 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 31 E(1)...int N = 1
13e0: 31 3b 20 0d 0a 09 73 74 72 69 6e 67 20 65 73 63 1; ...string esc
13f0: 44 65 73 63 72 69 70 74 69 6f 6e 5f 5b 5d 20 3d Description_[] =
1400: 20 7b 22 31 20 31 20 31 2c 31 20 31 20 32 2c 31 {"1 1 1,1 1 2,1
1410: 20 31 20 33 2c 31 20 31 20 34 2c 31 20 31 20 35 1 3,1 1 4,1 1 5
1420: 2c 31 20 31 20 36 2c 31 20 31 20 37 2c 31 20 31 ,1 1 6,1 1 7,1 1
1430: 20 38 2c 31 20 22 2c 20 0d 0a 20 22 31 20 39 2c 8,1 ", .. "1 9,
1440: 31 20 31 20 31 30 22 7d 3b 0d 0a 09 20 20 76 65 1 1 10"};... ve
1450: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 65 73 ctor <string> es
1460: 63 44 65 73 63 72 69 70 74 69 6f 6e 28 65 73 63 cDescription(esc
1470: 44 65 73 63 72 69 70 74 69 6f 6e 5f 2c 20 65 73 Description_, es
1480: 63 44 65 73 63 72 69 70 74 69 6f 6e 5f 2b 73 69 cDescription_+si
1490: 7a 65 6f 66 28 65 73 63 44 65 73 63 72 69 70 74 zeof(escDescript
14a0: 69 6f 6e 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 73 ion_)/sizeof(*es
14b0: 63 44 65 73 63 72 69 70 74 69 6f 6e 5f 29 29 3b cDescription_));
14c0: 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 36 3b 20 0d ...int _ = 6; .
14d0: 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 .END..CASE(2)...
14e0: 69 6e 74 20 4e 20 3d 20 31 30 3b 20 0d 0a 09 73 int N = 10; ...s
14f0: 74 72 69 6e 67 20 65 73 63 44 65 73 63 72 69 70 tring escDescrip
1500: 74 69 6f 6e 5f 5b 5d 20 3d 20 7b 22 31 20 31 20 tion_[] = {"1 1
1510: 37 2c 31 20 32 20 39 2c 32 20 31 22 2c 20 0d 0a 7,1 2 9,2 1", ..
1520: 20 22 20 38 2c 31 20 32 20 36 2c 31 20 31 20 38 " 8,1 2 6,1 1 8
1530: 2c 31 20 32 20 33 2c 31 20 32 20 32 2c 32 20 22 ,1 2 3,1 2 2,2 "
1540: 2c 20 0d 0a 20 22 32 20 34 2c 31 20 31 20 31 2c , .. "2 4,1 1 1,
1550: 32 20 31 20 32 2c 33 20 32 20 33 2c 31 20 31 20 2 1 2,3 2 3,1 1
1560: 35 2c 32 20 31 20 31 2c 34 20 22 2c 20 0d 0a 20 5,2 1 1,4 ", ..
1570: 22 31 20 37 2c 31 20 31 20 31 30 2c 33 20 32 20 "1 7,1 1 10,3 2
1580: 35 2c 31 20 32 20 35 2c 33 20 33 20 31 2c 22 2c 5,1 2 5,3 3 1,",
1590: 20 0d 0a 20 22 33 20 32 20 38 2c 33 20 31 20 32 .. "3 2 8,3 1 2
15a0: 2c 31 20 31 20 33 2c 34 20 34 20 32 2c 32 22 2c ,1 1 3,4 4 2,2",
15b0: 20 0d 0a 20 22 20 34 20 36 2c 34 20 32 20 35 2c .. " 4 6,4 2 5,
15c0: 32 20 33 20 33 2c 36 20 34 20 31 2c 35 20 32 20 2 3 3,6 4 1,5 2
15d0: 38 2c 31 20 33 20 36 2c 31 20 33 20 37 2c 22 2c 8,1 3 6,1 3 7,",
15e0: 20 0d 0a 20 22 34 20 33 20 38 2c 31 20 33 20 38 .. "4 3 8,1 3 8
15f0: 2c 35 20 32 20 33 2c 34 20 32 20 38 2c 32 20 36 ,5 2 3,4 2 8,2 6
1600: 20 37 2c 31 20 33 20 39 2c 22 2c 20 0d 0a 20 22 7,1 3 9,", .. "
1610: 31 20 31 20 34 2c 36 20 31 20 31 2c 32 20 33 20 1 1 4,6 1 1,2 3
1620: 31 2c 35 20 31 20 35 2c 36 20 31 20 38 2c 35 20 1,5 1 5,6 1 8,5
1630: 22 2c 20 0d 0a 20 22 32 20 32 2c 33 20 32 20 31 ", .. "2 2,3 2 1
1640: 30 2c 33 20 33 20 39 2c 31 20 35 20 32 2c 34 20 0,3 3 9,1 5 2,4
1650: 31 20 31 2c 31 20 35 20 31 30 22 7d 3b 0d 0a 09 1 1,1 5 10"};...
1660: 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 vector <string
1670: 3e 20 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e > escDescription
1680: 28 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e 5f (escDescription_
1690: 2c 20 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e , escDescription
16a0: 5f 2b 73 69 7a 65 6f 66 28 65 73 63 44 65 73 63 _+sizeof(escDesc
16b0: 72 69 70 74 69 6f 6e 5f 29 2f 73 69 7a 65 6f 66 ription_)/sizeof
16c0: 28 2a 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e (*escDescription
16d0: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 _)); ...int _ =
16e0: 32 35 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 25; ..END..CASE(
16f0: 33 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 31 33 3b 3)...int N = 13;
1700: 20 0d 0a 09 73 74 72 69 6e 67 20 65 73 63 44 65 ...string escDe
1710: 73 63 72 69 70 74 69 6f 6e 5f 5b 5d 20 3d 20 7b scription_[] = {
1720: 22 35 20 31 20 31 31 2c 32 20 33 20 39 2c 33 20 "5 1 11,2 3 9,3
1730: 37 20 31 30 2c 35 20 32 20 31 31 2c 35 20 35 20 7 10,5 2 11,5 5
1740: 38 2c 37 20 35 20 36 2c 35 20 32 20 31 33 2c 34 8,7 5 6,5 2 13,4
1750: 20 32 20 22 2c 20 22 38 2c 33 20 37 20 31 32 2c 2 ", "8,3 7 12,
1760: 37 20 33 20 39 2c 32 20 37 20 31 32 2c 38 20 35 7 3 9,2 7 12,8 5
1770: 20 34 2c 34 20 36 20 36 2c 37 20 33 20 31 31 2c 4,4 6 6,7 3 11,
1780: 31 20 35 20 37 2c 34 20 34 22 2c 20 22 20 31 30 1 5 7,4 4", " 10
1790: 2c 33 20 31 20 39 2c 37 20 32 20 35 2c 34 20 36 ,3 1 9,7 2 5,4 6
17a0: 20 31 32 2c 35 20 35 20 35 2c 36 20 36 20 35 2c 12,5 5 5,6 6 5,
17b0: 31 20 35 20 31 32 2c 36 20 34 20 33 2c 32 20 22 1 5 12,6 4 3,2 "
17c0: 2c 20 22 35 20 31 2c 32 20 35 20 35 2c 35 20 34 , "5 1,2 5 5,5 4
17d0: 20 33 2c 35 20 36 20 38 2c 33 20 35 20 31 31 2c 3,5 6 8,3 5 11,
17e0: 36 20 32 20 37 2c 38 20 33 20 37 2c 36 20 38 20 6 2 7,8 3 7,6 8
17f0: 32 2c 35 20 33 22 2c 20 22 20 31 32 2c 36 20 31 2,5 3", " 12,6 1
1800: 20 33 2c 36 20 32 20 38 2c 36 20 32 20 36 2c 35 3,6 2 8,6 2 6,5
1810: 20 35 20 36 2c 33 20 32 20 32 2c 34 20 33 20 31 5 6,3 2 2,4 3 1
1820: 31 2c 31 20 38 20 32 2c 33 20 34 22 2c 20 22 20 1,1 8 2,3 4", "
1830: 35 2c 31 20 36 20 38 2c 35 20 37 20 36 2c 33 20 5,1 6 8,5 7 6,3
1840: 32 20 37 2c 34 20 31 20 39 2c 34 20 37 20 38 2c 2 7,4 1 9,4 7 8,
1850: 34 20 33 20 37 2c 34 20 35 20 34 2c 32 20 31 20 4 3 7,4 5 4,2 1
1860: 37 22 2c 20 22 2c 35 20 34 20 32 2c 36 20 35 20 7", ",5 4 2,6 5
1870: 34 2c 36 20 38 20 31 33 2c 32 20 36 20 33 2c 36 4,6 8 13,2 6 3,6
1880: 20 33 20 36 2c 33 20 34 20 37 2c 34 20 35 20 38 3 6,3 4 7,4 5 8
1890: 2c 31 20 33 20 31 31 22 2c 20 22 2c 36 20 36 20 ,1 3 11", ",6 6
18a0: 31 2c 35 20 31 20 38 2c 33 20 35 20 37 2c 37 20 1,5 1 8,3 5 7,7
18b0: 33 20 34 2c 33 20 34 20 31 33 2c 35 20 34 20 36 3 4,3 4 13,5 4 6
18c0: 2c 37 20 34 20 31 2c 33 20 31 20 31 33 22 2c 20 ,7 4 1,3 1 13",
18d0: 22 2c 31 20 35 20 36 2c 37 20 37 20 31 32 2c 34 ",1 5 6,7 7 12,4
18e0: 20 37 20 33 2c 37 20 34 20 34 2c 31 20 36 20 31 7 3,7 4 4,1 6 1
18f0: 30 2c 33 20 34 20 36 2c 37 20 34 20 31 30 2c 35 0,3 4 6,7 4 10,5
1900: 20 33 20 22 2c 20 22 31 33 2c 31 20 31 20 34 2c 3 ", "13,1 1 4,
1910: 38 20 37 20 37 2c 32 20 37 20 31 33 2c 35 20 36 8 7 7,2 7 13,5 6
1920: 20 31 31 2c 31 20 34 20 39 2c 34 20 34 20 31 33 11,1 4 9,4 4 13
1930: 2c 32 20 36 20 38 2c 37 20 22 2c 20 22 35 20 31 ,2 6 8,7 ", "5 1
1940: 30 2c 31 20 32 20 37 2c 31 20 37 20 38 2c 38 20 0,1 2 7,1 7 8,8
1950: 38 20 33 2c 32 20 34 20 31 2c 37 20 36 20 31 32 8 3,2 4 1,7 6 12
1960: 2c 32 20 35 20 31 32 2c 32 20 32 20 33 2c 31 22 ,2 5 12,2 2 3,1"
1970: 2c 20 22 20 32 20 32 2c 31 20 34 20 37 2c 34 20 , " 2 2,1 4 7,4
1980: 31 20 31 31 2c 36 20 32 20 34 2c 34 20 36 20 34 1 11,6 2 4,4 6 4
1990: 2c 36 20 33 20 38 2c 35 20 36 20 37 2c 34 20 32 ,6 3 8,5 6 7,4 2
19a0: 20 34 2c 32 20 22 2c 20 22 37 20 36 2c 37 20 32 4,2 ", "7 6,7 2
19b0: 20 31 2c 33 20 34 20 34 2c 34 20 34 20 33 2c 31 1,3 4 4,4 4 3,1
19c0: 20 32 20 33 2c 31 20 31 20 31 30 2c 32 20 33 20 2 3,1 1 10,2 3
19d0: 38 2c 36 20 36 20 31 31 2c 35 20 22 2c 20 22 35 8,6 6 11,5 ", "5
19e0: 20 31 33 2c 37 20 37 20 34 2c 35 20 33 20 31 31 13,7 7 4,5 3 11
19f0: 2c 36 20 36 20 38 2c 36 20 34 20 31 32 2c 36 20 ,6 6 8,6 4 12,6
1a00: 31 20 37 2c 33 20 38 20 39 2c 32 20 31 20 31 2c 1 7,3 8 9,2 1 1,
1a10: 35 22 2c 20 22 20 35 20 31 30 2c 38 20 31 20 37 5", " 5 10,8 1 7
1a20: 2c 37 20 32 20 36 2c 31 20 37 20 34 2c 35 20 31 ,7 2 6,1 7 4,5 1
1a30: 20 31 32 2c 32 20 35 20 37 2c 36 20 37 20 37 2c 12,2 5 7,6 7 7,
1a40: 33 20 36 20 33 2c 38 22 2c 20 22 20 31 20 31 2c 3 6 3,8", " 1 1,
1a50: 33 20 38 20 32 2c 33 20 36 20 36 2c 33 20 36 20 3 8 2,3 6 6,3 6
1a60: 34 2c 36 20 33 20 32 2c 34 20 35 20 35 2c 32 20 4,6 3 2,4 5 5,2
1a70: 36 20 34 2c 33 20 32 20 36 2c 37 20 36 22 2c 20 6 4,3 2 6,7 6",
1a80: 22 20 35 2c 31 20 38 20 36 2c 35 20 35 20 34 2c " 5,1 8 6,5 5 4,
1a90: 32 20 37 20 31 30 22 2c 20 22 2c 31 20 37 20 39 2 7 10", ",1 7 9
1aa0: 2c 31 20 31 20 33 2c 34 20 34 20 34 2c 34 20 33 ,1 1 3,4 4 4,4 3
1ab0: 20 35 2c 34 20 32 20 31 30 2c 35 20 37 20 33 2c 5,4 2 10,5 7 3,
1ac0: 35 20 33 20 35 2c 33 20 36 20 39 2c 22 2c 20 22 5 3 5,3 6 9,", "
1ad0: 32 20 35 20 31 31 2c 33 20 32 20 33 2c 34 20 31 2 5 11,3 2 3,4 1
1ae0: 20 31 2c 32 20 35 20 31 30 2c 35 20 31 20 34 2c 1,2 5 10,5 1 4,
1af0: 36 20 35 20 35 2c 31 20 37 20 35 2c 37 20 35 20 6 5 5,1 7 5,7 5
1b00: 35 2c 22 2c 20 22 38 20 35 20 31 32 2c 37 20 38 5,", "8 5 12,7 8
1b10: 20 31 33 2c 31 20 32 20 31 30 2c 33 20 37 20 36 13,1 2 10,3 7 6
1b20: 2c 34 20 37 20 31 33 2c 34 20 33 20 31 33 2c 36 ,4 7 13,4 3 13,6
1b30: 20 34 20 31 31 2c 36 20 22 2c 20 22 37 20 34 2c 4 11,6 ", "7 4,
1b40: 32 20 36 20 37 2c 32 20 37 20 33 2c 37 20 38 20 2 6 7,2 7 3,7 8
1b50: 38 2c 36 20 31 20 31 32 2c 36 20 37 20 38 2c 33 8,6 1 12,6 7 8,3
1b60: 20 31 20 31 30 2c 38 20 36 20 31 2c 31 20 22 2c 1 10,8 6 1,1 ",
1b70: 20 22 37 20 31 30 2c 31 20 33 20 39 2c 37 20 37 "7 10,1 3 9,7 7
1b80: 20 31 31 2c 35 20 36 20 34 2c 37 20 37 20 31 2c 11,5 6 4,7 7 1,
1b90: 34 20 32 20 31 2c 38 20 32 20 33 2c 37 20 38 20 4 2 1,8 2 3,7 8
1ba0: 32 2c 31 20 22 2c 20 22 34 20 31 33 2c 32 20 33 2,1 ", "4 13,2 3
1bb0: 20 31 33 2c 33 20 32 20 31 31 2c 36 20 37 20 31 13,3 2 11,6 7 1
1bc0: 32 2c 34 20 38 20 32 2c 35 20 36 20 31 2c 36 20 2,4 8 2,5 6 1,6
1bd0: 33 20 31 32 2c 33 20 35 20 33 22 2c 20 22 2c 31 3 12,3 5 3", ",1
1be0: 20 35 20 31 30 2c 31 20 34 20 35 2c 34 20 36 20 5 10,1 4 5,4 6
1bf0: 31 30 2c 31 20 36 20 36 2c 36 20 33 20 35 2c 34 10,1 6 6,6 3 5,4
1c00: 20 33 20 31 32 2c 36 20 32 20 31 31 2c 33 20 38 3 12,6 2 11,3 8
1c10: 22 2c 20 22 20 33 2c 37 20 35 20 33 2c 36 20 37 ", " 3,7 5 3,6 7
1c20: 20 31 30 2c 33 20 32 20 31 33 2c 37 20 34 20 33 10,3 2 13,7 4 3
1c30: 2c 31 20 37 20 31 32 2c 32 20 37 20 34 2c 34 20 ,1 7 12,2 7 4,4
1c40: 37 20 31 2c 38 20 22 2c 20 22 35 20 31 30 2c 36 7 1,8 ", "5 10,6
1c50: 20 36 20 34 2c 36 20 37 20 32 2c 34 20 37 20 37 6 4,6 7 2,4 7 7
1c60: 2c 31 20 33 20 31 2c 31 20 34 20 31 32 2c 36 20 ,1 3 1,1 4 12,6
1c70: 35 20 37 2c 35 20 31 20 31 33 2c 35 22 2c 20 22 5 7,5 1 13,5", "
1c80: 20 38 20 31 33 2c 32 20 31 20 31 30 2c 35 20 32 8 13,2 1 10,5 2
1c90: 20 37 2c 38 20 33 20 31 30 2c 35 20 31 20 35 2c 7,8 3 10,5 1 5,
1ca0: 31 20 34 20 36 2c 31 20 31 20 36 2c 35 20 32 20 1 4 6,1 1 6,5 2
1cb0: 32 2c 22 2c 20 22 32 20 33 20 31 31 2c 33 20 32 2,", "2 3 11,3 2
1cc0: 20 31 30 2c 32 20 31 20 31 33 2c 38 20 32 20 39 10,2 1 13,8 2 9
1cd0: 2c 33 20 35 20 32 2c 31 20 37 20 32 2c 33 20 33 ,3 5 2,1 7 2,3 3
1ce0: 20 35 2c 35 20 32 20 35 22 2c 20 22 2c 38 20 34 5,5 2 5", ",8 4
1cf0: 20 31 32 2c 37 20 33 20 32 2c 32 20 35 20 33 2c 12,7 3 2,2 5 3,
1d00: 33 20 37 20 31 2c 36 20 37 20 36 2c 38 20 35 20 3 7 1,6 7 6,8 5
1d10: 39 2c 34 20 35 20 37 2c 32 20 38 20 33 2c 22 2c 9,4 5 7,2 8 3,",
1d20: 20 22 32 20 34 20 36 2c 37 20 31 20 31 30 2c 35 "2 4 6,7 1 10,5
1d30: 20 38 20 31 31 2c 34 20 37 20 36 2c 37 20 36 20 8 11,4 7 6,7 6
1d40: 34 2c 33 20 36 20 31 31 2c 35 20 33 20 31 2c 37 4,3 6 11,5 3 1,7
1d50: 20 37 20 38 22 2c 20 22 2c 31 20 36 20 39 2c 37 7 8", ",1 6 9,7
1d60: 20 36 20 37 2c 31 20 32 20 31 2c 32 20 32 20 31 6 7,1 2 1,2 2 1
1d70: 32 2c 33 20 35 20 39 2c 34 20 34 20 31 2c 36 20 2,3 5 9,4 4 1,6
1d80: 34 20 35 2c 35 20 38 20 33 2c 22 2c 20 22 32 20 4 5,5 8 3,", "2
1d90: 31 20 32 2c 36 20 36 20 31 30 2c 31 20 35 20 39 1 2,6 6 10,1 5 9
1da0: 2c 38 20 31 20 33 2c 35 20 31 20 31 30 2c 34 20 ,8 1 3,5 1 10,4
1db0: 37 20 32 2c 38 20 34 20 39 2c 32 20 32 20 37 2c 7 2,8 4 9,2 2 7,
1dc0: 22 2c 20 22 32 20 33 20 34 2c 36 20 31 20 34 2c ", "2 3 4,6 1 4,
1dd0: 31 20 34 20 31 31 2c 37 20 31 20 31 2c 33 20 37 1 4 11,7 1 1,3 7
1de0: 20 37 2c 35 20 34 20 31 33 2c 31 20 36 20 31 2c 7,5 4 13,1 6 1,
1df0: 34 20 37 20 31 32 22 7d 3b 0d 0a 09 20 20 76 65 4 7 12"};... ve
1e00: 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 65 73 ctor <string> es
1e10: 63 44 65 73 63 72 69 70 74 69 6f 6e 28 65 73 63 cDescription(esc
1e20: 44 65 73 63 72 69 70 74 69 6f 6e 5f 2c 20 65 73 Description_, es
1e30: 63 44 65 73 63 72 69 70 74 69 6f 6e 5f 2b 73 69 cDescription_+si
1e40: 7a 65 6f 66 28 65 73 63 44 65 73 63 72 69 70 74 zeof(escDescript
1e50: 69 6f 6e 5f 29 2f 73 69 7a 65 6f 66 28 2a 65 73 ion_)/sizeof(*es
1e60: 63 44 65 73 63 72 69 70 74 69 6f 6e 5f 29 29 3b cDescription_));
1e70: 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 35 30 3b 20 ...int _ = 50;
1e80: 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 ..END../*..CASE(
1e90: 34 29 0d 0a 09 69 6e 74 20 4e 20 3d 20 3b 20 0d 4)...int N = ; .
1ea0: 0a 09 73 74 72 69 6e 67 20 65 73 63 44 65 73 63 ..string escDesc
1eb0: 72 69 70 74 69 6f 6e 5f 5b 5d 20 3d 20 3b 0d 0a ription_[] = ;..
1ec0: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
1ed0: 67 3e 20 65 73 63 44 65 73 63 72 69 70 74 69 6f g> escDescriptio
1ee0: 6e 28 65 73 63 44 65 73 63 72 69 70 74 69 6f 6e n(escDescription
1ef0: 5f 2c 20 65 73 63 44 65 73 63 72 69 70 74 69 6f _, escDescriptio
1f00: 6e 5f 2b 73 69 7a 65 6f 66 28 65 73 63 44 65 73 n_+sizeof(escDes
1f10: 63 72 69 70 74 69 6f 6e 5f 29 2f 73 69 7a 65 6f cription_)/sizeo
1f20: 66 28 2a 65 73 63 44 65 73 63 72 69 70 74 69 6f f(*escDescriptio
1f30: 6e 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d n_)); ...int _ =
1f40: 20 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d ; ..END..*/..}.
1f50: 0a 2f 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 .// END CUT HERE
1f60: 0d 0a ..