0000: 23 69 6e 63 6c 75 64 65 20 3c 69 6f 73 74 72 65 #include <iostre
0010: 61 6d 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 am>.#include <st
0020: 72 69 6e 67 3e 0a 23 69 6e 63 6c 75 64 65 20 3c ring>.#include <
0030: 6d 61 70 3e 0a 75 73 69 6e 67 20 6e 61 6d 65 73 map>.using names
0040: 70 61 63 65 20 73 74 64 3b 0a 0a 73 74 72 69 6e pace std;..strin
0050: 67 20 65 72 72 20 3d 20 22 32 32 32 32 32 32 32 g err = "2222222
0060: 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 2222222222222222
0070: 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 2222222222222222
0080: 32 32 32 32 32 32 32 32 32 22 3b 0a 0a 76 6f 69 222222222";..voi
0090: 64 20 6f 70 65 72 61 74 6f 72 26 3d 28 20 73 74 d operator&=( st
00a0: 72 69 6e 67 26 20 78 2c 20 63 6f 6e 73 74 20 73 ring& x, const s
00b0: 74 72 69 6e 67 26 20 72 20 29 0a 7b 0a 09 69 66 tring& r ).{..if
00c0: 28 20 78 2e 73 69 7a 65 28 29 20 3e 20 72 2e 73 ( x.size() > r.s
00d0: 69 7a 65 28 29 20 29 0a 09 09 78 20 3d 20 72 3b ize() )...x = r;
00e0: 0a 09 65 6c 73 65 20 69 66 28 20 78 2e 73 69 7a ..else if( x.siz
00f0: 65 28 29 3d 3d 72 2e 73 69 7a 65 28 29 20 26 26 e()==r.size() &&
0100: 20 78 20 3e 20 72 20 29 0a 09 09 78 20 3d 20 72 x > r )...x = r
0110: 3b 0a 7d 0a 0a 73 74 72 75 63 74 20 42 69 6e 61 ;.}..struct Bina
0120: 72 79 53 75 6d 0a 7b 0a 09 6d 61 70 3c 69 6e 74 rySum.{..map<int
0130: 2c 20 73 74 72 69 6e 67 3e 20 6d 65 6d 6f 3b 0a , string> memo;.
0140: 0a 09 69 6e 74 20 72 65 61 72 72 61 6e 67 65 28 ..int rearrange(
0150: 69 6e 74 20 61 2c 20 69 6e 74 20 62 2c 20 69 6e int a, int b, in
0160: 74 20 63 29 0a 09 7b 0a 09 09 69 6e 74 20 61 6e t c)..{...int an
0170: 3d 30 2c 62 6e 3d 30 2c 63 6e 3d 30 2c 6e 3d 30 =0,bn=0,cn=0,n=0
0180: 3b 0a 09 09 66 6f 72 28 75 6e 73 69 67 6e 65 64 ;...for(unsigned
0190: 20 69 6e 74 20 69 3d 31 2c 74 3d 31 3b 20 69 3c int i=1,t=1; i<
01a0: 3d 61 3b 20 69 3c 3c 3d 31 2c 2b 2b 74 29 20 7b =a; i<<=1,++t) {
01b0: 69 66 28 61 26 69 29 20 61 6e 2b 2b 3b 20 6e 3d if(a&i) an++; n=
01c0: 6d 61 78 3c 69 6e 74 3e 28 6e 2c 74 29 3b 7d 0a max<int>(n,t);}.
01d0: 09 09 66 6f 72 28 75 6e 73 69 67 6e 65 64 20 69 ..for(unsigned i
01e0: 6e 74 20 69 3d 31 2c 74 3d 31 3b 20 69 3c 3d 62 nt i=1,t=1; i<=b
01f0: 3b 20 69 3c 3c 3d 31 2c 2b 2b 74 29 20 7b 69 66 ; i<<=1,++t) {if
0200: 28 62 26 69 29 20 62 6e 2b 2b 3b 20 6e 3d 6d 61 (b&i) bn++; n=ma
0210: 78 3c 69 6e 74 3e 28 6e 2c 74 29 3b 7d 0a 09 09 x<int>(n,t);}...
0220: 66 6f 72 28 75 6e 73 69 67 6e 65 64 20 69 6e 74 for(unsigned int
0230: 20 69 3d 31 2c 74 3d 31 3b 20 69 3c 3d 63 3b 20 i=1,t=1; i<=c;
0240: 69 3c 3c 3d 31 2c 2b 2b 74 29 20 7b 69 66 28 63 i<<=1,++t) {if(c
0250: 26 69 29 20 63 6e 2b 2b 3b 20 6e 3d 6d 61 78 3c &i) cn++; n=max<
0260: 69 6e 74 3e 28 6e 2c 74 29 3b 7d 0a 09 09 73 74 int>(n,t);}...st
0270: 72 69 6e 67 20 61 6e 73 20 3d 20 65 72 72 3b 0a ring ans = err;.
0280: 09 09 61 6e 73 20 26 3d 20 6d 69 6e 69 28 20 30 ..ans &= mini( 0
0290: 2c 20 63 6e 2d 31 2c 20 61 6e 2d 31 2c 20 62 6e , cn-1, an-1, bn
02a0: 20 20 20 29 3b 20 2f 2f 20 31 2b 30 28 2b 30 29 ); // 1+0(+0)
02b0: 3d 30 31 0a 09 09 61 6e 73 20 26 3d 20 6d 69 6e =01...ans &= min
02c0: 69 28 20 30 2c 20 63 6e 2d 31 2c 20 61 6e 2c 20 i( 0, cn-1, an,
02d0: 20 20 62 6e 2d 31 20 29 3b 20 2f 2f 20 30 2b 31 bn-1 ); // 0+1
02e0: 28 2b 30 29 3d 30 31 0a 09 09 61 6e 73 20 26 3d (+0)=01...ans &=
02f0: 20 6d 69 6e 69 28 20 31 2c 20 63 6e 2d 31 2c 20 mini( 1, cn-1,
0300: 61 6e 2c 20 20 20 62 6e 20 29 3b 20 20 20 2f 2f an, bn ); //
0310: 20 30 2b 30 28 2b 31 29 3d 30 31 0a 09 09 69 66 0+0(+1)=01...if
0320: 28 20 61 6e 73 2e 66 69 6e 64 28 27 32 27 29 20 ( ans.find('2')
0330: 21 3d 20 73 74 72 69 6e 67 3a 3a 6e 70 6f 73 20 != string::npos
0340: 29 0a 09 09 09 72 65 74 75 72 6e 20 2d 31 3b 0a )....return -1;.
0350: 09 09 61 6e 73 20 3d 20 22 31 22 2b 61 6e 73 3b ..ans = "1"+ans;
0360: 0a 09 09 69 66 28 20 61 6e 73 2e 73 69 7a 65 28 ...if( ans.size(
0370: 29 20 3e 20 6e 20 29 0a 09 09 09 72 65 74 75 72 ) > n )....retur
0380: 6e 20 2d 31 3b 0a 09 09 69 6e 74 20 76 20 3d 20 n -1;...int v =
0390: 30 3b 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 0;...for(int i=0
03a0: 3b 20 69 3c 61 6e 73 2e 73 69 7a 65 28 29 3b 20 ; i<ans.size();
03b0: 2b 2b 69 29 0a 09 09 09 76 20 3d 20 28 76 3c 3c ++i)....v = (v<<
03c0: 31 29 20 7c 20 28 61 6e 73 5b 69 5d 20 2d 20 27 1) | (ans[i] - '
03d0: 30 27 29 3b 0a 09 09 72 65 74 75 72 6e 20 76 3b 0');...return v;
03e0: 0a 09 7d 0a 0a 09 73 74 72 69 6e 67 20 6d 69 6e ..}...string min
03f0: 69 28 69 6e 74 20 64 2c 20 69 6e 74 20 63 6e 2c i(int d, int cn,
0400: 20 69 6e 74 20 61 6e 2c 20 69 6e 74 20 62 6e 29 int an, int bn)
0410: 0a 09 7b 0a 09 09 69 66 28 20 63 6e 3c 30 20 7c ..{...if( cn<0 |
0420: 7c 20 61 6e 3c 30 20 7c 7c 20 62 6e 3c 30 20 29 | an<0 || bn<0 )
0430: 0a 09 09 09 72 65 74 75 72 6e 20 65 72 72 3b 0a ....return err;.
0440: 0a 09 09 69 6e 74 20 6b 65 79 20 3d 20 28 63 6e ...int key = (cn
0450: 3c 3c 32 34 29 2b 28 61 6e 3c 3c 31 36 29 2b 28 <<24)+(an<<16)+(
0460: 62 6e 3c 3c 38 29 2b 64 3b 0a 09 09 69 66 28 20 bn<<8)+d;...if(
0470: 6d 65 6d 6f 2e 63 6f 75 6e 74 28 6b 65 79 29 20 memo.count(key)
0480: 29 0a 09 09 09 72 65 74 75 72 6e 20 6d 65 6d 6f )....return memo
0490: 5b 6b 65 79 5d 3b 0a 0a 09 09 69 66 28 20 64 3d [key];....if( d=
04a0: 3d 30 20 26 26 20 63 6e 3d 3d 30 20 26 26 20 61 =0 && cn==0 && a
04b0: 6e 3d 3d 30 20 26 26 20 62 6e 3d 3d 30 20 29 0a n==0 && bn==0 ).
04c0: 09 09 09 72 65 74 75 72 6e 20 22 22 3b 0a 0a 09 ...return "";...
04d0: 09 73 74 72 69 6e 67 20 61 6e 73 20 3d 20 65 72 .string ans = er
04e0: 72 3b 0a 09 09 69 66 28 20 64 20 3d 3d 20 30 20 r;...if( d == 0
04f0: 29 20 7b 0a 09 09 09 61 6e 73 20 26 3d 20 22 31 ) {....ans &= "1
0500: 22 2b 6d 69 6e 69 28 20 30 2c 20 63 6e 2d 31 2c "+mini( 0, cn-1,
0510: 20 61 6e 2d 31 2c 20 62 6e 20 29 3b 20 2f 2f 20 an-1, bn ); //
0520: 31 2b 30 28 2b 30 29 3d 30 31 0a 09 09 09 61 6e 1+0(+0)=01....an
0530: 73 20 26 3d 20 22 31 22 2b 6d 69 6e 69 28 20 30 s &= "1"+mini( 0
0540: 2c 20 63 6e 2d 31 2c 20 61 6e 2c 20 62 6e 2d 31 , cn-1, an, bn-1
0550: 20 29 3b 20 2f 2f 20 30 2b 31 28 2b 30 29 3d 30 ); // 0+1(+0)=0
0560: 31 0a 09 09 09 61 6e 73 20 26 3d 20 22 31 22 2b 1....ans &= "1"+
0570: 6d 69 6e 69 28 20 31 2c 20 63 6e 2d 31 2c 20 61 mini( 1, cn-1, a
0580: 6e 2c 20 62 6e 20 29 3b 20 20 20 2f 2f 20 30 2b n, bn ); // 0+
0590: 30 28 2b 31 29 3d 30 31 0a 09 09 7d 20 65 6c 73 0(+1)=01...} els
05a0: 65 20 7b 0a 09 09 09 61 6e 73 20 26 3d 20 22 30 e {....ans &= "0
05b0: 22 2b 6d 69 6e 69 28 20 30 2c 20 63 6e 2c 20 61 "+mini( 0, cn, a
05c0: 6e 2d 31 2c 20 62 6e 2d 31 20 29 3b 20 2f 2f 20 n-1, bn-1 ); //
05d0: 31 2b 31 28 2b 30 29 3d 31 30 0a 09 09 09 61 6e 1+1(+0)=10....an
05e0: 73 20 26 3d 20 22 30 22 2b 6d 69 6e 69 28 20 31 s &= "0"+mini( 1
05f0: 2c 20 63 6e 2c 20 61 6e 2d 31 2c 20 62 6e 20 29 , cn, an-1, bn )
0600: 3b 20 20 20 2f 2f 20 31 2b 30 28 2b 31 29 3d 31 ; // 1+0(+1)=1
0610: 30 0a 09 09 09 61 6e 73 20 26 3d 20 22 30 22 2b 0....ans &= "0"+
0620: 6d 69 6e 69 28 20 31 2c 20 63 6e 2c 20 61 6e 2c mini( 1, cn, an,
0630: 20 62 6e 2d 31 20 29 3b 20 20 20 20 2f 2f 20 30 bn-1 ); // 0
0640: 2b 31 28 2b 31 29 3d 31 30 0a 09 09 09 61 6e 73 +1(+1)=10....ans
0650: 20 26 3d 20 22 31 22 2b 6d 69 6e 69 28 20 31 2c &= "1"+mini( 1,
0660: 20 63 6e 2d 31 2c 20 61 6e 2d 31 2c 20 62 6e 2d cn-1, an-1, bn-
0670: 31 20 29 3b 20 2f 2f 20 31 2b 31 28 2b 31 29 3d 1 ); // 1+1(+1)=
0680: 31 31 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 11...}...return
0690: 6d 65 6d 6f 5b 6b 65 79 5d 20 3d 20 61 6e 73 3b memo[key] = ans;
06a0: 0a 09 7d 0a 7d 3b 0a ..}.};.