Artifact 34827d4e4ac8d217cd082419de6ccac314429340:
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 63 6c 61 73 73 20 43 6f CMP;....class Co
01a0: 72 72 65 63 74 4d 75 6c 74 69 70 6c 69 63 61 74 rrectMultiplicat
01b0: 69 6f 6e 20 7b 20 70 75 62 6c 69 63 3a 0d 0a 09 ion { public:...
01c0: 6c 6f 6e 67 20 6c 6f 6e 67 20 67 65 74 4d 69 6e long long getMin
01d0: 69 6d 75 6d 28 69 6e 74 20 61 2c 20 69 6e 74 20 imum(int a, int
01e0: 62 2c 20 69 6e 74 20 63 29 0d 0a 09 7b 0d 0a 09 b, int c)...{...
01f0: 09 72 65 74 75 72 6e 20 73 6f 6c 76 65 28 61 2c .return solve(a,
0200: 62 2c 63 29 3b 0d 0a 09 7d 0d 0a 0d 0a 09 4c 4c b,c);...}.....LL
0210: 20 73 6f 6c 76 65 28 4c 4c 20 61 2c 20 4c 4c 20 solve(LL a, LL
0220: 62 2c 20 4c 4c 20 63 29 0d 0a 09 7b 0d 0a 09 09 b, LL c)...{....
0230: 69 66 28 20 61 20 3e 20 62 20 29 0d 0a 09 09 09 if( a > b ).....
0240: 73 77 61 70 28 61 2c 62 29 3b 0d 0a 09 09 4c 4c swap(a,b);....LL
0250: 20 76 76 20 3d 20 28 31 4c 4c 3c 3c 36 32 29 3b vv = (1LL<<62);
0260: 0d 0a 09 09 66 6f 72 28 4c 4c 20 41 3d 31 3b 20 ....for(LL A=1;
0270: 41 2a 41 20 3c 3d 20 28 61 2b 62 2b 63 29 2a 32 A*A <= (a+b+c)*2
0280: 3b 20 2b 2b 41 29 0d 0a 09 09 09 76 76 20 3d 20 ; ++A).....vv =
0290: 6d 69 6e 28 76 76 2c 20 62 65 73 74 5f 6f 66 28 min(vv, best_of(
02a0: 41 2c 61 2c 62 2c 63 29 29 3b 0d 0a 09 09 72 65 A,a,b,c));....re
02b0: 74 75 72 6e 20 76 76 3b 0d 0a 09 7d 0d 0a 0d 0a turn vv;...}....
02c0: 09 4c 4c 20 62 65 73 74 5f 6f 66 28 4c 4c 20 41 .LL best_of(LL A
02d0: 2c 20 4c 4c 20 61 2c 20 4c 4c 20 62 2c 20 4c 4c , LL a, LL b, LL
02e0: 20 63 29 0d 0a 09 7b 0d 0a 09 09 4c 4c 20 42 6c c)...{....LL Bl
02f0: 20 3d 20 31 3b 0d 0a 09 09 4c 4c 20 42 72 20 3d = 1;....LL Br =
0300: 20 61 2b 62 2b 63 3b 0d 0a 09 09 77 68 69 6c 65 a+b+c;....while
0310: 28 20 42 6c 2b 33 20 3c 20 42 72 20 29 0d 0a 09 ( Bl+3 < Br )...
0320: 09 7b 0d 0a 09 09 09 4c 4c 20 42 63 31 20 3d 20 .{.....LL Bc1 =
0330: 28 42 6c 2a 32 2b 42 72 2a 31 29 20 2f 20 33 3b (Bl*2+Br*1) / 3;
0340: 0d 0a 09 09 09 4c 4c 20 42 63 32 20 3d 20 28 42 .....LL Bc2 = (B
0350: 6c 2a 31 2b 42 72 2a 32 29 20 2f 20 33 3b 0d 0a l*1+Br*2) / 3;..
0360: 09 09 09 4c 4c 20 63 63 31 20 3d 20 61 62 73 28 ...LL cc1 = abs(
0370: 41 2d 61 29 2b 61 62 73 28 42 63 31 2d 62 29 2b A-a)+abs(Bc1-b)+
0380: 61 62 73 28 41 2a 42 63 31 2d 63 29 3b 0d 0a 09 abs(A*Bc1-c);...
0390: 09 09 4c 4c 20 63 63 32 20 3d 20 61 62 73 28 41 ..LL cc2 = abs(A
03a0: 2d 61 29 2b 61 62 73 28 42 63 32 2d 62 29 2b 61 -a)+abs(Bc2-b)+a
03b0: 62 73 28 41 2a 42 63 32 2d 63 29 3b 0d 0a 09 09 bs(A*Bc2-c);....
03c0: 09 69 66 28 63 63 31 20 3c 20 63 63 32 29 0d 0a .if(cc1 < cc2)..
03d0: 09 09 09 09 42 72 20 3d 20 42 63 32 3b 0d 0a 09 ....Br = Bc2;...
03e0: 09 09 65 6c 73 65 0d 0a 09 09 09 09 42 6c 20 3d ..else......Bl =
03f0: 20 42 63 31 3b 0d 0a 09 09 7d 0d 0a 09 09 4c 4c Bc1;....}....LL
0400: 20 76 76 20 3d 20 28 31 4c 4c 3c 3c 36 32 29 3b vv = (1LL<<62);
0410: 0d 0a 09 09 66 6f 72 28 4c 4c 20 42 3d 42 6c 3b ....for(LL B=Bl;
0420: 20 42 3c 3d 42 72 3b 20 2b 2b 42 29 0d 0a 09 09 B<=Br; ++B)....
0430: 09 76 76 20 3d 20 6d 69 6e 28 76 76 2c 20 61 62 .vv = min(vv, ab
0440: 73 28 41 2d 61 29 2b 61 62 73 28 42 2d 62 29 2b s(A-a)+abs(B-b)+
0450: 61 62 73 28 41 2a 42 2d 63 29 29 3b 0d 0a 09 09 abs(A*B-c));....
0460: 72 65 74 75 72 6e 20 76 76 3b 0d 0a 09 7d 0d 0a return vv;...}..
0470: 7d 3b 0d 0a 0d 0a 2f 2f 20 42 45 47 49 4e 20 43 };....// BEGIN C
0480: 55 54 20 48 45 52 45 0d 0a 23 69 6e 63 6c 75 64 UT HERE..#includ
0490: 65 20 3c 63 74 69 6d 65 3e 0d 0a 64 6f 75 62 6c e <ctime>..doubl
04a0: 65 20 73 74 61 72 74 5f 74 69 6d 65 3b 20 73 74 e start_time; st
04b0: 72 69 6e 67 20 74 69 6d 65 72 28 29 0d 0a 20 7b ring timer().. {
04c0: 20 6f 73 74 72 69 6e 67 73 74 72 65 61 6d 20 6f ostringstream o
04d0: 73 3b 20 6f 73 20 3c 3c 20 22 20 28 22 20 3c 3c s; os << " (" <<
04e0: 20 69 6e 74 28 28 63 6c 6f 63 6b 28 29 2d 73 74 int((clock()-st
04f0: 61 72 74 5f 74 69 6d 65 29 2f 43 4c 4f 43 4b 53 art_time)/CLOCKS
0500: 5f 50 45 52 5f 53 45 43 2a 31 30 30 30 29 20 3c _PER_SEC*1000) <
0510: 3c 20 22 20 6d 73 65 63 29 22 3b 20 72 65 74 75 < " msec)"; retu
0520: 72 6e 20 6f 73 2e 73 74 72 28 29 3b 20 7d 0d 0a rn os.str(); }..
0530: 74 65 6d 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d template<typenam
0540: 65 20 54 3e 20 6f 73 74 72 65 61 6d 26 20 6f 70 e T> ostream& op
0550: 65 72 61 74 6f 72 3c 3c 28 6f 73 74 72 65 61 6d erator<<(ostream
0560: 26 20 6f 73 2c 20 63 6f 6e 73 74 20 76 65 63 74 & os, const vect
0570: 6f 72 3c 54 3e 26 20 76 29 0d 0a 20 7b 20 6f 73 or<T>& v).. { os
0580: 20 3c 3c 20 22 7b 20 22 3b 0d 0a 20 20 20 66 6f << "{ ";.. fo
0590: 72 28 74 79 70 65 6e 61 6d 65 20 76 65 63 74 6f r(typename vecto
05a0: 72 3c 54 3e 3a 3a 63 6f 6e 73 74 5f 69 74 65 72 r<T>::const_iter
05b0: 61 74 6f 72 20 69 74 3d 76 2e 62 65 67 69 6e 28 ator it=v.begin(
05c0: 29 3b 20 69 74 21 3d 76 2e 65 6e 64 28 29 3b 20 ); it!=v.end();
05d0: 2b 2b 69 74 29 0d 0a 20 20 20 6f 73 20 3c 3c 20 ++it).. os <<
05e0: 27 5c 22 27 20 3c 3c 20 2a 69 74 20 3c 3c 20 27 '\"' << *it << '
05f0: 5c 22 27 20 3c 3c 20 28 69 74 2b 31 3d 3d 76 2e \"' << (it+1==v.
0600: 65 6e 64 28 29 20 3f 20 22 22 20 3a 20 22 2c 20 end() ? "" : ",
0610: 22 29 3b 20 6f 73 20 3c 3c 20 22 20 7d 22 3b 20 "); os << " }";
0620: 72 65 74 75 72 6e 20 6f 73 3b 20 7d 0d 0a 76 6f return os; }..vo
0630: 69 64 20 76 65 72 69 66 79 5f 63 61 73 65 28 63 id verify_case(c
0640: 6f 6e 73 74 20 6c 6f 6e 67 20 6c 6f 6e 67 26 20 onst long long&
0650: 45 78 70 65 63 74 65 64 2c 20 63 6f 6e 73 74 20 Expected, const
0660: 6c 6f 6e 67 20 6c 6f 6e 67 26 20 52 65 63 65 69 long long& Recei
0670: 76 65 64 29 20 7b 0d 0a 20 62 6f 6f 6c 20 6f 6b ved) {.. bool ok
0680: 20 3d 20 28 45 78 70 65 63 74 65 64 20 3d 3d 20 = (Expected ==
0690: 52 65 63 65 69 76 65 64 29 3b 0d 0a 20 69 66 28 Received);.. if(
06a0: 6f 6b 29 20 63 65 72 72 20 3c 3c 20 22 50 41 53 ok) cerr << "PAS
06b0: 53 45 44 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 SED" << timer()
06c0: 3c 3c 20 65 6e 64 6c 3b 20 20 65 6c 73 65 20 7b << endl; else {
06d0: 20 63 65 72 72 20 3c 3c 20 22 46 41 49 4c 45 44 cerr << "FAILED
06e0: 22 20 3c 3c 20 74 69 6d 65 72 28 29 20 3c 3c 20 " << timer() <<
06f0: 65 6e 64 6c 3b 0d 0a 20 63 65 72 72 20 3c 3c 20 endl;.. cerr <<
0700: 22 5c 74 6f 3a 20 5c 22 22 20 3c 3c 20 45 78 70 "\to: \"" << Exp
0710: 65 63 74 65 64 20 3c 3c 20 27 5c 22 27 20 3c 3c ected << '\"' <<
0720: 20 65 6e 64 6c 20 3c 3c 20 22 5c 74 78 3a 20 5c endl << "\tx: \
0730: 22 22 20 3c 3c 20 52 65 63 65 69 76 65 64 20 3c "" << Received <
0740: 3c 20 27 5c 22 27 20 3c 3c 20 65 6e 64 6c 3b 20 < '\"' << endl;
0750: 7d 20 7d 0d 0a 23 64 65 66 69 6e 65 20 43 41 53 } }..#define CAS
0760: 45 28 4e 29 20 7b 63 65 72 72 20 3c 3c 20 22 54 E(N) {cerr << "T
0770: 65 73 74 20 43 61 73 65 20 23 22 20 3c 3c 20 4e est Case #" << N
0780: 20 3c 3c 20 22 2e 2e 2e 22 20 3c 3c 20 66 6c 75 << "..." << flu
0790: 73 68 3b 20 73 74 61 72 74 5f 74 69 6d 65 3d 63 sh; start_time=c
07a0: 6c 6f 63 6b 28 29 3b 0d 0a 23 64 65 66 69 6e 65 lock();..#define
07b0: 20 45 4e 44 09 20 76 65 72 69 66 79 5f 63 61 73 END. verify_cas
07c0: 65 28 5f 2c 20 43 6f 72 72 65 63 74 4d 75 6c 74 e(_, CorrectMult
07d0: 69 70 6c 69 63 61 74 69 6f 6e 28 29 2e 67 65 74 iplication().get
07e0: 4d 69 6e 69 6d 75 6d 28 61 2c 20 62 2c 20 63 29 Minimum(a, b, c)
07f0: 29 3b 7d 0d 0a 69 6e 74 20 6d 61 69 6e 28 29 7b );}..int main(){
0800: 0d 0a 0d 0a 43 41 53 45 28 30 29 0d 0a 09 69 6e ....CASE(0)...in
0810: 74 20 61 20 3d 20 31 39 3b 20 0d 0a 09 69 6e 74 t a = 19; ...int
0820: 20 62 20 3d 20 32 38 3b 20 0d 0a 09 69 6e 74 20 b = 28; ...int
0830: 63 20 3d 20 35 32 32 3b 20 0d 0a 09 6c 6f 6e 67 c = 522; ...long
0840: 20 6c 6f 6e 67 20 5f 20 3d 20 32 4c 4c 3b 20 0d long _ = 2LL; .
0850: 0a 45 4e 44 0d 0a 43 41 53 45 28 31 29 0d 0a 09 .END..CASE(1)...
0860: 69 6e 74 20 61 20 3d 20 31 30 3b 20 0d 0a 09 69 int a = 10; ...i
0870: 6e 74 20 62 20 3d 20 33 30 3b 20 0d 0a 09 69 6e nt b = 30; ...in
0880: 74 20 63 20 3d 20 35 30 30 3b 20 0d 0a 09 6c 6f t c = 500; ...lo
0890: 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 31 4c 4c ng long _ = 11LL
08a0: 3b 20 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 32 29 ; ..END..CASE(2)
08b0: 0d 0a 09 69 6e 74 20 61 20 3d 20 31 31 31 31 31 ...int a = 11111
08c0: 3b 20 0d 0a 09 69 6e 74 20 62 20 3d 20 31 31 31 ; ...int b = 111
08d0: 31 31 3b 20 0d 0a 09 69 6e 74 20 63 20 3d 20 31 11; ...int c = 1
08e0: 32 33 34 35 34 33 32 31 3b 20 0d 0a 09 6c 6f 6e 23454321; ...lon
08f0: 67 20 6c 6f 6e 67 20 5f 20 3d 20 30 4c 4c 3b 20 g long _ = 0LL;
0900: 0d 0a 45 4e 44 0d 0a 43 41 53 45 28 33 29 0d 0a ..END..CASE(3)..
0910: 09 69 6e 74 20 61 20 3d 20 31 30 30 30 3b 20 0d .int a = 1000; .
0920: 0a 09 69 6e 74 20 62 20 3d 20 31 30 30 3b 20 0d ..int b = 100; .
0930: 0a 09 69 6e 74 20 63 20 3d 20 31 30 3b 20 0d 0a ..int c = 10; ..
0940: 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f 20 3d 20 31 .long long _ = 1
0950: 30 38 39 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 43 41 089LL; ..END..CA
0960: 53 45 28 34 29 0d 0a 09 69 6e 74 20 61 20 3d 20 SE(4)...int a =
0970: 33 39 39 3b 20 0d 0a 09 69 6e 74 20 62 20 3d 20 399; ...int b =
0980: 35 32 32 3b 20 0d 0a 09 69 6e 74 20 63 20 3d 20 522; ...int c =
0990: 31 39 39 39 39 39 3b 20 0d 0a 09 6c 6f 6e 67 20 199999; ...long
09a0: 6c 6f 6e 67 20 5f 20 3d 20 32 34 4c 4c 3b 20 0d long _ = 24LL; .
09b0: 0a 45 4e 44 0d 0a 43 41 53 45 28 35 29 0d 0a 09 .END..CASE(5)...
09c0: 69 6e 74 20 61 20 3d 20 31 30 30 30 30 30 30 30 int a = 10000000
09d0: 30 30 3b 20 0d 0a 09 69 6e 74 20 62 20 3d 20 31 00; ...int b = 1
09e0: 30 30 30 30 30 30 30 30 30 3b 20 0d 0a 09 69 6e 000000000; ...in
09f0: 74 20 63 20 3d 20 31 30 30 30 30 30 30 30 30 30 t c = 1000000000
0a00: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f ; ...long long _
0a10: 20 3d 20 2d 31 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a = -1LL; ..END..
0a20: 2f 2a 0d 0a 43 41 53 45 28 36 29 0d 0a 09 69 6e /*..CASE(6)...in
0a30: 74 20 61 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 62 t a = ; ...int b
0a40: 20 3d 20 3b 20 0d 0a 09 69 6e 74 20 63 20 3d 20 = ; ...int c =
0a50: 3b 20 0d 0a 09 6c 6f 6e 67 20 6c 6f 6e 67 20 5f ; ...long long _
0a60: 20 3d 20 4c 4c 3b 20 0d 0a 45 4e 44 0d 0a 2a 2f = LL; ..END..*/
0a70: 0d 0a 7d 0d 0a 2f 2f 20 45 4e 44 20 43 55 54 20 ..}..// END CUT
0a80: 48 45 52 45 0d 0a HERE..