ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование команд УрГУ. Март 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Теперь ты в армии

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Сержант приказал всем новобранцам встать в ряд. Новобранцы сформировали K шеренг по N человек в каждой, но не смогли встать по росту. Правильный способ встать в шеренгу следующий: первый солдат должен быть самым высоким, второй – вторым по росту и так далее; последний солдат в шеренге должен быть самым низким. С целью научить молодых людей вставать в шеренги, сержант приказал, чтобы каждый из новобранцев подпрыгнул на месте столько раз, сколько стоит перед ним в его шеренге новобранцев ниже него. Обратите внимание, что нет двух новобранцев одинакового роста.
Сержант хочет понять, в какой из шеренг в сумме будет совершено наибольшее количество прыжков, чтобы отправить эту шеренгу работать на кухню. Помогите сержанту найти эту шеренгу.

Исходные данные

Первая строка содержит целые числа N и K (2 ≤ N ≤ 10000; 1 ≤ K ≤ 20). Каждая из следующих K строк содержит N различных целых чисел от 1 до N. Новобранцы в каждой шеренге пронумерованы в соответствии с их ростом (1 – самый высокий, N – самый низкий). Каждая строка отображает порядок, в котором новобранцы стоят в соответствующей шеренге. Первое целое число в строке – это номер первого новобранца в этой шеренге и так далее. Следовательно, каждый новобранец подпрыгнет столько раз, сколько есть чисел в строке перед его номером, которые больше, чем его номер.

Результат

Выведите номер шеренги, для которой общее количество прыжков будет наибольшим. Если есть несколько шеренг с максимальным общим количеством прыжков, выведите наименьший из их номеров.

Пример

исходные данныерезультат
3 3
1 2 3
2 1 3
3 2 1
3
Автор задачи: Никита Шамгунов
Источник задачи: USU Open Collegiate Programming Contest March'2001 Senior Session
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1090. Теперь ты в армии