Задача D. Лабораторные работы
Задачу добавил: alef
Успешно сдано решений: 6
Чтобы получить зачет по одному из предметов, нужно в течение семестра сдать N лабораторных работ. На сдачу одной лабораторной работы при условии, что студент подготовился, уходит 1 минута. Как это бывает, не все студенты сдавали лабораторные работы вовремя, и теперь надеются наверстать все на последней неделе. Преподаватель на прием лабораторных на последней неделе выделил K минут.
Студенты организовали "очередь", однако у преподавателя (повышенная вредность) особое мнение, и он сообщил, что будет принимать лабораторные в следующем порядке.
1. Наивысший приоритет имеют студенты, которые готовы ответить по всем оставшимся до получения зачета лабораторным работам.
2. Если таких не оказалось, из очереди выбирается тот студент, у которого уже сдано наибольшее количество лабораторных, и он сдает все работы, которые успел подготовить к этому моменту. Когда подготовленные работы у него закончились, то он либо идет отдыхать (если сдал их все), либо готовиться к отчету по следующим лабораторным работам и в этом случае вновь встает в конец очереди в следующую минуту после того, когда будет готов сдавать хотя бы еще одну работу. В эту минуту он уже может пойти отвечать.
Если есть несколько студентов, имеющих одинаковый приоритет, то выбирается тот, который ближе к "голове" очереди.
Считайте, что на подготовку к одной работе у студента уходит L минут. Кроме того, студент не в состоянии удержать в памяти материал более, чем по Z лабораторным работам одновременно. Поэтому если он подготовился к отчету по Z работам, а его очередь еще не подошла, он прекращает готовиться, пока не сдаст эти.
Наконец, если подготовка к отчету по лабораторной работе была прервана до истечения L минут (подошла очередь сдавать), то студент забывает все то, что выучил, и ему придется готовиться к этой лабораторной с самого начала.
Ваша задача — определить, сколько студентов получит зачет.
Формат входного файла input.txt
Первая строка — целые числа S, N, K, L, Z (все натуральные и не превосходят 1000) через пробел. S — количество студентов, желающих получить зачет, N — количество лабораторных работ, которые надо сдать, K — время в минутах, которое выделил на прием задолженностей преподаватель, L — время в минутах, которое требуется студенту, чтобы подготовиться к отчету по лабораторной работе, Z — максимальное количество лабораторных работ, которые студент может подготовить перед очередной сдачей.
Вторая строка содержит S целых чисел Vj (0 <= Vj < N, j = 1, 2, ..., S) — количество лабораторных работ, которые уже сданы соответствующим студентом на момент начала приема лабораторных работ. Студенты перечислены в порядке занятой ими очереди.
Третья строка содержит S целых чисел Uj (0 < Uj <= Z, j = 1, 2, ..., S) — количество лабораторных работ, которые подготовлены соответствующим студентом к сдаче на момент начала приема лабораторных работ.
Гарантируется, что на момент начала приема лабораторных работ ни один студент не готовится к отчету по лабораторным. В момент начала приема все студенты начинают готовиться к лабораторным работам.
Формат выходного файла output.txt
Первая строка — целое число A — количество студентов, которые получат зачет.
Пример входного файла
8 18 54 4 3
12 16 15 16 15 8 3 15
2 1 3 1 1 3 1 2
Пример выходного файла
7