Разбор задач финала Технокубка 2016

[grechnik]

Если же входил, то ответом для данного i будет k – 1 + gi, где k — порядковый номер данного друга в оптимальном ответе.

Это же неправда. Контрпример: Малыш живёт на этаже 1000, рост Карлсона 1 (чтобы не заморачиваться с вопросами инициализации), на первом этаже друг роста 4, на втором — друг роста 998, на третьем — друг роста 1000, на четвёртом — друг роста 999, на каждом следующем этаже m — друг роста m+1. Оптимальная стратегия, очевидно, — две пересадки на первом и на третьем этажах. Если же поссориться с другом на третьем этаже, то g₃=3 (если доступны только два первых этажа, придётся просить друзей на 2,998,999 этажах), k-1+g₃=4, но Карлсон вполне может добраться за три пересадки, этажи 1,4,999.