Задача №114693. Проверка олимпиады
На национальную олимпиаду по математике приехало \(n\) участников со всей страны, каждый из которых сдал свою работу. Теперь перед жюри стоит непростая задача: проверить все \(n\) работ как можно быстрее.
Процесс проверки происходит следующим образом. Каждый из \(m\) проверяющих может выбрать одну из работ участников, которую он будет проверять в течение одного часа. Два проверяющих не могут одновременно проверять одну и ту же работу, поэтому различные проверяющие должны выбрать различные работы. Некоторые проверяющие могут ничего не выбрать. Через час проверка оканчивается, и работы заново распределяются между проверяющими.
Чтобы сделать проверку более объективной, жюри придумало следующее правило: каждую работу должны проверить как минимум \(k\) разных людей.
Помогите жюри составить подходящее расписание проверки, занимающее минимальное время.
На единственной строке даны три целых числа \(n\), \(m\), \(k\) \((1 \le k \le m \le n \le 500)\) – количество работ, общее число проверяющих и минимальное число людей, которые должны проверить каждую работу.
В первой строке выведите единственное целое число \(t\) — минимальное число часов, которое потребуется, чтобы каждую работу проверило хотя бы \(k\) проверяющих.
Далее выведите \(t\) строк по \(n\) чисел \(C_{ij}\) \((0 \le C_{ij} \le m)\), обозначающих номер проверяющего работы номер \(j\) во время часа \(i\). \(C_{ij} = 0\) означает, что работа \(j\) в час \(i\) не проверяется.
Если возможно несколько вариантов ответа, выведите любой из них.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 7 | \(n \le 4\) | \(m \le 4\) | \(k \le 4\) | – | |
| 2 | 9 | \(n \le 9\) | \(m \le 9\) | \(k \le 9\) | \(0, 1\) | |
| 3 | 8 | – | \(m = 1\) | \(k = 1\) | – | |
| 4 | 13 | – | – | – | – | \(n = m\) |
| 5 | 17 | – | – | – | \(3, 4\) | \(n\) делится на \(m\). |
| 6 | 11 | – | – | \(k = 1\) | \(3\) | |
| 7 | 35 | – | – | – | 0–6 | |
3 1 1
3 1 0 0 0 1 0 0 0 1
4 2 2
4 1 2 0 0 0 0 1 2 2 1 0 0 0 0 2 1
5 3 2
4 1 2 3 0 0 3 0 0 1 2 0 1 2 3 0 0 0 0 0 1