Is the following io generated correct? I'm getting wa. Thank you.
Input:
Code: Select all
6
7
15
16
100
1000
10000
1000000000
Code: Select all
3
4
5
6
14
45
141
44721
Moderator: Board moderators
Code: Select all
6
7
15
16
100
1000
10000
1000000000
Code: Select all
3
4
5
6
14
45
141
44721
Maybe, I'm not understanding the problem correctly, butNo. Its not correct.
For example, with n=7, need only 3 steps.
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
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
I think it could be proven with induction.yiuyuho wrote:Hi. Can anyone proof for me that the optimal solution always only subtracts powers of 2 from the set of selected numbers?