русский
english
0402. Олимпиада
| Input file name: | matrix.in |
| Output file name: | matrix.out |
| Time limit: | 4 s |
| Memory limit: | 256 megabytes |
Святослав и Валентин любят играть в игры. Недавно они решили сыграть в игру, в которой каждый по очереди предлагает задачу, а соперник должен дать ответ. Если у кого-то не получилось решить задачу, то он считается проигравшим. Святослав загадал Валентину задачу, над которой тот сильно задумался. Дано n строк, в каждой строке содержится n чисел от 1 до n, причем каждое число в строке встречается ровно один раз. Необходимо выбрать такое подмножество из k столбцов, что количество хороших строк относительно этого подмножества максимально.
Строка называется хорошей относительно подмножества столбцов, если числа в соответствующих столбцах этой строки после сортировки представляют собой непрерывный интервал.
Более формально. Пусть дана строка a и выбраны столбцы i1, i2, …, ik. Пусть b1 < b2 < …< bk – это числа ai1, ai2, …, aik в отсортированном порядке. Тогда строка a хорошая, если для любого 2 ≤ j ≤ k выполняется bj - 1 + 1 = bj.
Валентин не хочет проигрывать, помогите ему с решением этой задачи.
Формат входного файла
В первой строке входного файла содержатся два целых числа: 1 ≤ n ≤ 2000, 1 ≤ k ≤ n. Далее содержится n строк, в каждой из которых выводится n различных целых чисел от 1 до n.
Формат выходного файла
В первой строке выходного файла выведите число равное максимально возможному количеству хороших строк. Во второй строке выведите k чисел – номера выбранных столбцов. Порядок столбцов может быть любой. Если существует несколько ответов, тогда выведите любой из них.
Пример:
| matrix.in | matrix.out |
|---|---|
| 4 2 4 1 3 2 1 4 2 3 1 2 3 4 2 4 1 3 | 3 3 4 |
| 4 3 4 1 3 2 1 4 2 3 1 2 3 4 2 4 1 3 | 3 1 4 3 |
В первом примере, если мы выберем столбцы 3 и 4, то все строки, кроме последней будут хорошими.
Во втором примере, если мы выберем столбцы 1, 3 и 4, то все строки, кроме третьей, будут хорошими.
Решения, верно работающие при ограничениях n ≤ 18 будут оценены в 20 баллов.
Решения, верно работающие при ограничениях n ≤ 50 будут оценены в 60 баллов.
Решения, верно работающие при ограничениях n ≤ 200 будут оценены в 80 баллов.
Решения, верно работающие при ограничениях n ≤ 2000 будут оценены в 100 баллов.