J. Двери
Задачу добавил: alef
Успешно сдано решений: 11
Ограничение по памяти: 256 Мб
Царь Пантелеймон внимательно слушал рассуждения Ферапонта про пальмы и размышлял о том, действительно ли всё новое к лучшему. Не так давно министр безопасности Пафнутий убедил царя, что нужно установить во дворце новую пропускную систему. И теперь, чтобы войти, каждый должен приложить к специальному считывателю пропуск, подождать, пока выполнится процедура аутентификации и массивные двери откроются, и лишь тогда пройти. А иной раз подождать надо, пока двери закроются после прохода предыдущего визитёра: прикладывать пропуск при открытых дверях крайне не рекомендуется.
Конечно, Пантелеймон согласен, что это повышает безопасность, но теперь министры стали чаще опаздывать на совещания, объясняя это тем, что им пришлось подолгу ждать своей очереди у дверей. Впрочем, у царя есть подозрение, что не все министры говорят правду, и он хочет это проверить.
От момента, в который пропуск прикладывают к специальному считывателю, до момента открытия дверей проходит единиц времени. Министр проходит через двери мгновенно, и система фиксирует время его прохода. Закрытие дверей занимает единиц времени.
На совещание пришло министров, и для каждого из них система зафиксировала время, в которое этот министр прошёл через двери.
Известно, что если министр подходил к дверям, когда они были закрыты и не осуществляли проверку пропуска другого министра, то он сразу же прикладывал свой пропуск к считывателю и проходил через двери, как только они откроются.
Если же министр подходил к дверям в момент, когда они не были закрыты или осуществляли проверку пропуска другого министра, ему приходилось ждать.
При этом министры не обязательно проходили через двери в том порядке, в котором пришли. Если несколько министров оказались перед дверями в ожидании, то они могли проходить через двери в любом порядке.
Царь Пантелеймон имеет в своём распоряжении отчёт системы о времени прохода каждого министра. Также он опросил министров, в какое время каждый из них пришёл к дверям. Царь будет считать, что министр говорит неправду, в следующих случаях:
- если считать, что министр указал правильное время своего прихода к дверям, то министр мог пройти через двери раньше того момента, чем он прошёл фактически;
- если считать, что министр указал правильное время своего прихода к дверям, то двери не успели бы открыться к тому моменту, в который он прошёл фактически.
Ваша задача — определить по данным царя Пантелеймона, какие министры совершенно точно сказали неправду.
В первой строке содержатся целые числа , , — количество министров, время, необходимое на открытие дверей, время, необходимое на закрытие дверей.
Во второй строке содержатся целые числа , — время, в которое министр прошёл через двери. Гарантируется, что все моменты времени корректны: для всех .
В третьей строке содержатся целые числа , — время, в которое по словам министра , он пришёл к двери.
В первой строке выведите количество министров, которые совершенно точно сказали неправду.
Во второй строке выведите номера этих министров в порядке возрастания.
12 5 2 6 14 21 30 42 49 56 63 70 80 87 94 1 10 10 7 37 38 40 37 35 72 39 12
6 2 4 9 10 11 12
Первый министр прошёл через двери в момент 6. В дальнейшем ради краткости будем называть время прохода через двери временем входа. Царю он сказал, что пришёл в момент 1, и это правда, поскольку 1+5=6. Время, в которое министр оказался перед дверями, будем также ради краткости называть временем прихода. Пока первый министр проходил через двери, никто другой не мог воспользоваться дверями. Будем говорить, что двери были заняты до момента 6+2=8 [1..8) (не включительно).
Время входа второго министра — момент 14, а время прихода — момент 10, но это не может быть правдой, поскольку 14−5=9 (конечно, возможно, у министра спешат часы, но это не отменяет факта предоставления неверной информации). Двери были заняты с момента 9 до момента 16.
Время входа четвёртого министра — момент 30, а время прихода — момент 7. Но если бы это было так, он мог бы приложить пропуск в момент 8, и прошёл бы раньше. Так что этот министр сказал неправду. Двери были заняты с 25 по 32 [25,32).
Время входа щестого министра — момент 49, а время прихода —- момент 38. И это тоже может быть правдой, если перед ним прошёл пятый. А двери теперь заняты на отрезке [44,51).
Время входа седьмого министра — момент 56, а время прихода — момент 40. Ему можно поверить: впереди были 5 и 6 министры, а затем он прошёл сам. Двери также заняты на отрезке [51,58).
Время входа восьмого министра — момент 63, время прихода — момент 37. Это тоже вполне может быть правдой: он пропустил 5, 6 и 7 министров, потом прошёл сам. Двери заняты на отрезке [58,65).
Время входа девятого министра — момент 70, а время прихода — момент 35. Поверить ему не получится, поскольку на отрезке [32,37) двери не были заняты, и он мог бы пройти. Двери теперь заняты ещё и на отрезке [65,72).
Время входа десятого министра — момент 80, а время прихода — момент 72. Ему тоже не получится поверить из-за «задержки» в 3 единицы времени. А к занятости дверей добавится отрезок [75,82).
Время входа одиннадцатого министра — момент 87, а время прихода — момент 39, и поверить ему никак не получится: на отрезке [72,75) двери были свободны, так что он мог бы пройти раньше.
Время входа двенадцатого министра — момент 94, а время прихода — момент 12. Но в этом случае у него была возможность воспользоваться дверями, ещё когда они были свободны на отрезке [32,37), так что и этот министр сказал неправду.