ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1876. Centipede's Morning

Posted by watashi 30 Oct 2011 17:12
Hi, I'm still getting WA-1, can anybody give me answers to these tests:

80 60
60 80
60 60

Re: WA-1
Posted by SkorKNURE 30 Oct 2011 19:17
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]...
Re: WA-1
Posted by Strekalovsky Oleg [Vologda SPU #1] 30 Oct 2011 19:19
My any Java solutions get's WA 1 too.
Re: WA-1
Posted by Di 30 Oct 2011 19:59
i think it's problem with java, have same too. wa for any solution, which has got ac before.
Re: WA-1
Posted by watashi 31 Oct 2011 02:09
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
Re: WA-1
Posted by d3m0n1c 31 Oct 2011 02:20
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
Re: WA-1
Posted by ONU_1785 31 Oct 2011 03:38
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.
Re: WA-1
Posted by ganador 30 Apr 2012 02:42

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
Re: WA-1
Posted by Alexey Dergunov [Samara SAU] 3 May 2012 15:53
Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :)
Re: WA-1
Posted by OmarOthman 20 May 2012 15:53
ONU_1785 means 39 right, it's just a typo.

Edited by author 20.05.2012 15:54
Re: WA-1
Posted by gmous 8 Nov 2012 18:28

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
Re: WA-1
Posted by Alina 18 May 2013 00:58
He wanted to wright 'We take 39 right'
Re: WA-1
Posted by phoenix16prep 22 Jan 2015 19:58
why 39 rights and no 40?
Re: WA-1
Posted by Gefest 15 Apr 2019 07:42
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.