SRM399 BinarySum

2019年04月15日 ⁄ 综合 ⁄ 共 2038字 ⁄ 字号 评论关闭

Problem Statement

You are given three integers: a, b and c. Convert each of them into their binary representations with no leading zeroes. Let x be the number of binary digits in the longest of the three. Add leading zeroes to the others until all of them have exactly x digits.

Transform a, b and c into a', b' and c', such that a'+b'=c', by optionally reordering the digits within each number. Leading zeroes are allowed. If there are several ways to do this, use the one that minimizes c'.

For example, let a = 7, b = 6 and c = 9. In binary notation, a = 111, b = 110 and c = 1001. We add leading zeroes to a and b so that all of them have exactly four digits: a = 0111, b = 0110, c = 1001. Now, if we reorder the digits within each number to get a' = 0111, b' = 0011 and c' = 1010, we satisfy a' + b' = c' (7 + 3 = 10). There is another way to do this as well (7 + 5 = 12), but this is the way that minimizes c'.

You are given ints a, b and c. Return the minimal possible value of c'. If there is no solution, return -1.

abc(binary)中1的个数固定，求a+b=c组合中c的最小值。

```#define INF  (1e60)
#define MAX  (1 << 29)
#define MIN  (-MAX)
#define INFLL   (10000000000LL)
#define MAX_N   (15)
#define min(x, y) ( x < y ? x : y )
#define max(x, y) ( x > y ? x : y )
#define rep(i, n) for ( i = 0; i < n; i ++ )
typedef long long LL;

class BinarySum
{
LL dp[32][32][32][32][2];
int ones ( int n )
{
return ( n > 0 ? ( n & 1 ) + ones ( n >> 1 ) : 0 );
}
int digit ( int n )
{
return ( n > 0 ? 1 + digit ( n >> 1 ) : 0 );
}
LL get ( int n, int a, int b, int c, int p )
{
if ( a < 0 || a > n )
return INFLL;
if ( b < 0 || b > n )
return INFLL;
if ( c < 0 || c > n )
return INFLL;
LL &res = dp[n][a][b][c][p];
if ( res != -1 )
return res;
res = INFLL;
if ( n == 0 )
{
if ( a == 0 && b == 0 && c == 0 && p == 0 )
res = 0;
else
res = INFLL;
//printf ( "%d %d %d %d %d %lld/n", n, a, b, c, p, res );
return res;
}
int i, j, k;
rep ( i, 2 ) rep ( j, 2 )
{
k = i + j + p;
LL temp = get ( n - 1, a - i, b - j, c - ( k & 1 ), k >> 1 );
temp = temp * 2 + ( k & 1 );
res = min ( res, temp );
}
//printf ( "%d %d %d %d %d %lld/n", n, a, b, c, p, res );
return res;
}
public:
int rearrange ( int a, int b, int c )
{
int la, lb, lc;
la = ones ( a ), lb = ones ( b ), lc = ones ( c );
int l = max ( max ( digit ( a ), digit ( b ) ), digit ( c ) );
memset ( dp, 0xff, sizeof ( dp ) );
LL res = get ( l, la, lb, lc, 0 );
if ( res == INFLL )
return -1;
else
return int ( res );
}
};
```
` `