ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1876. Утро сороконожки

WA-1
Послано watashi 30 окт 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 окт 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 окт 2011 19:19
My any Java solutions get's WA 1 too.
Re: WA-1
Послано Di 30 окт 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 окт 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 окт 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 окт 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 апр 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
Послано Alexey Dergunov [Samara SAU] 3 май 2012 15:53
Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :)
Re: WA-1
Послано OmarOthman 20 май 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 ноя 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 май 2013 00:58
He wanted to wright 'We take 39 right'
Re: WA-1
Послано phoenix16prep 22 янв 2015 19:58
why 39 rights and no 40?
Re: WA-1
Послано Gefest 15 апр 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.