Page 1 of 1
11384 - Help is needed for Dexter
Posted: Sat Jan 05, 2008 9:21 pm
by 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:
Posted: Sat Jan 05, 2008 9:28 pm
by rio
No. Its not correct.
For example, with n=7, need only 3 steps.
-----
Rio
Posted: Sat Jan 05, 2008 9:36 pm
by 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
Posted: Sat Jan 05, 2008 9:49 pm
by 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
problem description
Posted: Tue Jan 08, 2008 12:45 am
by ThanhNhan
Problem description is not up. Someone should fix this.
Posted: Tue Jan 08, 2008 1:33 am
by sonyckson
By the moment you can see it in the contest page...
http://icpcres.ecs.baylor.edu/onlinejud ... 11384.html
gl!.Eric.
Re: 11384 - Help is needed for Dexter
Posted: Sat May 10, 2008 9:36 pm
by yiuyuho
Hi. Can anyone proof for me that the optimal solution always only subtracts powers of 2 from the set of selected numbers?
Re: 11384 - Help is needed for Dexter
Posted: Mon Jun 02, 2008 10:52 am
by rio
yiuyuho wrote: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
Re: 11384 - Help is needed for Dexter
Posted: Sun Jul 10, 2011 7:54 pm
by 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
