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 74 75 70 6c 65 3e 0d 0a 75 73 69 6e 67 20 6e <tuple>..using n
0150: 61 6d 65 73 70 61 63 65 20 73 74 64 3b 0d 0a 74 amespace std;..t
0160: 79 70 65 64 65 66 20 6c 6f 6e 67 20 6c 6f 6e 67 ypedef long long
0170: 20 4c 4c 3b 0d 0a 74 79 70 65 64 65 66 20 63 6f LL;..typedef co
0180: 6d 70 6c 65 78 3c 64 6f 75 62 6c 65 3e 20 43 4d mplex<double> CM
0190: 50 3b 0d 0a 0d 0a 63 6c 61 73 73 20 53 74 6f 72 P;....class Stor
01a0: 79 46 72 6f 6d 54 43 4f 20 7b 20 70 75 62 6c 69 yFromTCO { publi
01b0: 63 3a 0d 0a 09 69 6e 74 20 6d 69 6e 69 6d 75 6d c:...int minimum
01c0: 43 68 61 6e 67 65 73 28 76 65 63 74 6f 72 20 3c Changes(vector <
01d0: 69 6e 74 3e 20 70 6c 61 63 65 73 2c 20 76 65 63 int> places, vec
01e0: 74 6f 72 20 3c 69 6e 74 3e 20 63 75 74 6f 66 66 tor <int> cutoff
01f0: 29 0d 0a 09 7b 0d 0a 09 09 63 6f 6e 73 74 20 69 )...{....const i
0200: 6e 74 20 4e 20 3d 20 70 6c 61 63 65 73 2e 73 69 nt N = places.si
0210: 7a 65 28 29 3b 0d 0a 09 09 76 65 63 74 6f 72 3c ze();....vector<
0220: 70 61 69 72 3c 69 6e 74 2c 69 6e 74 3e 3e 20 63 pair<int,int>> c
0230: 70 3b 0d 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d p;....for(int i=
0240: 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0d 0a 09 09 0; i<N; ++i)....
0250: 09 63 70 2e 65 6d 70 6c 61 63 65 5f 62 61 63 6b .cp.emplace_back
0260: 28 63 75 74 6f 66 66 5b 69 5d 2c 20 70 6c 61 63 (cutoff[i], plac
0270: 65 73 5b 69 5d 29 3b 0d 0a 09 09 73 6f 72 74 28 es[i]);....sort(
0280: 63 70 2e 62 65 67 69 6e 28 29 2c 20 63 70 2e 65 cp.begin(), cp.e
0290: 6e 64 28 29 29 3b 0d 0a 0d 0a 09 09 76 65 63 74 nd());......vect
02a0: 6f 72 3c 69 6e 74 3e 20 6c 6d 28 4e 29 3b 20 20 or<int> lm(N);
02b0: 2f 2f 20 69 2d 74 68 20 70 6c 61 63 65 20 63 61 // i-th place ca
02c0: 6e 64 69 64 61 74 65 20 63 61 6e 20 62 65 20 70 ndidate can be p
02d0: 75 74 20 61 74 20 3e 3d 6c 6d 5b 69 5d 0d 0a 09 ut at >=lm[i]...
02e0: 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c .for(int i=0; i<
02f0: 4e 3b 20 2b 2b 69 29 20 7b 0d 0a 09 09 09 69 6e N; ++i) {.....in
0300: 74 20 70 3d 63 70 5b 69 5d 2e 73 65 63 6f 6e 64 t p=cp[i].second
0310: 2c 20 6b 3d 30 3b 0d 0a 09 09 09 66 6f 72 28 3b , k=0;.....for(;
0320: 20 6b 3c 4e 3b 20 2b 2b 6b 29 0d 0a 09 09 09 09 k<N; ++k)......
0330: 69 66 28 70 20 3c 3d 20 63 70 5b 6b 5d 2e 66 69 if(p <= cp[k].fi
0340: 72 73 74 29 0d 0a 09 09 09 09 09 62 72 65 61 6b rst).......break
0350: 3b 0d 0a 09 09 09 69 66 28 6b 20 3d 3d 20 4e 29 ;.....if(k == N)
0360: 0d 0a 09 09 09 09 72 65 74 75 72 6e 20 2d 31 3b ......return -1;
0370: 0d 0a 09 09 09 6c 6d 5b 69 5d 20 3d 20 6b 3b 0d .....lm[i] = k;.
0380: 0a 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 73 ...}....return s
0390: 6f 6c 76 65 28 6c 6d 29 3b 0d 0a 09 7d 0d 0a 0d olve(lm);...}...
03a0: 0a 09 2f 2f 20 72 65 6f 72 64 65 72 20 76 20 73 ..// reorder v s
03b0: 6f 20 74 68 61 74 20 76 5b 69 5d 3c 3d 69 20 66 o that v[i]<=i f
03c0: 6f 72 20 61 6c 6c 20 69 2e 0d 0a 09 69 6e 74 20 or all i....int
03d0: 73 6f 6c 76 65 28 76 65 63 74 6f 72 3c 69 6e 74 solve(vector<int
03e0: 3e 20 76 29 0d 0a 09 7b 0d 0a 09 09 63 6f 6e 73 > v)...{....cons
03f0: 74 20 69 6e 74 20 4e 20 3d 20 76 2e 73 69 7a 65 t int N = v.size
0400: 28 29 3b 0d 0a 09 09 63 6f 6e 73 74 20 69 6e 74 ();....const int
0410: 20 48 4f 4c 45 20 3d 20 30 78 37 66 66 66 66 66 HOLE = 0x7fffff
0420: 66 66 3b 0d 0a 09 09 69 6e 74 20 61 6e 73 20 3d ff;....int ans =
0430: 20 30 3b 0d 0a 09 09 6d 75 6c 74 69 73 65 74 3c 0;....multiset<
0440: 69 6e 74 3e 20 73 74 6f 63 6b 3b 0d 0a 09 09 66 int> stock;....f
0450: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b or(int i=0; i<N;
0460: 20 2b 2b 69 29 0d 0a 09 09 09 69 66 28 21 28 76 ++i).....if(!(v
0470: 5b 69 5d 3c 3d 69 29 29 20 7b 0d 0a 09 09 09 09 [i]<=i)) {......
0480: 69 66 28 73 74 6f 63 6b 2e 65 6d 70 74 79 28 29 if(stock.empty()
0490: 20 7c 7c 20 21 28 2a 73 74 6f 63 6b 2e 62 65 67 || !(*stock.beg
04a0: 69 6e 28 29 3c 3d 69 29 29 20 7b 0d 0a 09 09 09 in()<=i)) {.....
04b0: 09 09 2f 2f 20 66 69 6e 64 20 72 69 67 68 74 20 ..// find right
04c0: 6d 6f 73 74 20 66 69 74 74 69 6e 67 20 65 6c 65 most fitting ele
04d0: 6d 2e 0d 0a 09 09 09 09 09 66 6f 72 28 69 6e 74 m........for(int
04e0: 20 6b 3d 4e 2d 31 3b 20 6b 3e 69 3b 20 2d 2d 6b k=N-1; k>i; --k
04f0: 29 0d 0a 09 09 09 09 09 09 69 66 28 76 5b 6b 5d )........if(v[k]
0500: 3c 3d 69 29 20 7b 0d 0a 09 09 09 09 09 09 09 73 <=i) {.........s
0510: 74 6f 63 6b 2e 69 6e 73 65 72 74 28 76 5b 6b 5d tock.insert(v[k]
0520: 29 3b 0d 0a 09 09 09 09 09 09 09 76 5b 6b 5d 20 );.........v[k]
0530: 3d 20 48 4f 4c 45 3b 0d 0a 09 09 09 09 09 09 09 = HOLE;.........
0540: 62 72 65 61 6b 3b 0d 0a 09 09 09 09 09 09 7d 0d break;........}.
0550: 0a 09 09 09 09 7d 0d 0a 0d 0a 09 09 09 09 69 66 .....}........if
0560: 28 73 74 6f 63 6b 2e 65 6d 70 74 79 28 29 20 7c (stock.empty() |
0570: 7c 20 21 28 2a 73 74 6f 63 6b 2e 62 65 67 69 6e | !(*stock.begin
0580: 28 29 3c 3d 69 29 29 0d 0a 09 09 09 09 09 72 65 ()<=i)).......re
0590: 74 75 72 6e 20 2d 31 3b 0d 0a 0d 0a 09 09 09 09 turn -1;........
05a0: 2b 2b 61 6e 73 3b 0d 0a 09 09 09 09 69 66 28 76 ++ans;......if(v
05b0: 5b 69 5d 20 21 3d 20 48 4f 4c 45 29 20 73 74 6f [i] != HOLE) sto
05c0: 63 6b 2e 69 6e 73 65 72 74 28 76 5b 69 5d 29 3b ck.insert(v[i]);
05d0: 0d 0a 09 09 09 09 76 5b 69 5d 20 3d 20 2a 73 74 ......v[i] = *st
05e0: 6f 63 6b 2e 62 65 67 69 6e 28 29 3b 0d 0a 09 09 ock.begin();....
05f0: 09 09 73 74 6f 63 6b 2e 65 72 61 73 65 28 73 74 ..stock.erase(st
0600: 6f 63 6b 2e 62 65 67 69 6e 28 29 29 3b 0d 0a 09 ock.begin());...
0610: 09 09 7d 0d 0a 09 09 72 65 74 75 72 6e 20 61 6e ..}....return an
0620: 73 3b 0d 0a 09 7d 0d 0a 7d 3b 0d 0a 0d 0a 2f 2f s;...}..};....//
0630: 20 42 45 47 49 4e 20 43 55 54 20 48 45 52 45 0d BEGIN CUT HERE.
0640: 0a 23 69 6e 63 6c 75 64 65 20 3c 63 74 69 6d 65 .#include <ctime
0650: 3e 0d 0a 64 6f 75 62 6c 65 20 73 74 61 72 74 5f >..double start_
0660: 74 69 6d 65 3b 20 73 74 72 69 6e 67 20 74 69 6d time; string tim
0670: 65 72 28 29 0d 0a 20 7b 20 6f 73 74 72 69 6e 67 er().. { ostring
0680: 73 74 72 65 61 6d 20 6f 73 3b 20 6f 73 20 3c 3c stream os; os <<
0690: 20 22 20 28 22 20 3c 3c 20 69 6e 74 28 28 63 6c " (" << int((cl
06a0: 6f 63 6b 28 29 2d 73 74 61 72 74 5f 74 69 6d 65 ock()-start_time
06b0: 29 2f 43 4c 4f 43 4b 53 5f 50 45 52 5f 53 45 43 )/CLOCKS_PER_SEC
06c0: 2a 31 30 30 30 29 20 3c 3c 20 22 20 6d 73 65 63 *1000) << " msec
06d0: 29 22 3b 20 72 65 74 75 72 6e 20 6f 73 2e 73 74 )"; return os.st
06e0: 72 28 29 3b 20 7d 0d 0a 74 65 6d 70 6c 61 74 65 r(); }..template
06f0: 3c 74 79 70 65 6e 61 6d 65 20 54 3e 20 6f 73 74 <typename T> ost
0700: 72 65 61 6d 26 20 6f 70 65 72 61 74 6f 72 3c 3c ream& operator<<
0710: 28 6f 73 74 72 65 61 6d 26 20 6f 73 2c 20 63 6f (ostream& os, co
0720: 6e 73 74 20 76 65 63 74 6f 72 3c 54 3e 26 20 76 nst vector<T>& v
0730: 29 0d 0a 20 7b 20 6f 73 20 3c 3c 20 22 7b 20 22 ).. { os << "{ "
0740: 3b 0d 0a 20 20 20 66 6f 72 28 74 79 70 65 6e 61 ;.. for(typena
0750: 6d 65 20 76 65 63 74 6f 72 3c 54 3e 3a 3a 63 6f me vector<T>::co
0760: 6e 73 74 5f 69 74 65 72 61 74 6f 72 20 69 74 3d nst_iterator it=
0770: 76 2e 62 65 67 69 6e 28 29 3b 20 69 74 21 3d 76 v.begin(); it!=v
0780: 2e 65 6e 64 28 29 3b 20 2b 2b 69 74 29 0d 0a 20 .end(); ++it)..
0790: 20 20 6f 73 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 os << '\"' <<
07a0: 2a 69 74 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 28 *it << '\"' << (
07b0: 69 74 2b 31 3d 3d 76 2e 65 6e 64 28 29 20 3f 20 it+1==v.end() ?
07c0: 22 22 20 3a 20 22 2c 20 22 29 3b 20 6f 73 20 3c "" : ", "); os <
07d0: 3c 20 22 20 7d 22 3b 20 72 65 74 75 72 6e 20 6f < " }"; return o
07e0: 73 3b 20 7d 0d 0a 76 6f 69 64 20 76 65 72 69 66 s; }..void verif
07f0: 79 5f 63 61 73 65 28 63 6f 6e 73 74 20 69 6e 74 y_case(const int
0800: 26 20 45 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 & Expected, cons
0810: 74 20 69 6e 74 26 20 52 65 63 65 69 76 65 64 29 t int& Received)
0820: 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b 20 3d 20 28 {.. bool ok = (
0830: 45 78 70 65 63 74 65 64 20 3d 3d 20 52 65 63 65 Expected == Rece
0840: 69 76 65 64 29 3b 0d 0a 20 69 66 28 6f 6b 29 20 ived);.. if(ok)
0850: 63 65 72 72 20 3c 3c 20 22 50 41 53 53 45 44 22 cerr << "PASSED"
0860: 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 << timer() << e
0870: 6e 64 6c 3b 20 20 65 6c 73 65 20 7b 20 63 65 72 ndl; else { cer
0880: 72 20 3c 3c 20 22 46 41 49 4c 45 44 22 20 3c 3c r << "FAILED" <<
0890: 20 74 69 6d 65 72 28 29 20 3c 3c 20 65 6e 64 6c timer() << endl
08a0: 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 22 5c 74 6f ;.. cerr << "\to
08b0: 3a 20 5c 22 22 20 3c 3c 20 45 78 70 65 63 74 65 : \"" << Expecte
08c0: 64 20 3c 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 d << '\"' << end
08d0: 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c 22 22 20 3c l << "\tx: \"" <
08e0: 3c 20 52 65 63 65 69 76 65 64 20 3c 3c 20 27 5c < Received << '\
08f0: 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 7d 20 7d 0d "' << endl; } }.
0900: 0a 23 64 65 66 69 6e 65 20 43 41 53 45 28 4e 29 .#define CASE(N)
0910: 20 7b 63 65 72 72 20 3c 3c 20 22 54 65 73 74 20 {cerr << "Test
0920: 43 61 73 65 20 23 22 20 3c 3c 20 4e 20 3c 3c 20 Case #" << N <<
0930: 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 73 68 3b 20 "..." << flush;
0940: 73 74 61 72 74 5f 74 69 6d 65 3d 63 6c 6f 63 6b start_time=clock
0950: 28 29 3b 0d 0a 23 64 65 66 69 6e 65 20 45 4e 44 ();..#define END
0960: 09 20 76 65 72 69 66 79 5f 63 61 73 65 28 5f 2c . verify_case(_,
0970: 20 53 74 6f 72 79 46 72 6f 6d 54 43 4f 28 29 2e StoryFromTCO().
0980: 6d 69 6e 69 6d 75 6d 43 68 61 6e 67 65 73 28 70 minimumChanges(p
0990: 6c 61 63 65 73 2c 20 63 75 74 6f 66 66 29 29 3b laces, cutoff));
09a0: 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b 0d 0a }..int main(){..
09b0: 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e 74 20 ..CASE(0)...int
09c0: 70 6c 61 63 65 73 5f 5b 5d 20 3d 20 7b 32 30 2c places_[] = {20,
09d0: 31 30 30 2c 35 30 30 2c 35 30 7d 3b 0d 0a 09 20 100,500,50};...
09e0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c vector <int> pl
09f0: 61 63 65 73 28 70 6c 61 63 65 73 5f 2c 20 70 6c aces(places_, pl
0a00: 61 63 65 73 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 aces_+sizeof(pla
0a10: 63 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c ces_)/sizeof(*pl
0a20: 61 63 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 aces_)); ...int
0a30: 63 75 74 6f 66 66 5f 5b 5d 20 3d 20 7b 37 35 30 cutoff_[] = {750
0a40: 30 2c 32 32 35 30 2c 31 35 30 2c 32 34 7d 3b 0d 0,2250,150,24};.
0a50: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0a60: 20 63 75 74 6f 66 66 28 63 75 74 6f 66 66 5f 2c cutoff(cutoff_,
0a70: 20 63 75 74 6f 66 66 5f 2b 73 69 7a 65 6f 66 28 cutoff_+sizeof(
0a80: 63 75 74 6f 66 66 5f 29 2f 73 69 7a 65 6f 66 28 cutoff_)/sizeof(
0a90: 2a 63 75 74 6f 66 66 5f 29 29 3b 20 0d 0a 09 69 *cutoff_)); ...i
0aa0: 6e 74 20 5f 20 3d 20 33 3b 20 0d 0a 45 4e 44 0d nt _ = 3; ..END.
0ab0: 0a 43 41 53 45 28 31 29 0d 0a 09 69 6e 74 20 70 .CASE(1)...int p
0ac0: 6c 61 63 65 73 5f 5b 5d 20 3d 20 7b 35 2c 34 2c laces_[] = {5,4,
0ad0: 33 2c 32 2c 31 7d 3b 0d 0a 09 20 20 76 65 63 74 3,2,1};... vect
0ae0: 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 63 65 73 28 or <int> places(
0af0: 70 6c 61 63 65 73 5f 2c 20 70 6c 61 63 65 73 5f places_, places_
0b00: 2b 73 69 7a 65 6f 66 28 70 6c 61 63 65 73 5f 29 +sizeof(places_)
0b10: 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 63 65 73 5f /sizeof(*places_
0b20: 29 29 3b 20 0d 0a 09 69 6e 74 20 63 75 74 6f 66 )); ...int cutof
0b30: 66 5f 5b 5d 20 3d 20 7b 35 2c 34 2c 33 2c 32 2c f_[] = {5,4,3,2,
0b40: 31 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 1};... vector <
0b50: 69 6e 74 3e 20 63 75 74 6f 66 66 28 63 75 74 6f int> cutoff(cuto
0b60: 66 66 5f 2c 20 63 75 74 6f 66 66 5f 2b 73 69 7a ff_, cutoff_+siz
0b70: 65 6f 66 28 63 75 74 6f 66 66 5f 29 2f 73 69 7a eof(cutoff_)/siz
0b80: 65 6f 66 28 2a 63 75 74 6f 66 66 5f 29 29 3b 20 eof(*cutoff_));
0b90: 0d 0a 09 69 6e 74 20 5f 20 3d 20 30 3b 20 0d 0a ...int _ = 0; ..
0ba0: 45 4e 44 0d 0a 43 41 53 45 28 32 29 0d 0a 09 69 END..CASE(2)...i
0bb0: 6e 74 20 70 6c 61 63 65 73 5f 5b 5d 20 3d 20 7b nt places_[] = {
0bc0: 31 2c 35 2c 35 2c 35 7d 3b 0d 0a 09 20 20 76 65 1,5,5,5};... ve
0bd0: 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 63 65 ctor <int> place
0be0: 73 28 70 6c 61 63 65 73 5f 2c 20 70 6c 61 63 65 s(places_, place
0bf0: 73 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 63 65 73 s_+sizeof(places
0c00: 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 63 65 _)/sizeof(*place
0c10: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 75 74 s_)); ...int cut
0c20: 6f 66 66 5f 5b 5d 20 3d 20 7b 38 2c 36 2c 34 2c off_[] = {8,6,4,
0c30: 32 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 2};... vector <
0c40: 69 6e 74 3e 20 63 75 74 6f 66 66 28 63 75 74 6f int> cutoff(cuto
0c50: 66 66 5f 2c 20 63 75 74 6f 66 66 5f 2b 73 69 7a ff_, cutoff_+siz
0c60: 65 6f 66 28 63 75 74 6f 66 66 5f 29 2f 73 69 7a eof(cutoff_)/siz
0c70: 65 6f 66 28 2a 63 75 74 6f 66 66 5f 29 29 3b 20 eof(*cutoff_));
0c80: 0d 0a 09 69 6e 74 20 5f 20 3d 20 2d 31 3b 20 0d ...int _ = -1; .
0c90: 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d 0a 09 .END..CASE(3)...
0ca0: 69 6e 74 20 70 6c 61 63 65 73 5f 5b 5d 20 3d 20 int places_[] =
0cb0: 7b 33 2c 31 2c 35 7d 3b 0d 0a 09 20 20 76 65 63 {3,1,5};... vec
0cc0: 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 63 65 73 tor <int> places
0cd0: 28 70 6c 61 63 65 73 5f 2c 20 70 6c 61 63 65 73 (places_, places
0ce0: 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 63 65 73 5f _+sizeof(places_
0cf0: 29 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 63 65 73 )/sizeof(*places
0d00: 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 75 74 6f _)); ...int cuto
0d10: 66 66 5f 5b 5d 20 3d 20 7b 36 2c 34 2c 32 7d 3b ff_[] = {6,4,2};
0d20: 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 ... vector <int
0d30: 3e 20 63 75 74 6f 66 66 28 63 75 74 6f 66 66 5f > cutoff(cutoff_
0d40: 2c 20 63 75 74 6f 66 66 5f 2b 73 69 7a 65 6f 66 , cutoff_+sizeof
0d50: 28 63 75 74 6f 66 66 5f 29 2f 73 69 7a 65 6f 66 (cutoff_)/sizeof
0d60: 28 2a 63 75 74 6f 66 66 5f 29 29 3b 20 0d 0a 09 (*cutoff_)); ...
0d70: 69 6e 74 20 5f 20 3d 20 33 3b 20 0d 0a 45 4e 44 int _ = 3; ..END
0d80: 0d 0a 43 41 53 45 28 34 29 0d 0a 09 69 6e 74 20 ..CASE(4)...int
0d90: 70 6c 61 63 65 73 5f 5b 5d 20 3d 20 7b 31 34 2c places_[] = {14,
0da0: 31 31 2c 34 32 2c 39 2c 31 39 7d 3b 0d 0a 09 20 11,42,9,19};...
0db0: 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c vector <int> pl
0dc0: 61 63 65 73 28 70 6c 61 63 65 73 5f 2c 20 70 6c aces(places_, pl
0dd0: 61 63 65 73 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 aces_+sizeof(pla
0de0: 63 65 73 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c ces_)/sizeof(*pl
0df0: 61 63 65 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 aces_)); ...int
0e00: 63 75 74 6f 66 66 5f 5b 5d 20 3d 20 7b 31 31 2c cutoff_[] = {11,
0e10: 31 36 2c 33 37 2c 34 31 2c 34 37 7d 0d 0a 3b 0d 16,37,41,47}..;.
0e20: 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e 74 3e .. vector <int>
0e30: 20 63 75 74 6f 66 66 28 63 75 74 6f 66 66 5f 2c cutoff(cutoff_,
0e40: 20 63 75 74 6f 66 66 5f 2b 73 69 7a 65 6f 66 28 cutoff_+sizeof(
0e50: 63 75 74 6f 66 66 5f 29 2f 73 69 7a 65 6f 66 28 cutoff_)/sizeof(
0e60: 2a 63 75 74 6f 66 66 5f 29 29 3b 20 0d 0a 09 69 *cutoff_)); ...i
0e70: 6e 74 20 5f 20 3d 20 34 3b 20 0d 0a 45 4e 44 0d nt _ = 4; ..END.
0e80: 0a 43 41 53 45 28 35 29 0d 0a 09 69 6e 74 20 70 .CASE(5)...int p
0e90: 6c 61 63 65 73 5f 5b 5d 20 3d 20 7b 34 2c 31 2c laces_[] = {4,1,
0ea0: 33 2c 33 2c 32 2c 34 2c 35 2c 35 2c 34 2c 34 7d 3,3,2,4,5,5,4,4}
0eb0: 3b 0d 0a 09 20 20 76 65 63 74 6f 72 20 3c 69 6e ;... vector <in
0ec0: 74 3e 20 70 6c 61 63 65 73 28 70 6c 61 63 65 73 t> places(places
0ed0: 5f 2c 20 70 6c 61 63 65 73 5f 2b 73 69 7a 65 6f _, places_+sizeo
0ee0: 66 28 70 6c 61 63 65 73 5f 29 2f 73 69 7a 65 6f f(places_)/sizeo
0ef0: 66 28 2a 70 6c 61 63 65 73 5f 29 29 3b 20 0d 0a f(*places_)); ..
0f00: 09 69 6e 74 20 63 75 74 6f 66 66 5f 5b 5d 20 3d .int cutoff_[] =
0f10: 20 7b 33 2c 33 2c 35 2c 32 2c 34 2c 34 2c 35 2c {3,3,5,2,4,4,5,
0f20: 34 2c 33 2c 35 7d 3b 0d 0a 09 20 20 76 65 63 74 4,3,5};... vect
0f30: 6f 72 20 3c 69 6e 74 3e 20 63 75 74 6f 66 66 28 or <int> cutoff(
0f40: 63 75 74 6f 66 66 5f 2c 20 63 75 74 6f 66 66 5f cutoff_, cutoff_
0f50: 2b 73 69 7a 65 6f 66 28 63 75 74 6f 66 66 5f 29 +sizeof(cutoff_)
0f60: 2f 73 69 7a 65 6f 66 28 2a 63 75 74 6f 66 66 5f /sizeof(*cutoff_
0f70: 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 36 )); ...int _ = 6
0f80: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 36 29 ; ..END..CASE(6)
0f90: 0d 0a 09 69 6e 74 20 70 6c 61 63 65 73 5f 5b 5d ...int places_[]
0fa0: 20 3d 20 7b 32 31 33 2c 31 37 37 2c 32 33 37 2c = {213,177,237,
0fb0: 34 34 34 2c 34 39 37 2c 33 31 35 2c 32 39 34 2c 444,497,315,294,
0fc0: 31 30 34 2c 35 32 32 2c 36 33 35 2c 31 33 2c 32 104,522,635,13,2
0fd0: 36 2c 32 32 2c 32 37 36 2c 38 38 2c 32 34 39 2c 6,22,276,88,249,
0fe0: 33 37 34 2c 31 37 2c 34 32 2c 32 34 35 2c 38 30 374,17,42,245,80
0ff0: 2c 35 35 33 2c 31 32 31 2c 36 32 35 2c 36 32 2c ,553,121,625,62,
1000: 31 30 35 2c 0d 0a 35 33 2c 31 33 32 2c 31 37 38 105,..53,132,178
1010: 2c 32 35 30 2c 31 38 2c 32 31 30 2c 34 39 32 2c ,250,18,210,492,
1020: 31 38 31 2c 32 2c 39 39 2c 32 39 2c 32 31 2c 36 181,2,99,29,21,6
1030: 32 2c 32 31 38 2c 31 38 38 2c 35 38 34 2c 37 30 2,218,188,584,70
1040: 32 2c 36 33 2c 34 31 2c 37 39 2c 32 38 2c 34 35 2,63,41,79,28,45
1050: 32 2c 32 7d 3b 0d 0a 09 20 20 76 65 63 74 6f 72 2,2};... vector
1060: 20 3c 69 6e 74 3e 20 70 6c 61 63 65 73 28 70 6c <int> places(pl
1070: 61 63 65 73 5f 2c 20 70 6c 61 63 65 73 5f 2b 73 aces_, places_+s
1080: 69 7a 65 6f 66 28 70 6c 61 63 65 73 5f 29 2f 73 izeof(places_)/s
1090: 69 7a 65 6f 66 28 2a 70 6c 61 63 65 73 5f 29 29 izeof(*places_))
10a0: 3b 20 0d 0a 09 69 6e 74 20 63 75 74 6f 66 66 5f ; ...int cutoff_
10b0: 5b 5d 20 3d 20 7b 33 33 2c 34 30 2c 34 31 2c 34 [] = {33,40,41,4
10c0: 38 2c 37 34 2c 38 34 2c 31 31 37 2c 31 32 35 2c 8,74,84,117,125,
10d0: 31 32 36 2c 31 36 34 2c 31 39 37 2c 31 39 37 2c 126,164,197,197,
10e0: 32 30 31 2c 32 31 38 2c 32 32 32 2c 32 33 31 2c 201,218,222,231,
10f0: 32 34 34 2c 32 37 37 2c 32 39 30 2c 33 30 39 2c 244,277,290,309,
1100: 33 32 31 2c 33 32 31 2c 33 36 30 2c 33 37 36 2c 321,321,360,376,
1110: 34 34 30 2c 0d 0a 34 34 32 2c 34 36 35 2c 34 37 440,..442,465,47
1120: 37 2c 34 39 31 2c 35 31 33 2c 36 33 39 2c 36 34 7,491,513,639,64
1130: 35 2c 36 34 37 2c 36 37 35 2c 37 30 36 2c 37 31 5,647,675,706,71
1140: 30 2c 37 32 36 2c 37 33 36 2c 37 33 36 2c 37 36 0,726,736,736,76
1150: 35 2c 38 30 31 2c 38 33 38 2c 38 34 35 2c 38 35 5,801,838,845,85
1160: 34 2c 38 36 33 2c 38 36 35 2c 38 38 37 2c 39 30 4,863,865,887,90
1170: 32 2c 39 30 38 7d 3b 0d 0a 09 20 20 76 65 63 74 2,908};... vect
1180: 6f 72 20 3c 69 6e 74 3e 20 63 75 74 6f 66 66 28 or <int> cutoff(
1190: 63 75 74 6f 66 66 5f 2c 20 63 75 74 6f 66 66 5f cutoff_, cutoff_
11a0: 2b 73 69 7a 65 6f 66 28 63 75 74 6f 66 66 5f 29 +sizeof(cutoff_)
11b0: 2f 73 69 7a 65 6f 66 28 2a 63 75 74 6f 66 66 5f /sizeof(*cutoff_
11c0: 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 32 )); ...int _ = 2
11d0: 33 3b 20 0d 0a 45 4e 44 0d 0a 2f 2a 0d 0a 43 41 3; ..END../*..CA
11e0: 53 45 28 37 29 0d 0a 09 69 6e 74 20 70 6c 61 63 SE(7)...int plac
11f0: 65 73 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 es_[] = ;... ve
1200: 63 74 6f 72 20 3c 69 6e 74 3e 20 70 6c 61 63 65 ctor <int> place
1210: 73 28 70 6c 61 63 65 73 5f 2c 20 70 6c 61 63 65 s(places_, place
1220: 73 5f 2b 73 69 7a 65 6f 66 28 70 6c 61 63 65 73 s_+sizeof(places
1230: 5f 29 2f 73 69 7a 65 6f 66 28 2a 70 6c 61 63 65 _)/sizeof(*place
1240: 73 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 63 75 74 s_)); ...int cut
1250: 6f 66 66 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 off_[] = ;... v
1260: 65 63 74 6f 72 20 3c 69 6e 74 3e 20 63 75 74 6f ector <int> cuto
1270: 66 66 28 63 75 74 6f 66 66 5f 2c 20 63 75 74 6f ff(cutoff_, cuto
1280: 66 66 5f 2b 73 69 7a 65 6f 66 28 63 75 74 6f 66 ff_+sizeof(cutof
1290: 66 5f 29 2f 73 69 7a 65 6f 66 28 2a 63 75 74 6f f_)/sizeof(*cuto
12a0: 66 66 5f 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 ff_)); ...int _
12b0: 3d 20 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 = ; ..END..CASE(
12c0: 38 29 0d 0a 09 69 6e 74 20 70 6c 61 63 65 73 5f 8)...int places_
12d0: 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 6f [] = ;... vecto
12e0: 72 20 3c 69 6e 74 3e 20 70 6c 61 63 65 73 28 70 r <int> places(p
12f0: 6c 61 63 65 73 5f 2c 20 70 6c 61 63 65 73 5f 2b laces_, places_+
1300: 73 69 7a 65 6f 66 28 70 6c 61 63 65 73 5f 29 2f sizeof(places_)/
1310: 73 69 7a 65 6f 66 28 2a 70 6c 61 63 65 73 5f 29 sizeof(*places_)
1320: 29 3b 20 0d 0a 09 69 6e 74 20 63 75 74 6f 66 66 ); ...int cutoff
1330: 5f 5b 5d 20 3d 20 3b 0d 0a 09 20 20 76 65 63 74 _[] = ;... vect
1340: 6f 72 20 3c 69 6e 74 3e 20 63 75 74 6f 66 66 28 or <int> cutoff(
1350: 63 75 74 6f 66 66 5f 2c 20 63 75 74 6f 66 66 5f cutoff_, cutoff_
1360: 2b 73 69 7a 65 6f 66 28 63 75 74 6f 66 66 5f 29 +sizeof(cutoff_)
1370: 2f 73 69 7a 65 6f 66 28 2a 63 75 74 6f 66 66 5f /sizeof(*cutoff_
1380: 29 29 3b 20 0d 0a 09 69 6e 74 20 5f 20 3d 20 3b )); ...int _ = ;
1390: 20 0d 0a 45 4e 44 0d 0a 2a 2f 0d 0a 7d 0d 0a 2f ..END..*/..}../
13a0: 2f 20 45 4e 44 20 43 55 54 20 48 45 52 45 0d 0a / END CUT HERE..