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 73 74 61 74 69 63 20 63 CMP;....static c
01a0: 6f 6e 73 74 20 69 6e 74 20 4e 56 20 3d 20 32 35 onst int NV = 25
01b0: 36 3b 0d 0a 74 79 70 65 64 65 66 20 69 6e 74 20 6;..typedef int
01c0: 20 20 20 20 20 20 20 20 20 20 66 6c 6f 77 3b 0d flow;.
01d0: 0a 74 79 70 65 64 65 66 20 69 6e 74 20 20 20 20 .typedef int
01e0: 20 20 20 20 20 20 20 63 6f 73 74 3b 0d 0a 74 79 cost;..ty
01f0: 70 65 64 65 66 20 69 6e 74 20 20 20 20 20 20 20 pedef int
0200: 20 20 20 20 76 65 72 74 3b 0d 0a 74 79 70 65 64 vert;..typed
0210: 65 66 20 76 65 72 74 20 20 20 20 20 20 20 20 20 ef vert
0220: 20 65 64 67 65 3b 0d 0a 74 79 70 65 64 65 66 20 edge;..typedef
0230: 76 65 63 74 6f 72 3c 65 64 67 65 3e 20 20 65 64 vector<edge> ed
0240: 67 65 73 3b 0d 0a 74 79 70 65 64 65 66 20 76 65 ges;..typedef ve
0250: 63 74 6f 72 3c 65 64 67 65 73 3e 20 67 72 61 70 ctor<edges> grap
0260: 68 3b 0d 0a 74 79 70 65 64 65 66 20 66 6c 6f 77 h;..typedef flow
0270: 20 20 20 20 20 20 20 20 20 20 66 6c 6f 77 5f 67 flow_g
0280: 72 61 70 68 5b 4e 56 5d 5b 4e 56 5d 3b 0d 0a 74 raph[NV][NV];..t
0290: 79 70 65 64 65 66 20 63 6f 73 74 20 20 20 20 20 ypedef cost
02a0: 20 20 20 20 20 63 6f 73 74 5f 67 72 61 70 68 5b cost_graph[
02b0: 4e 56 5d 5b 4e 56 5d 3b 0d 0a 73 74 61 74 69 63 NV][NV];..static
02c0: 20 63 6f 6e 73 74 20 66 6c 6f 77 20 46 4c 4f 57 const flow FLOW
02d0: 5f 49 4e 46 20 3d 20 30 78 37 46 46 46 46 46 46 _INF = 0x7FFFFFF
02e0: 46 3b 0d 0a 73 74 61 74 69 63 20 63 6f 6e 73 74 F;..static const
02f0: 20 63 6f 73 74 20 43 4f 53 54 5f 49 4e 46 20 3d cost COST_INF =
0300: 20 30 78 37 46 46 46 46 46 46 46 3b 0d 0a 0d 0a 0x7FFFFFFF;....
0310: 2f 2f 20 65 64 67 65 73 28 62 69 64 69 29 2c 20 // edges(bidi),
0320: 63 61 70 61 63 69 74 79 2c 20 63 6f 73 74 28 73 capacity, cost(s
0330: 2e 74 2e 20 43 5b 78 5d 5b 79 5d 3d 2d 43 5b 79 .t. C[x][y]=-C[y
0340: 5d 5b 78 5d 29 20 70 65 72 20 31 20 66 6c 6f 77 ][x]) per 1 flow
0350: 2c 20 73 72 63 2c 20 64 73 74 0d 0a 70 61 69 72 , src, dst..pair
0360: 3c 63 6f 73 74 2c 66 6c 6f 77 3e 20 6d 69 6e 63 <cost,flow> minc
0370: 6f 73 74 46 6c 6f 77 28 67 72 61 70 68 26 20 47 ostFlow(graph& G
0380: 2c 20 66 6c 6f 77 5f 67 72 61 70 68 20 46 2c 20 , flow_graph F,
0390: 63 6f 73 74 5f 67 72 61 70 68 20 43 2c 20 76 65 cost_graph C, ve
03a0: 72 74 20 53 2c 20 76 65 72 74 20 44 29 0d 0a 7b rt S, vert D)..{
03b0: 0d 0a 09 69 6e 74 20 4e 20 3d 20 47 2e 73 69 7a ...int N = G.siz
03c0: 65 28 29 3b 0d 0a 09 63 6f 73 74 20 74 6f 74 61 e();...cost tota
03d0: 6c 5f 63 6f 73 74 20 3d 20 30 3b 0d 0a 09 66 6c l_cost = 0;...fl
03e0: 6f 77 20 74 6f 74 61 6c 5f 66 6c 6f 77 20 3d 20 ow total_flow =
03f0: 30 3b 0d 0a 0d 0a 09 76 65 63 74 6f 72 3c 63 6f 0;.....vector<co
0400: 73 74 3e 20 68 28 4e 2c 20 30 29 3b 20 2f 2f 20 st> h(N, 0); //
0410: 70 6f 74 65 6e 74 69 61 6c 0d 0a 09 66 6f 72 28 potential...for(
0420: 63 6f 73 74 20 52 46 3d 46 4c 4f 57 5f 49 4e 46 cost RF=FLOW_INF
0430: 3b 20 52 46 3e 30 3b 20 29 20 2f 2f 20 72 65 73 ; RF>0; ) // res
0440: 69 64 75 61 6c 20 66 6c 6f 77 0d 0a 09 7b 0d 0a idual flow...{..
0450: 09 09 2f 2f 20 44 69 6a 6b 73 74 72 61 20 2d 2d ..// Dijkstra --
0460: 20 66 69 6e 64 20 74 68 65 20 6d 69 6e 2d 63 6f find the min-co
0470: 73 74 20 70 61 74 68 0d 0a 09 09 76 65 63 74 6f st path....vecto
0480: 72 3c 63 6f 73 74 3e 20 64 28 4e 2c 20 43 4f 53 r<cost> d(N, COS
0490: 54 5f 49 4e 46 29 3b 20 20 64 5b 53 5d 20 3d 20 T_INF); d[S] =
04a0: 30 3b 0d 0a 09 09 76 65 63 74 6f 72 3c 76 65 72 0;....vector<ver
04b0: 74 3e 20 70 72 65 76 28 4e 2c 20 2d 31 29 3b 0d t> prev(N, -1);.
04c0: 0a 0d 0a 09 09 74 79 70 65 64 65 66 20 70 61 69 .....typedef pai
04d0: 72 3c 63 6f 73 74 2c 20 70 61 69 72 3c 76 65 72 r<cost, pair<ver
04e0: 74 2c 76 65 72 74 3e 20 3e 20 63 65 64 67 65 3b t,vert> > cedge;
04f0: 0d 0a 09 09 70 72 69 6f 72 69 74 79 5f 71 75 65 ....priority_que
0500: 75 65 3c 20 63 65 64 67 65 2c 20 76 65 63 74 6f ue< cedge, vecto
0510: 72 3c 63 65 64 67 65 3e 2c 20 67 72 65 61 74 65 r<cedge>, greate
0520: 72 3c 63 65 64 67 65 3e 20 3e 20 51 3b 0d 0a 09 r<cedge> > Q;...
0530: 09 51 2e 70 75 73 68 28 20 63 65 64 67 65 28 30 .Q.push( cedge(0
0540: 2c 20 6d 61 6b 65 5f 70 61 69 72 28 53 2c 53 29 , make_pair(S,S)
0550: 29 20 29 3b 0d 0a 09 09 77 68 69 6c 65 28 20 21 ) );....while( !
0560: 51 2e 65 6d 70 74 79 28 29 20 29 20 7b 0d 0a 09 Q.empty() ) {...
0570: 09 09 63 65 64 67 65 20 65 20 3d 20 51 2e 74 6f ..cedge e = Q.to
0580: 70 28 29 3b 20 51 2e 70 6f 70 28 29 3b 0d 0a 09 p(); Q.pop();...
0590: 09 09 69 66 28 20 70 72 65 76 5b 65 2e 73 65 63 ..if( prev[e.sec
05a0: 6f 6e 64 2e 73 65 63 6f 6e 64 5d 20 3e 3d 20 30 ond.second] >= 0
05b0: 20 29 0d 0a 09 09 09 09 63 6f 6e 74 69 6e 75 65 )......continue
05c0: 3b 0d 0a 09 09 09 70 72 65 76 5b 65 2e 73 65 63 ;.....prev[e.sec
05d0: 6f 6e 64 2e 73 65 63 6f 6e 64 5d 20 3d 20 65 2e ond.second] = e.
05e0: 73 65 63 6f 6e 64 2e 66 69 72 73 74 3b 0d 0a 0d second.first;...
05f0: 0a 09 09 09 76 65 72 74 20 75 20 3d 20 65 2e 73 ....vert u = e.s
0600: 65 63 6f 6e 64 2e 73 65 63 6f 6e 64 3b 0d 0a 09 econd.second;...
0610: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0620: 3c 47 5b 75 5d 2e 73 69 7a 65 28 29 3b 20 2b 2b <G[u].size(); ++
0630: 69 29 20 7b 0d 0a 09 09 09 09 76 65 72 74 20 76 i) {......vert v
0640: 20 3d 20 47 5b 75 5d 5b 69 5d 3b 0d 0a 09 09 09 = G[u][i];.....
0650: 09 63 6f 73 74 20 72 5f 63 6f 73 74 20 3d 20 43 .cost r_cost = C
0660: 5b 75 5d 5b 76 5d 20 2b 20 68 5b 75 5d 20 2d 20 [u][v] + h[u] -
0670: 68 5b 76 5d 3b 0d 0a 09 09 09 09 69 66 28 20 46 h[v];......if( F
0680: 5b 75 5d 5b 76 5d 20 3e 20 30 20 26 26 20 64 5b [u][v] > 0 && d[
0690: 76 5d 20 3e 20 64 5b 75 5d 2b 72 5f 63 6f 73 74 v] > d[u]+r_cost
06a0: 20 29 0d 0a 09 09 09 09 09 51 2e 70 75 73 68 28 ).......Q.push(
06b0: 20 63 65 64 67 65 28 64 5b 76 5d 3d 64 5b 75 5d cedge(d[v]=d[u]
06c0: 2b 72 5f 63 6f 73 74 2c 20 6d 61 6b 65 5f 70 61 +r_cost, make_pa
06d0: 69 72 28 75 2c 76 29 29 20 29 3b 0d 0a 09 09 09 ir(u,v)) );.....
06e0: 7d 0d 0a 09 09 7d 0d 0a 0d 0a 09 09 69 66 28 20 }....}......if(
06f0: 70 72 65 76 5b 44 5d 20 3c 20 30 20 29 0d 0a 09 prev[D] < 0 )...
0700: 09 09 62 72 65 61 6b 3b 20 2f 2f 20 46 69 6e 69 ..break; // Fini
0710: 73 68 65 64 0d 0a 0d 0a 09 09 2f 2f 20 41 73 20 shed......// As
0720: 6d 75 63 68 20 61 73 20 70 6f 73 73 69 62 6c 65 much as possible
0730: 0d 0a 09 09 66 6c 6f 77 20 66 20 3d 20 52 46 3b ....flow f = RF;
0740: 0d 0a 09 09 66 6f 72 28 76 65 72 74 20 75 3d 44 ....for(vert u=D
0750: 3b 20 75 21 3d 53 3b 20 75 3d 70 72 65 76 5b 75 ; u!=S; u=prev[u
0760: 5d 29 0d 0a 09 09 09 66 20 3d 20 6d 69 6e 28 66 ]).....f = min(f
0770: 2c 20 46 5b 70 72 65 76 5b 75 5d 5d 5b 75 5d 29 , F[prev[u]][u])
0780: 3b 0d 0a 09 09 52 46 20 20 20 20 20 20 20 20 20 ;....RF
0790: 2d 3d 20 66 3b 0d 0a 09 09 74 6f 74 61 6c 5f 66 -= f;....total_f
07a0: 6c 6f 77 20 2b 3d 20 66 3b 0d 0a 0d 0a 09 09 66 low += f;......f
07b0: 6f 72 28 76 65 72 74 20 75 3d 44 3b 20 75 21 3d or(vert u=D; u!=
07c0: 53 3b 20 75 3d 70 72 65 76 5b 75 5d 29 0d 0a 09 S; u=prev[u])...
07d0: 09 7b 0d 0a 09 09 09 74 6f 74 61 6c 5f 63 6f 73 .{.....total_cos
07e0: 74 20 20 20 20 2b 3d 20 66 20 2a 20 43 5b 70 72 t += f * C[pr
07f0: 65 76 5b 75 5d 5d 5b 75 5d 3b 0d 0a 09 09 09 46 ev[u]][u];.....F
0800: 5b 70 72 65 76 5b 75 5d 5d 5b 75 5d 20 2d 3d 20 [prev[u]][u] -=
0810: 66 3b 0d 0a 09 09 09 46 5b 75 5d 5b 70 72 65 76 f;.....F[u][prev
0820: 5b 75 5d 5d 20 2b 3d 20 66 3b 0d 0a 09 09 7d 0d [u]] += f;....}.
0830: 0a 0d 0a 09 09 2f 2f 20 55 70 64 61 74 65 20 74 .....// Update t
0840: 68 65 20 70 6f 74 65 6e 74 69 61 6c 0d 0a 09 09 he potential....
0850: 66 6f 72 28 76 65 72 74 20 75 3d 30 3b 20 75 3c for(vert u=0; u<
0860: 4e 3b 20 2b 2b 75 29 0d 0a 09 09 09 68 5b 75 5d N; ++u).....h[u]
0870: 20 2b 3d 20 64 5b 75 5d 3b 0d 0a 09 7d 0d 0a 09 += d[u];...}...
0880: 72 65 74 75 72 6e 20 6d 61 6b 65 5f 70 61 69 72 return make_pair
0890: 28 74 6f 74 61 6c 5f 63 6f 73 74 2c 20 74 6f 74 (total_cost, tot
08a0: 61 6c 5f 66 6c 6f 77 29 3b 0d 0a 7d 0d 0a 0d 0a al_flow);..}....
08b0: 63 6c 61 73 73 20 4d 61 72 62 6c 65 73 52 65 67 class MarblesReg
08c0: 72 6f 75 70 69 6e 67 48 61 72 64 20 7b 20 70 75 roupingHard { pu
08d0: 62 6c 69 63 3a 0d 0a 09 69 6e 74 20 6d 69 6e 4d blic:...int minM
08e0: 6f 76 65 73 28 76 65 63 74 6f 72 20 3c 73 74 72 oves(vector <str
08f0: 69 6e 67 3e 20 62 6f 78 65 73 29 20 0d 0a 09 7b ing> boxes) ...{
0900: 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 4e 42 ....const int NB
0910: 20 3d 20 62 6f 78 65 73 2e 73 69 7a 65 28 29 3b = boxes.size();
0920: 0d 0a 09 09 76 65 63 74 6f 72 3c 20 76 65 63 74 ....vector< vect
0930: 6f 72 3c 69 6e 74 3e 20 3e 20 62 62 28 4e 42 29 or<int> > bb(NB)
0940: 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 ;....for(int i=0
0950: 3b 20 69 3c 62 6f 78 65 73 2e 73 69 7a 65 28 29 ; i<boxes.size()
0960: 3b 20 2b 2b 69 29 0d 0a 09 09 7b 0d 0a 09 09 09 ; ++i)....{.....
0970: 73 74 72 69 6e 67 73 74 72 65 61 6d 20 73 69 6e stringstream sin
0980: 28 62 6f 78 65 73 5b 69 5d 29 3b 0d 0a 09 09 09 (boxes[i]);.....
0990: 66 6f 72 28 69 6e 74 20 76 3b 20 73 69 6e 3e 3e for(int v; sin>>
09a0: 76 3b 20 29 0d 0a 09 09 09 09 62 62 5b 69 5d 2e v; )......bb[i].
09b0: 70 75 73 68 5f 62 61 63 6b 28 76 29 3b 0d 0a 09 push_back(v);...
09c0: 09 7d 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 20 .}....const int
09d0: 4e 43 20 3d 20 62 62 5b 30 5d 2e 73 69 7a 65 28 NC = bb[0].size(
09e0: 29 3b 0d 0a 0d 0a 09 09 67 72 61 70 68 20 47 28 );......graph G(
09f0: 4e 42 2b 4e 43 2b 33 29 3b 0d 0a 09 09 66 6c 6f NB+NC+3);....flo
0a00: 77 5f 67 72 61 70 68 20 46 20 3d 20 7b 7d 3b 0d w_graph F = {};.
0a10: 0a 09 09 63 6f 73 74 5f 67 72 61 70 68 20 43 20 ...cost_graph C
0a20: 3d 20 7b 7d 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 = {};....for(int
0a30: 20 69 3d 30 3b 20 69 3c 4e 42 3b 20 2b 2b 69 29 i=0; i<NB; ++i)
0a40: 20 7b 0d 0a 09 09 09 47 5b 30 5d 2e 70 75 73 68 {.....G[0].push
0a50: 5f 62 61 63 6b 28 32 2b 69 29 3b 0d 0a 09 09 09 _back(2+i);.....
0a60: 47 5b 32 2b 69 5d 2e 70 75 73 68 5f 62 61 63 6b G[2+i].push_back
0a70: 28 30 29 3b 0d 0a 09 09 09 46 5b 30 5d 5b 32 2b (0);.....F[0][2+
0a80: 69 5d 20 3d 20 31 3b 0d 0a 09 09 7d 0d 0a 09 09 i] = 1;....}....
0a90: 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e for(int i=0; i<N
0aa0: 43 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 47 5b C; ++i) {.....G[
0ab0: 32 2b 4e 42 2b 69 5d 2e 70 75 73 68 5f 62 61 63 2+NB+i].push_bac
0ac0: 6b 28 31 29 3b 0d 0a 09 09 09 47 5b 31 5d 2e 70 k(1);.....G[1].p
0ad0: 75 73 68 5f 62 61 63 6b 28 32 2b 4e 42 2b 69 29 ush_back(2+NB+i)
0ae0: 3b 0d 0a 09 09 09 46 5b 32 2b 4e 42 2b 69 5d 5b ;.....F[2+NB+i][
0af0: 31 5d 20 3d 20 31 3b 0d 0a 09 09 7d 0d 0a 09 09 1] = 1;....}....
0b00: 7b 0d 0a 09 09 09 47 5b 32 2b 4e 42 2b 4e 43 5d {.....G[2+NB+NC]
0b10: 2e 70 75 73 68 5f 62 61 63 6b 28 31 29 3b 0d 0a .push_back(1);..
0b20: 09 09 09 47 5b 31 5d 2e 70 75 73 68 5f 62 61 63 ...G[1].push_bac
0b30: 6b 28 32 2b 4e 42 2b 4e 43 29 3b 0d 0a 09 09 09 k(2+NB+NC);.....
0b40: 46 5b 32 2b 4e 42 2b 4e 43 5d 5b 31 5d 20 3d 20 F[2+NB+NC][1] =
0b50: 4e 42 2d 4e 43 3b 0d 0a 09 09 7d 0d 0a 09 09 66 NB-NC;....}....f
0b60: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 42 or(int i=0; i<NB
0b70: 3b 20 2b 2b 69 29 0d 0a 09 09 66 6f 72 28 69 6e ; ++i)....for(in
0b80: 74 20 6a 3d 30 3b 20 6a 3c 4e 43 3b 20 2b 2b 6a t j=0; j<NC; ++j
0b90: 29 20 7b 0d 0a 09 09 09 47 5b 32 2b 69 5d 2e 70 ) {.....G[2+i].p
0ba0: 75 73 68 5f 62 61 63 6b 28 32 2b 4e 42 2b 6a 29 ush_back(2+NB+j)
0bb0: 3b 0d 0a 09 09 09 47 5b 32 2b 4e 42 2b 6a 5d 2e ;.....G[2+NB+j].
0bc0: 70 75 73 68 5f 62 61 63 6b 28 32 2b 69 29 3b 0d push_back(2+i);.
0bd0: 0a 09 09 09 46 5b 32 2b 69 5d 5b 32 2b 4e 42 2b ....F[2+i][2+NB+
0be0: 6a 5d 20 3d 20 31 3b 0d 0a 09 09 09 69 6e 74 20 j] = 1;.....int
0bf0: 63 20 3d 20 30 3b 0d 0a 09 09 09 66 6f 72 28 69 c = 0;.....for(i
0c00: 6e 74 20 6b 3d 30 3b 20 6b 3c 4e 42 3b 20 2b 2b nt k=0; k<NB; ++
0c10: 6b 29 20 69 66 28 6b 21 3d 69 29 0d 0a 09 09 09 k) if(k!=i).....
0c20: 09 63 20 2b 3d 20 62 62 5b 6b 5d 5b 6a 5d 3b 0d .c += bb[k][j];.
0c30: 0a 09 09 09 43 5b 32 2b 69 5d 5b 32 2b 4e 42 2b ....C[2+i][2+NB+
0c40: 6a 5d 20 3d 20 63 3b 0d 0a 09 09 09 43 5b 32 2b j] = c;.....C[2+
0c50: 4e 42 2b 6a 5d 5b 32 2b 69 5d 20 3d 20 2d 63 3b NB+j][2+i] = -c;
0c60: 0d 0a 09 09 7d 0d 0a 09 09 66 6f 72 28 69 6e 74 ....}....for(int
0c70: 20 69 3d 30 3b 20 69 3c 4e 42 3b 20 2b 2b 69 29 i=0; i<NB; ++i)
0c80: 20 7b 0d 0a 09 09 09 47 5b 32 2b 69 5d 2e 70 75 {.....G[2+i].pu
0c90: 73 68 5f 62 61 63 6b 28 32 2b 4e 42 2b 4e 43 29 sh_back(2+NB+NC)
0ca0: 3b 0d 0a 09 09 09 47 5b 32 2b 4e 42 2b 4e 43 5d ;.....G[2+NB+NC]
0cb0: 2e 70 75 73 68 5f 62 61 63 6b 28 32 2b 69 29 3b .push_back(2+i);
0cc0: 0d 0a 09 09 09 46 5b 32 2b 69 5d 5b 32 2b 4e 42 .....F[2+i][2+NB
0cd0: 2b 4e 43 5d 20 3d 20 31 3b 0d 0a 09 09 7d 0d 0a +NC] = 1;....}..
0ce0: 09 09 70 61 69 72 3c 63 6f 73 74 2c 66 6c 6f 77 ..pair<cost,flow
0cf0: 3e 20 66 66 20 3d 20 6d 69 6e 63 6f 73 74 46 6c > ff = mincostFl
0d00: 6f 77 28 47 2c 20 46 2c 20 43 2c 20 30 2c 20 31 ow(G, F, C, 0, 1
0d10: 29 3b 0d 0a 09 09 72 65 74 75 72 6e 20 66 66 2e );....return ff.
0d20: 66 69 72 73 74 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a first;...}..};..
0d30: 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 55 54 20 48 ..// BEGIN CUT H
0d40: 45 52 45 0d 0a 23 69 6e 63 6c 75 64 65 20 3c 63 ERE..#include <c
0d50: 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 time>..double st
0d60: 61 72 74 5f 74 69 6d 65 3b 20 73 74 72 69 6e 67 art_time; string
0d70: 20 74 69 6d 65 72 28 29 0d 0a 20 7b 20 6f 73 74 timer().. { ost
0d80: 72 69 6e 67 73 74 72 65 61 6d 20 6f 73 3b 20 6f ringstream os; o
0d90: 73 20 3c 3c 20 22 20 28 22 20 3c 3c 20 69 6e 74 s << " (" << int
0da0: 28 28 63 6c 6f 63 6b 28 29 2d 73 74 61 72 74 5f ((clock()-start_
0db0: 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 time)/CLOCKS_PER
0dc0: 5f 53 45 43 2a 31 30 30 30 29 20 3c 3c 20 22 20 _SEC*1000) << "
0dd0: 6d 73 65 63 29 22 3b 20 72 65 74 75 72 6e 20 6f msec)"; return o
0de0: 73 2e 73 74 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 s.str(); }..temp
0df0: 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 54 3e late<typename T>
0e00: 20 6f 73 74 72 65 61 6d 26 20 6f 70 65 72 61 74 ostream& operat
0e10: 6f 72 3c 3c 28 6f 73 74 72 65 61 6d 26 20 6f 73 or<<(ostream& os
0e20: 2c 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 54 , const vector<T
0e30: 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 >& v).. { os <<
0e40: 22 7b 20 22 3b 0d 0a 20 20 20 66 6f 72 28 74 79 "{ ";.. for(ty
0e50: 70 65 6e 61 6d 65 20 76 65 63 74 6f 72 3c 54 3e pename vector<T>
0e60: 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 61 74 6f 72 ::const_iterator
0e70: 20 69 74 3d 76 2e 62 65 67 69 6e 28 29 3b 20 69 it=v.begin(); i
0e80: 74 21 3d 76 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 t!=v.end(); ++it
0e90: 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 27 5c 22 27 ).. os << '\"'
0ea0: 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 5c 22 27 20 << *it << '\"'
0eb0: 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 << (it+1==v.end(
0ec0: 29 20 3f 20 22 22 20 3a 20 22 2c 20 22 29 3b 20 ) ? "" : ", ");
0ed0: 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 72 65 74 75 os << " }"; retu
0ee0: 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 rn os; }..void v
0ef0: 65 72 69 66 79 5f 63 61 73 65 28 63 6f 6e 73 74 erify_case(const
0f00: 20 69 6e 74 26 20 45 78 70 65 63 74 65 64 2c 20 int& Expected,
0f10: 63 6f 6e 73 74 20 69 6e 74 26 20 52 65 63 65 69 const int& Recei
0f20: 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b ved) {.. bool ok
0f30: 20 3d 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 = (Expected ==
0f40: 52 65 63 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 Received);.. if(
0f50: 6f 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 ok) cerr << "PAS
0f60: 53 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 SED" << timer()
0f70: 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b << endl; else {
0f80: 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 cerr << "FAILED
0f90: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
0fa0: 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 endl;.. cerr <<
0fb0: 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 "\to: \"" << Exp
0fc0: 65 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c ected << '\"' <<
0fd0: 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c endl << "\tx: \
0fe0: 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c "" << Received <
0ff0: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 < '\"' << endl;
1000: 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 } }..#define CAS
1010: 45 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 E(N) {cerr << "T
1020: 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e est Case #" << N
1030: 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 << "..." << flu
1040: 73 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 sh; start_time=c
1050: 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 lock();..#define
1060: 20 45 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 END. verify_cas
1070: 65 28 5f 2c 20 4d 61 72 62 6c 65 73 52 65 67 72 e(_, MarblesRegr
1080: 6f 75 70 69 6e 67 48 61 72 64 28 29 2e 6d 69 6e oupingHard().min
1090: 4d 6f 76 65 73 28 62 6f 78 65 73 29 29 3b 7d 0d Moves(boxes));}.
10a0: 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a 0d 0a .int main(){....
10b0: 43 41 53 45 28 30 29 0d 0a 09 73 74 72 69 6e 67 CASE(0)...string
10c0: 20 62 6f 78 65 73 5f 5b 5d 20 3d 20 7b 22 30 22 boxes_[] = {"0"
10d0: 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 };... vector <s
10e0: 74 72 69 6e 67 3e 20 62 6f 78 65 73 28 62 6f 78 tring> boxes(box
10f0: 65 73 5f 2c 20 62 6f 78 65 73 5f 2b 73 69 7a 65 es_, boxes_+size
1100: 6f 66 28 62 6f 78 65 73 5f 29 2f 73 69 7a 65 6f of(boxes_)/sizeo
1110: 66 28 2a 62 6f 78 65 73 5f 29 29 3b 20 0d 0a 09 f(*boxes_)); ...
1120: 69 6e 74 20 5f 20 3d 20 30 3b 20 0d 0a 45 4e 44 int _ = 0; ..END
1130: 0d 0a 43 41 53 45 28 31 29 0d 0a 09 73 74 72 69 ..CASE(1)...stri
1140: 6e 67 20 62 6f 78 65 73 5f 5b 5d 20 3d 20 7b 22 ng boxes_[] = {"
1150: 37 37 20 39 37 22 2c 22 38 20 30 22 7d 3b 0d 0a 77 97","8 0"};..
1160: 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e . vector <strin
1170: 67 3e 20 62 6f 78 65 73 28 62 6f 78 65 73 5f 2c g> boxes(boxes_,
1180: 20 62 6f 78 65 73 5f 2b 73 69 7a 65 6f 66 28 62 boxes_+sizeof(b
1190: 6f 78 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 oxes_)/sizeof(*b
11a0: 6f 78 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 oxes_)); ...int
11b0: 5f 20 3d 20 37 37 3b 20 0d 0a 45 4e 44 0d 0a 43 _ = 77; ..END..C
11c0: 41 53 45 28 32 29 0d 0a 09 73 74 72 69 6e 67 20 ASE(2)...string
11d0: 62 6f 78 65 73 5f 5b 5d 20 3d 20 7b 22 36 20 39 boxes_[] = {"6 9
11e0: 37 20 37 22 2c 22 37 33 20 34 35 20 30 22 2c 22 7 7","73 45 0","
11f0: 36 37 20 34 35 20 36 33 22 7d 3b 0d 0a 09 20 20 67 45 63"};...
1200: 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e 20 vector <string>
1210: 62 6f 78 65 73 28 62 6f 78 65 73 5f 2c 20 62 6f boxes(boxes_, bo
1220: 78 65 73 5f 2b 73 69 7a 65 6f 66 28 62 6f 78 65 xes_+sizeof(boxe
1230: 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 6f 78 65 s_)/sizeof(*boxe
1240: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d s_)); ...int _ =
1250: 20 31 37 30 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 170; ..END..CAS
1260: 45 28 33 29 0d 0a 09 73 74 72 69 6e 67 20 62 6f E(3)...string bo
1270: 78 65 73 5f 5b 5d 20 3d 20 7b 22 39 37 20 39 34 xes_[] = {"97 94
1280: 20 30 20 39 39 22 2c 22 31 20 37 32 20 34 36 20 0 99","1 72 46
1290: 34 35 22 2c 22 30 20 31 30 20 34 37 20 37 35 22 45","0 10 47 75"
12a0: 2c 22 30 20 39 32 20 37 36 20 32 30 22 2c 22 32 ,"0 92 76 20","2
12b0: 20 32 35 20 39 38 20 32 32 22 7d 3b 0d 0a 09 20 25 98 22"};...
12c0: 20 76 65 63 74 6f 72 20 3c 73 74 72 69 6e 67 3e vector <string>
12d0: 20 62 6f 78 65 73 28 62 6f 78 65 73 5f 2c 20 62 boxes(boxes_, b
12e0: 6f 78 65 73 5f 2b 73 69 7a 65 6f 66 28 62 6f 78 oxes_+sizeof(box
12f0: 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 62 6f 78 es_)/sizeof(*box
1300: 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 es_)); ...int _
1310: 3d 20 35 35 39 3b 20 0d 0a 45 4e 44 0d 0a 43 41 = 559; ..END..CA
1320: 53 45 28 34 29 0d 0a 09 73 74 72 69 6e 67 20 62 SE(4)...string b
1330: 6f 78 65 73 5f 5b 5d 20 3d 20 7b 22 33 38 20 30 oxes_[] = {"38 0
1340: 20 30 20 34 35 20 37 37 20 36 31 20 30 20 30 20 0 45 77 61 0 0
1350: 38 20 38 37 20 36 35 20 35 33 20 30 20 32 22 2c 8 87 65 53 0 2",
1360: 0d 0a 20 22 30 20 39 37 20 37 39 20 33 37 20 37 .. "0 97 79 37 7
1370: 30 20 30 20 36 39 20 33 35 20 39 35 20 31 31 20 0 0 69 35 95 11
1380: 37 35 20 39 36 20 37 37 20 32 39 22 2c 0d 0a 20 75 96 77 29",..
1390: 22 33 39 20 33 32 20 30 20 32 34 20 36 33 20 32 "39 32 0 24 63 2
13a0: 32 20 39 31 20 37 31 20 30 20 36 33 20 39 32 20 2 91 71 0 63 92
13b0: 35 39 20 31 32 20 30 22 2c 0d 0a 20 22 33 34 20 59 12 0",.. "34
13c0: 30 20 30 20 37 31 20 38 38 20 31 33 20 36 30 20 0 0 71 88 13 60
13d0: 35 36 20 30 20 32 32 20 32 39 20 38 39 20 38 31 56 0 22 29 89 81
13e0: 20 35 33 22 2c 0d 0a 20 22 36 39 20 39 35 20 36 53",.. "69 95 6
13f0: 35 20 30 20 39 34 20 39 38 20 38 34 20 33 37 20 5 0 94 98 84 37
1400: 30 20 38 37 20 31 36 20 30 20 35 38 20 31 38 22 0 87 16 0 58 18"
1410: 2c 0d 0a 20 22 38 32 20 30 20 33 36 20 38 38 20 ,.. "82 0 36 88
1420: 30 20 35 34 20 38 32 20 34 30 20 36 20 30 20 33 0 54 82 40 6 0 3
1430: 34 20 34 34 20 38 30 20 32 22 2c 0d 0a 20 22 33 4 44 80 2",.. "3
1440: 33 20 35 38 20 37 20 39 35 20 38 33 20 38 37 20 3 58 7 95 83 87
1450: 30 20 30 20 37 39 20 33 35 20 30 20 35 31 20 32 0 0 79 35 0 51 2
1460: 32 20 38 34 22 2c 0d 0a 20 22 37 20 30 20 33 30 2 84",.. "7 0 30
1470: 20 35 37 20 33 33 20 34 20 30 20 32 36 20 34 34 57 33 4 0 26 44
1480: 20 35 35 20 36 37 20 33 31 20 38 38 20 34 32 22 55 67 31 88 42"
1490: 2c 0d 0a 20 22 36 32 20 35 38 20 36 32 20 39 33 ,.. "62 58 62 93
14a0: 20 39 31 20 30 20 31 20 30 20 34 34 20 32 33 20 91 0 1 0 44 23
14b0: 39 35 20 30 20 35 35 20 35 37 22 2c 0d 0a 20 22 95 0 55 57",.. "
14c0: 33 35 20 38 20 32 32 20 32 36 20 37 36 20 30 20 35 8 22 26 76 0
14d0: 37 38 20 35 34 20 30 20 34 36 20 34 32 20 30 20 78 54 0 46 42 0
14e0: 30 20 36 34 22 2c 0d 0a 20 22 39 33 20 35 34 20 0 64",.. "93 54
14f0: 35 38 20 30 20 38 39 20 38 39 20 30 20 30 20 35 58 0 89 89 0 0 5
1500: 37 20 30 20 39 38 20 33 20 32 34 20 30 22 2c 0d 7 0 98 3 24 0",.
1510: 0a 20 22 39 20 30 20 30 20 32 33 20 38 32 20 31 . "9 0 0 23 82 1
1520: 38 20 30 20 34 36 20 30 20 30 20 39 34 20 38 34 8 0 46 0 0 94 84
1530: 20 31 39 20 31 38 22 2c 0d 0a 20 22 37 38 20 31 19 18",.. "78 1
1540: 32 20 36 20 34 35 20 30 20 38 30 20 31 36 20 36 2 6 45 0 80 16 6
1550: 39 20 35 39 20 37 36 20 33 35 20 30 20 36 36 20 9 59 76 35 0 66
1560: 30 22 2c 0d 0a 20 22 30 20 36 38 20 37 37 20 31 0",.. "0 68 77 1
1570: 33 20 31 35 20 30 20 35 32 20 37 32 20 30 20 30 3 15 0 52 72 0 0
1580: 20 31 38 20 36 35 20 32 33 20 30 22 2c 0d 0a 20 18 65 23 0",..
1590: 22 30 20 30 20 37 33 20 35 33 20 30 20 39 35 20 "0 0 73 53 0 95
15a0: 39 31 20 34 34 20 32 37 20 39 36 20 38 35 20 30 91 44 27 96 85 0
15b0: 20 39 39 20 38 35 22 2c 0d 0a 20 22 39 33 20 32 99 85",.. "93 2
15c0: 39 20 34 20 38 39 20 32 37 20 34 34 20 32 37 20 9 4 89 27 44 27
15d0: 31 37 20 32 31 20 36 20 30 20 38 20 33 20 39 31 17 21 6 0 8 3 91
15e0: 22 2c 0d 0a 20 22 30 20 34 36 20 37 33 20 39 34 ",.. "0 46 73 94
15f0: 20 36 30 20 35 39 20 31 35 20 35 30 20 31 38 20 60 59 15 50 18
1600: 37 35 20 37 34 20 38 38 20 34 36 20 39 33 22 2c 75 74 88 46 93",
1610: 0d 0a 20 22 30 20 30 20 30 20 39 34 20 39 33 20 .. "0 0 0 94 93
1620: 32 36 20 32 31 20 38 33 20 35 34 20 36 32 20 30 26 21 83 54 62 0
1630: 20 38 39 20 35 39 20 37 37 22 2c 0d 0a 20 22 33 89 59 77",.. "3
1640: 32 20 39 38 20 30 20 34 34 20 33 34 20 33 38 20 2 98 0 44 34 38
1650: 35 36 20 32 30 20 30 20 36 31 20 32 39 20 39 34 56 20 0 61 29 94
1660: 20 35 32 20 35 37 22 2c 0d 0a 20 22 35 32 20 36 52 57",.. "52 6
1670: 30 20 30 20 32 32 20 30 20 35 20 33 38 20 30 20 0 0 22 0 5 38 0
1680: 35 30 20 39 38 20 31 32 20 37 35 20 30 20 38 31 50 98 12 75 0 81
1690: 22 2c 0d 0a 20 22 32 33 20 30 20 34 31 20 31 38 ",.. "23 0 41 18
16a0: 20 33 36 20 38 37 20 34 39 20 33 32 20 36 32 20 36 87 49 32 62
16b0: 34 33 20 32 32 20 37 34 20 30 20 39 37 22 2c 0d 43 22 74 0 97",.
16c0: 0a 20 22 30 20 30 20 33 30 20 37 39 20 31 36 20 . "0 0 30 79 16
16d0: 37 33 20 36 31 20 30 20 37 35 20 35 31 20 36 34 73 61 0 75 51 64
16e0: 20 31 33 20 34 35 20 30 22 2c 0d 0a 20 22 31 31 13 45 0",.. "11
16f0: 20 30 20 31 34 20 32 20 30 20 31 20 32 20 31 36 0 14 2 0 1 2 16
1700: 20 38 34 20 33 37 20 39 35 20 34 35 20 34 38 20 84 37 95 45 48
1710: 33 33 22 2c 0d 0a 20 22 31 30 20 30 20 30 20 33 33",.. "10 0 0 3
1720: 35 20 30 20 38 35 20 32 38 20 37 36 20 39 39 20 5 0 85 28 76 99
1730: 37 34 20 37 36 20 33 32 20 35 32 20 38 22 2c 0d 74 76 32 52 8",.
1740: 0a 20 22 36 30 20 30 20 39 36 20 30 20 39 35 20 . "60 0 96 0 95
1750: 32 36 20 35 39 20 31 33 20 30 20 30 20 34 34 20 26 59 13 0 0 44
1760: 34 32 20 39 37 20 34 38 22 2c 0d 0a 20 22 33 34 42 97 48",.. "34
1770: 20 37 20 37 37 20 32 35 20 39 31 20 38 35 20 33 7 77 25 91 85 3
1780: 35 20 37 38 20 33 32 20 39 39 20 37 20 32 39 20 5 78 32 99 7 29
1790: 31 38 20 31 35 22 2c 0d 0a 20 22 36 31 20 35 30 18 15",.. "61 50
17a0: 20 34 33 20 32 32 20 34 32 20 36 33 20 36 34 20 43 22 42 63 64
17b0: 35 30 20 39 20 39 34 20 34 32 20 32 32 20 32 31 50 9 94 42 22 21
17c0: 20 33 33 22 2c 0d 0a 20 22 35 38 20 30 20 34 31 33",.. "58 0 41
17d0: 20 31 30 20 31 36 20 30 20 32 37 20 36 37 20 38 10 16 0 27 67 8
17e0: 33 20 32 37 20 31 34 20 33 37 20 39 38 20 34 37 3 27 14 37 98 47
17f0: 22 2c 0d 0a 20 22 33 37 20 36 30 20 36 30 20 37 ",.. "37 60 60 7
1800: 36 20 37 31 20 32 20 38 34 20 33 32 20 32 37 20 6 71 2 84 32 27
1810: 33 39 20 38 32 20 38 34 20 30 20 39 34 22 2c 0d 39 82 84 0 94",.
1820: 0a 20 22 31 35 20 39 38 20 36 39 20 38 32 20 33 . "15 98 69 82 3
1830: 36 20 36 36 20 30 20 39 37 20 36 32 20 33 39 20 6 66 0 97 62 39
1840: 30 20 36 35 20 36 32 20 36 37 22 2c 0d 0a 20 22 0 65 62 67",.. "
1850: 30 20 34 31 20 30 20 34 33 20 30 20 30 20 39 34 0 41 0 43 0 0 94
1860: 20 30 20 30 20 35 38 20 30 20 30 20 32 37 20 33 0 0 58 0 0 27 3
1870: 33 22 2c 0d 0a 20 22 35 33 20 39 30 20 37 31 20 3",.. "53 90 71
1880: 39 31 20 38 35 20 30 20 33 32 20 38 36 20 34 30 91 85 0 32 86 40
1890: 20 36 30 20 31 31 20 30 20 39 39 20 32 38 22 2c 60 11 0 99 28",
18a0: 0d 0a 20 22 37 39 20 36 32 20 30 20 30 20 37 39 .. "79 62 0 0 79
18b0: 20 30 20 31 34 20 36 32 20 38 37 20 37 36 20 33 0 14 62 87 76 3
18c0: 35 20 30 20 37 30 20 30 22 2c 0d 0a 20 22 30 20 5 0 70 0",.. "0
18d0: 34 30 20 37 33 20 34 38 20 30 20 36 33 20 30 20 40 73 48 0 63 0
18e0: 30 20 36 33 20 35 20 33 30 20 31 38 20 34 37 20 0 63 5 30 18 47
18f0: 35 31 22 2c 0d 0a 20 22 37 35 20 36 20 35 38 20 51",.. "75 6 58
1900: 36 39 20 33 33 20 35 37 20 36 36 20 30 20 31 32 69 33 57 66 0 12
1910: 20 30 20 34 36 20 30 20 36 35 20 31 30 22 7d 3b 0 46 0 65 10"};
1920: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 72 ... vector <str
1930: 69 6e 67 3e 20 62 6f 78 65 73 28 62 6f 78 65 73 ing> boxes(boxes
1940: 5f 2c 20 62 6f 78 65 73 5f 2b 73 69 7a 65 6f 66 _, boxes_+sizeof
1950: 28 62 6f 78 65 73 5f 29 2f 73 69 7a 65 6f 66 28 (boxes_)/sizeof(
1960: 2a 62 6f 78 65 73 5f 29 29 3b 20 0d 0a 09 69 6e *boxes_)); ...in
1970: 74 20 5f 20 3d 20 31 38 36 31 38 3b 20 0d 0a 45 t _ = 18618; ..E
1980: 4e 44 0d 0a 2f 2a 0d 0a 43 41 53 45 28 35 29 0d ND../*..CASE(5).
1990: 0a 09 73 74 72 69 6e 67 20 62 6f 78 65 73 5f 5b ..string boxes_[
19a0: 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f 72 ] = ;... vector
19b0: 20 3c 73 74 72 69 6e 67 3e 20 62 6f 78 65 73 28 <string> boxes(
19c0: 62 6f 78 65 73 5f 2c 20 62 6f 78 65 73 5f 2b 73 boxes_, boxes_+s
19d0: 69 7a 65 6f 66 28 62 6f 78 65 73 5f 29 2f 73 69 izeof(boxes_)/si
19e0: 7a 65 6f 66 28 2a 62 6f 78 65 73 5f 29 29 3b 20 zeof(*boxes_));
19f0: 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 ...int _ = ; ..E
1a00: 4e 44 0d 0a 43 41 53 45 28 36 29 0d 0a 09 73 74 ND..CASE(6)...st
1a10: 72 69 6e 67 20 62 6f 78 65 73 5f 5b 5d 20 3d 20 ring boxes_[] =
1a20: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 73 74 ;... vector <st
1a30: 72 69 6e 67 3e 20 62 6f 78 65 73 28 62 6f 78 65 ring> boxes(boxe
1a40: 73 5f 2c 20 62 6f 78 65 73 5f 2b 73 69 7a 65 6f s_, boxes_+sizeo
1a50: 66 28 62 6f 78 65 73 5f 29 2f 73 69 7a 65 6f 66 f(boxes_)/sizeof
1a60: 28 2a 62 6f 78 65 73 5f 29 29 3b 20 0d 0a 09 69 (*boxes_)); ...i
1a70: 6e 74 20 5f 20 3d 20 3b 20 0d 0a 45 4e 44 0d 0a nt _ = ; ..END..
1a80: 2a 2f 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 */..}..// END CU
1a90: 54 20 48 45 52 45 0d 0a T HERE..