Решение задачи Элитные дома с Codeforces
Без пояснения   Просмотров: 91
В столице Берляндии есть n многоэтажных домов. Архитектор, который застраивал столицу, был человеком очень творческим, поэтому все дома были построены в один ряд.
Пронумеруем все дома слева направо, начиная с единицы. Дом считается элитным, если количество этажей в нем строго больше, чем во всех домах с большими номерами. Иными словами, дом элитный, если количество этажей в нем строго больше, чем во всех домах, которые расположены правее, чем он. В данной задаче полагается, что высоты всех этажей во всех домах одинаковы.
Нового архитектора заинтересовали n вопросов, i-й из которых звучит так: «сколько этажей нужно достроить к i-му дому, чтобы он стал элитным?» (где i принимает все значения от 1 до n). Вам предстоит помочь ему справиться с этой задачей.
Заметим, что все вопросы независимы друг от друга — ответ на вопрос для дома i не влияет на другие ответы (то есть, этажи к домам на самом деле не достраиваются).
Пронумеруем все дома слева направо, начиная с единицы. Дом считается элитным, если количество этажей в нем строго больше, чем во всех домах с большими номерами. Иными словами, дом элитный, если количество этажей в нем строго больше, чем во всех домах, которые расположены правее, чем он. В данной задаче полагается, что высоты всех этажей во всех домах одинаковы.
Нового архитектора заинтересовали n вопросов, i-й из которых звучит так: «сколько этажей нужно достроить к i-му дому, чтобы он стал элитным?» (где i принимает все значения от 1 до n). Вам предстоит помочь ему справиться с этой задачей.
Заметим, что все вопросы независимы друг от друга — ответ на вопрос для дома i не влияет на другие ответы (то есть, этажи к домам на самом деле не достраиваются).