11532 - Simple Adjacency Maximization

[saiful_sust]

I try to solve this problem
But i get WA.......
can any one help me????????

Code: Select all

CUT after acc..........................

[helloneo]

Try some test cases..

Code: Select all

6
0 1
1 0
5 1
1 5
7 2
2 7

My output is..

Code: Select all

0
1
47
1
367
5

[saiful_sust]

Thanks helloneo
now i can solve it........

[f74956227]

I think this problem can be solved by using DP, but i can't find the recursive relationship...
could someone give me a hint?

[helloneo]

I think this problem can be solved by using DP, but i can't find the recursive relationship...
could someone give me a hint?

I didn't solve this problem with DP.. Just try to find a pattern..
If there are enough '0's, the best representation would be like this..

...000000101101101101

If there are not enough '0's, you have to insert '0' in smarter way..

[f74956227]

I got AC!!! It is just a simple simulation problem Thank!

[aliahmed]

ACC
It was wrong for 3 1

[helloneo]

I think you might get a precision error here..

Code: Select all

			sum+=pow(2,q);

Do not use floating point operation

Remove your code after AC

[tryit1]

The number of 1s adjacent to one or more 0 in the binary representation is maximized.

What does this mean ? Why isn't 0101011 (43) better than 0101101 (45) in case of 4 3 .

Also i don't understand in case 3 2 , why is it 1101 (13) instead of 10101(21) ?

[helloneo]

43 -> 0101011 has three '1's which are adjacent to '0'
45 -> 0101101 has four '1's which are adjacent to '0'
So, 45 is better than 43

For input
3 2

1101 and 10101 both have three '1's adjacent to '0'
But, problem statements say that

Find the smallest integer N ..

So, the answer would be 13 (1101)