 |
|
Модераторы: Poseidon |
 
|
|
[алгоритм]Сороконожка 
| Merhaba |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 93 Регистрация: 23.4.2011 Репутация: нет Всего: нет |
Помогите Пожалуйста решить задачу!
У сороконожки 40 левых ножек и 40 правых ножек. Под кроватью у сороконожки a левых тапочек и b правых тапочек. Сороконожка, просыпаясь, надевает тапочки. Для этого она засовывает под кровать первую левую ножку и надевает первый попавшийся тапочек, тратя на это одну секунду. Если тапочек оказывается левым, то она переходит ко второй левой ножке. Если же он оказывается правым, она переодевает его на какую-нибудь необутую правую ножку, тратя ещё одну секунду, то есть всего на такой тапочек уходит две секунды. Если все правые ножки уже обуты, то она снимает тапочек и кидает его в угол комнаты, тратя на это одну секунду, то есть на такой тапочек сороконожка тратит также две секунды. Процесс продолжается до тех пор, пока все левые ножки не окажутся в левых тапочках. Затем сороконожка аналогичным образом начинает надевать правые тапочки, продолжая до тех пор, пока не будут обуты все правые ножки. Сегодня сороконожка встала не с той ножки, поэтому она готовится к худшему. Несмотря на это, она, как обычно, начинает обуваться с левой ножки. Сколько секунд понадобится сороконожке на утреннее обувание? В единственной строке записаны целые числа a и b (40 ≤ a, b ≤ 100). Выведите, сколько секунд понадобится в худшем случае сороконожке на утреннее обувание. |
|||
|
||||
Загрузка ...
| Silent |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 252 Регистрация: 3.10.2006 Репутация: 6 Всего: 9 |
Есть всего два плохих случая когда:
1) сначала идет 40 правых тапок, на которые тратятся по две секунды на тапок, потом идут еще b-40 правых тапочек, на которые также тратится по две секунды на тапок, а затем одевается 40 левых тапочек - итоговая формула 40*2+(b-40)*2+40 сек. Упрощаем: 120+2*(b-40) 2) сначала идет 39 правых тапочек (2 сек/тапка), потом все левые (40 нужных по 1 сек/тапка, и остальные по 2 сек/тапка), и последняя оставшаяся правая, 1 сек/тапка (ибо левые уже одеты все и под кровать лезем нужной правой ножкой). формула: 39*2+40+2*(a-40)+1. Упрощаем: 119+2*(a-40) Максимальная цифра и будет наихудшим вариантов, то есть ответом =) З.Ы. Если непонятно, почему именно эти два случая являются самыми плохими, то можно пытаться найти ответ динамическим программированием ))) |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0686 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |