Задача C. Цвет победы (Школьный этап 2015 - 2016)
Задачу добавил: alef
Успешно сдано решений: 52
Тем временем путь товарища B лежит вдоль реки, на которой проводится парусная регата. Товарищ B совсем не разбирается в парусном спорте, ему просто нравится смотреть на яхты под разноцветными парусами. Впрочем, у товарища B есть небольшая теория, согласно которой место, занятое яхтой, зависит от цвета её паруса.
До настоящего момента товарищ B уже наблюдал за n регатами, в каждой из которых участвовало m яхт. Ради простоты будем описывать цвета парусов этих яхт целыми числами от 1 до c. У разных яхт, участвовавших в одной регате, могли быть паруса одинакового цвета.
Для каждого цвета паруса j (j = 1, 2, ..., c) товарищ B определил целое число kj следующим образом. Он посчитал, сколько раз яхта с цветом паруса j заняла первое место (пусть это будет число z(j)1), сколько раз — второе место (z(j)2), и т.д., вплоть до m-го места (z(j)m). Затем он посчитал для каждого места y сумму z(j)1 + z(j)2 + ... + z(j)y — сколько раз яхта с цветом паруса j занимала места не ниже y.
Затем он стал сравнивать для каждого места y суммы S[1..y] = z(j)1 + z(j)2 + ... + z(j)y и S[y + 1..m] = z(j)y + 1 + z(j)y + 2 + ... + z(j)m. Через kj товарищ B обозначил наименьшее y, при котором выполняется S[1..y] > S[y + 1..m].
Товарищ B считает наиболее вероятным такой исход нынешней регаты, при котором яхта с цветом паруса j займёт место не ниже kj. Ваша задача — определить цвет паруса (или парусов), для которого товарищ B прогнозирует наиболее высокое место (т.е. наименьшее kj).
В первой строке содержатся целые числа n, m, c (2 ≤ n ≤ 100, 2 ≤ m ≤ 100, 2 ≤ c ≤ 100) — количество регат, за которыми наблюдал товарищ B, количество яхт, участвовавших в каждой регате, и количество цветов парусов.
В каждой из следующих n строк содержится по m целых чисел p(i)1, p(i)2, ..., p(i)m, (i = 1, 2, ..., n, 1 ≤ p(i)q ≤ c, q = 1, 2, ..., m) — цвета парусов яхт в порядке занятых ими мест, начиная с первого.
Для каждого цвета паруса j гарантируется, что яхта под парусом такого цвета участвовала хотя бы в одной регате.
Выведите в первой строке наименьшее значение kj и (через пробел) число s — количество цветов парусов, которым оно соответствует.
Во второй строке выведите через пробел s чисел — цвета этих парусов. Цвета можно выводить в любом порядке.
5 7 4
2 4 1 3 4 3 3
3 1 3 4 4 3 1
4 3 2 2 4 4 3
4 3 4 1 3 3 2
3 3 3 2 3 3 3
4 3
1 2 4