Задача В. Оптимизация нагрузки
Задачу добавил: alef
Успешно сдано решений: 35
Николай решил подойти к обучению систематически и выполнять все домашние задания. Экспериментальным путем он выяснил, что на подготовку к практическому занятию, длящемуся одну "пару" (в СамГУ пара — 1 час 30 минут = 2 * 45 минут), ему требуется 2 "пары". Также он определил, что нагрузка N пар в день (учебные пары плюс выполнение домашних заданий) для него является предельной (после этого он устает и ничего не может ни решить, ни выучить). К лекции или к физкультуре Николаю готовиться не нужно.
У Николая имеется расписание на ближайшие D дней, начиная с завтрашнего. Считайте, что учебный год только начался, и ни по одному предмету еще нет заданий.
Ваша задача - составить расписание выполнения домашних заданий. Имейте в виду, что выполнять домашнее задание можно не ранее того дня, когда оно было задано (т.е. состоялось практическое занятие по предмету), и выполнить его нужно не позже дня, предшествующего следующему практическому занятию. Гарантируется, что ни в один день в расписании нет двух пар практических занятий по одному и тому же предмету.
Считайте, что Николай не хочет разбивать подготовку (т.е. он не станет выполнять половину задания в один день, а половину в другой). Также считайте, что Николай очень прагматичен, и не станет делать домашнее задание по предмету, если оно задано на последней в течение этих D дней паре по этому предмету.
Формат входного файла input.txt
Первая строка — целые числа D, K и N (2 <= D <= 10^5, 2 <= K, N <= 1000) через пробел — количество дней в расписании, количество предметов и количество пар в день, в течение которых Николай может заниматься эффективно.
Предметы перенумерованы числами от 1 до K, физкультура числом 0. В случае, если это лекция, после числа без пробела следует заглавная буква L.
Расписание — D строк, в каждой из которых не более N номеров предметов, записанных через пробел. (строки могут быть пустыми, если у Николая выходной день)
Формат выходного файла output.txt
Первая строка выходного файла содержит YES, если удовлетворяющее требованиям задачи расписание выполнения домашних заданий возможно составить, и NO, если это не так.
Пример входного файла – 1
8 4 4
2 2L 3 0
4 1
1L 3L 3
2
2L 1 3L
1
3 4 2 0
Пример выходного файла – 1
NO
Пример входного файла – 2
8 4 6
2 2L 3 0
4 1
1L 3L 3
2
2L 1L 3L
1
3 4 2 0
Пример выходного файла – 2
YES