@HizhanovVolodya

Всем привет! Как-то недавно друг рассказал мне про одну задачу, я заинтересовался, но так и не пришел к решению. Нуждаюсь в небольших подсказках, советах, напутствиях

И так, задача такая. Петя играет в игру: под песню должен нажимать ногами на кнопки. В каждый момент он должен нажимать либо на одну (вторая нога может располагаться в любом месте), либо на две сразу.

Для лучшего понимания смотрите рисунок:


Изначально ноги мальчика в центре. Расстояние между блоками 5-1, 5-2, 5-3 и 5-4 - 1 единица. Расстояние между блоками 1-2, 2-3, 3-4, 4-1 - 1.35 единицы. Необходимо минимизировать суммарное перемещение ног и вывести это значение на экран.

Входные данные в таком формате: 1) N - число позиций в песне (от 1 до 10^6) В следующих N строках записано: Z (количество задействованных ног в данный момент) (1 или 2) и сами позиции

К примеру:

вход:

3

1 2

1 4

2 1 3

выход:

4.7

Предполагаю, что решается динамикой, но пока не понимаю, как её организовать.

Буду благодарен за любую помощь!)

0