Discussion @ 1876. Centipede's Morning @ Timus Online Judge

WA-1 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

Thanks.

Re: WA-1 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 Strekalovsky Oleg [Vologda SPU #1] 30 Oct 2011 19:19

My any Java solutions get's WA 1 too.

Re: WA-1 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 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 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 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 ganador 30 Apr 2012 02:42

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

Re: WA-1 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 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 Alina 18 May 2013 00:58

He wanted to wright 'We take 39 right'

Re: WA-1 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 phoenix16prep 22 Jan 2015 19:58

why 39 rights and no 40?

Re: WA-1 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.

Re: WA-1 Andre Marin 27 May 2023 02:52

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

Discussion of Problem 1876. Centipede's Morning