Hi, I'm still getting WA-1, can anybody give me answers to these tests:

80 60
60 80
60 60

Thanks.

My AC program writes following answers:

80 60 >> 199
60 80 >> 200
60 60 >> 160

BTW I solved this problem without any boring special cases consideration, using only stupid DP[101][101]...

My any Java solutions get's WA 1 too.

i think it's problem with java, have same too. wa for any solution, which has got ac before.

I saw DP[101][101], is it for dynamic programming ?
I don't think we'll need it.

Edited by author 31.10.2011 02:12

in this problem dont need DP.
you may take max from two optimal cases ;D

...or think how to make on DP

Edited by author 31.10.2011 02:21

80 60     199
60 80     200
60 60     160

Its quite easy to do.
Basically, there are 2 "worst" cases:
1). We take 40 right (equals 40*2=80 secs), then throw all the rest of the right ones (2*(b-40) secs), and them take the 40 left (40 secs). The time is 80+2*(b-40)+40=120+2*(b-40).
2). We take 39 left (78 secs), take 40 left ones (40 secs), throw all the other left ones away (2*(a-40)), and take the last right one (1 sec). The time is 78+40+2*(a-40)+1=119+2*(a-40).

The answer is the maximum of these two.

ONU_1785

In the case two, when you say: "We take 39 left (78 secs)", why?
If I take the first 39 lefts, this not is 39 secs???? one second per each slipper

Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :)

ONU_1785 means 39 right, it's just a typo.

Edited by author 20.05.2012 15:54

In the case two, when you say: "We take 39 left (78 secs)", why?
If I take the first 39 lefts, this not is 39 secs???? one second per each slipper

He wanted to wright 'We take 39 right'

why 39 rights and no 40?

There are 2 possible bad ways:

1) mode "putting on left slippers" |*0*|0|
   slippers come only for right legs |*0*|40| (time +40*2)
   if there are more than 40 slippers for right legs
      they still come  |*0*|40| (time + (b-40)*2)
   then there are slippers only for left legs |*40*|40| (time +40);

2) mode "putting on left slippers" |*0*|0|
   slippers come for right legs except 1 |*0*|39| (time +39*2)
   then slippers come only for left legs |*40*|39| (time +40)

   now mode changes to "putting on right slippers" |40|*39*|
   happy centipede hopes to get the last needed right slipper,
   she gets all slippers for left legs, which are still left |40|*39*| (time + (a-40)*2)
   and finally she gets the last one right slipper |40|*40*| (time +1)

So, just choose the worst way according to exact input.

you have 60  and 80, from where you take 39?