LINUX.ORG.RU

Алгоритм для задачи

 ,


0

1

Всем привет.
Вот нашел такую интересную задачу, пока в голову ничего путевого не пришло. Собственно задача

У сороконожки 40 левых ножек и 40 правых ножек. Под кроватью у сороконожки a левых тапочек и b правых тапочек. Сороконожка, просыпаясь, надевает тапочки. Для этого она засовывает под кровать первую левую ножку и надевает первый попавшийся тапочек, тратя на это одну секунду. Если тапочек оказывается левым, то она переходит ко второй левой ножке. Если же он оказывается правым, она переодевает его на какую-нибудь необутую правую ножку, тратя ещё одну секунду, то есть всего на такой тапочек уходит две секунды. Если все правые ножки уже обуты, то она снимает тапочек и кидает его в угол комнаты, тратя на это одну секунду, то есть на такой тапочек сороконожка тратит также две секунды. Процесс продолжается до тех пор, пока все левые ножки не окажутся в левых тапочках. Затем сороконожка аналогичным образом начинает надевать правые тапочки, продолжая до тех пор, пока не будут обуты все правые ножки.
Сегодня сороконожка встала не с той ножки, поэтому она готовится к худшему. Несмотря на это, она, как обычно, начинает обуваться с левой ножки. Сколько секунд понадобится сороконожке на утреннее обувание?
Исходные данные целые числа a и b (40 ≤ a, b ≤ 100).
Результат, сколько секунд понадобится в худшем случае сороконожке на утреннее обувание.


Кто что подскажет)
Спасибо.

Как пример, если взять 40 и 40 то получим 120.

Boy_from_Jungle ★★★★
() автор топика

Пусть a ≤ b, для определённости и начинает обуваться она с левой ноги.

Пусть сороконожка b раз вытищила правый тапок, тогда надела все правые тапки и потратила 2*b секунд на это. В таком случае все следующие тапки будут левыми и сороконоэка обуется за 2*b + 40 секунд. В этом случае минимально время обувания - 120 сек., максимальное определяется через b.

Может можно ещё увеличить время, но ночью ничего лучше в голову уже не приходит. Вроде таким способом получается максимальное кол-во использованных тапков, но я не уверен, что это самый «долгий» способ.

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

А, есть езё такой вариант.

Сначала надеть 39 правых за 39*2 сек, потом 40 левых за 40 сек.

Получим оценку времени 39*2 + 40 + (a - 40)*2 +1.

(a - 40)*2 - это добивание левых тапков, думай можно прикинуть для какие a и b какой алгоритм лучше.

Norgat ★★★★★
()

У сороконожки 40 левых ножек и 40 правых ножек

восьмидесятиножка?

Результат, сколько секунд понадобится в худшем случае сороконожке на утреннее обувание.

160

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от metar

находил такое, но в сонном состоянии так и не понял зачем так

Boy_from_Jungle ★★★★
() автор топика

лобовое решение дин прог

на четырёх осях - число(ещё не обутых) левых ног , число(ещё не обутых) правых ног, число свободных левых тапок.

в ячейке максимальное время.

начиная из состояния 40,40,a,b идя в глубину заполняем ячейки(начальные значения нули) -

лень думать катит ли жадное - после тестовой проверки можно сравнить решения дин прога и жадного и если совпадают то

qulinxao ★★☆
()

Сороконожка, просыпаясь, надевает тапочки. Для этого она засовывает под кровать первую левую ножку

Сегодня сороконожка встала не с той ножки, поэтому она готовится к худшему. Несмотря на это, она, как обычно, начинает обуваться с левой ножки

x = как обычно? Я угадал?

vahtu
()

худший случай - это когда левой ножкой 100 раз в правый тапочек, получается 40х2=80с - на правые ножки , плюс 60х2=120 - в угол тапочки и 40 сек для всех левых. Всего 240с

skvach
()

У сороконожки 40 левых ножек и 40 правых ножек.

У сороконожки 20 писек.

DELIRIUM ☆☆☆☆☆
()

У сороконожки 40 левых ножек и 40 правых ножек.

Сороконожка - всего сорок ножек, а не 40 правых и 40 левых.

andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Сороконожка - всего сорок ножек, а не 40 правых и 40 левых.

Я помню задачку для младших классов, где спрашивается, сколько ножек у сороконожки. Правильный ответ там: нисколько, потому что у сороконожки не ножки а лапки.

DELIRIUM ☆☆☆☆☆
()

Вот нашел такую интересную задачу

У тебя очень своеобразное представление об интересном.

anonymous
()

что сороконожка делает когда все левые ножки обуты, а следующий валенок - левый. Тратит 2?

pousqie
()
Ответ на: комментарий от metar

пардон - не читал, только стартовое сообщение прочел и сразу вспомнилось это задание на тимусе

saibogo ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.