WA-1
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
Thanks.
Re: WA-1
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
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
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
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
Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :)
Re: WA-1
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
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.
Re: WA-1
you have 60 and 80, from where you take 39?