11384 - Help is needed for Dexter

[zuluaga]

Hi,

Is the following io generated correct? I'm getting wa. Thank you.

Input:

Code: Select all

6
7
15
16
100
1000
10000
1000000000

Output:

Code: Select all

3
4
5
6
14
45
141
44721

[rio]

No. Its not correct.
For example, with n=7, need only 3 steps.

-----
Rio

[zuluaga]

No. Its not correct.
For example, with n=7, need only 3 steps.

Maybe, I'm not understanding the problem correctly, but
in my interpretation, 7 requires 4 steps, because 7-3=4,
and 4 requires 3 steps. I interpret it as you can subtract
a maximum of L, to get L moves.

This is one of the optimal sequence.. (subtract 3, then we need 4 steps, so L=4).

Code: Select all

1 2 3 4 5 6 7
1 2 0 1 2 3 4
1 2 0 1 2 0 1
0 1 0 0 1 0 0
0 0 0 0 0 0 0

[rio]

This is the optimal move for n=7.

Code: Select all

1 2 3 4 5 6 7
1 2 3 0 1 2 3
1 0 1 0 1 0 1
0 0 0 0 0 0 0

-----
Rio

[ThanhNhan]

Problem description is not up. Someone should fix this.

[sonyckson]

By the moment you can see it in the contest page... http://icpcres.ecs.baylor.edu/onlinejud ... 11384.html
gl!.Eric.

[yiuyuho]

Hi. Can anyone proof for me that the optimal solution always only subtracts powers of 2 from the set of selected numbers?

[rio]

Hi. Can anyone proof for me that the optimal solution always only subtracts powers of 2 from the set of selected numbers?

I think it could be proven with induction.

-----
Rio

[plamplam]

Awesome problem lol.....I found out all the minimum moves from 1 to 16 on paper first , may be this is not the way to solve this problem, but I like do it in my way. Nice recurrence relation. Thanks to the problem setter