| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [алгоритм]Сороконожка |
| Автор: Merhaba 20.1.2012, 09:50 |
| Помогите Пожалуйста решить задачу! У сороконожки 40 левых ножек и 40 правых ножек. Под кроватью у сороконожки a левых тапочек и b правых тапочек. Сороконожка, просыпаясь, надевает тапочки. Для этого она засовывает под кровать первую левую ножку и надевает первый попавшийся тапочек, тратя на это одну секунду. Если тапочек оказывается левым, то она переходит ко второй левой ножке. Если же он оказывается правым, она переодевает его на какую-нибудь необутую правую ножку, тратя ещё одну секунду, то есть всего на такой тапочек уходит две секунды. Если все правые ножки уже обуты, то она снимает тапочек и кидает его в угол комнаты, тратя на это одну секунду, то есть на такой тапочек сороконожка тратит также две секунды. Процесс продолжается до тех пор, пока все левые ножки не окажутся в левых тапочках. Затем сороконожка аналогичным образом начинает надевать правые тапочки, продолжая до тех пор, пока не будут обуты все правые ножки. Сегодня сороконожка встала не с той ножки, поэтому она готовится к худшему. Несмотря на это, она, как обычно, начинает обуваться с левой ножки. Сколько секунд понадобится сороконожке на утреннее обувание? В единственной строке записаны целые числа a и b (40 ≤ a, b ≤ 100). Выведите, сколько секунд понадобится в худшем случае сороконожке на утреннее обувание. |
| Автор: Silent 20.1.2012, 13:05 |
| Есть всего два плохих случая когда: 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) Максимальная цифра и будет наихудшим вариантов, то есть ответом =) З.Ы. Если непонятно, почему именно эти два случая являются самыми плохими, то можно пытаться найти ответ динамическим программированием ))) |