Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Распределение участков

(Время: 1 сек. Память: 16 Мб Сложность: 62%)

В одном маленьком городке начинают работать n крупных компаний. Для начала они хотят поделить между собой n земельных участков. По расчетам экономистов, компания i может получить с участка j доход ai,j . Каждая компания, разумеется, хочет получить наибольший доход.

Распределением участков занимается лично мэр города. Распределение происходит следующим образом. Каждая компания сообщает мэру, какой участок ей бы хотелось получить. После этого, если на участок претендует несколько компаний, то он отдается той из них, которая может получить с него наибольший доход (чем больше доход, тем больше налогов), а если таких несколько, то той, у которой наименьший номер (меньшие номера, разумеется, имеют знакомые мэра).

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

Оказалось, однако, что найти такой план не так-то просто. Помогите им сделать это.

Входные данные

В первой строке входного файла INPUT.TXT содержится число n (1 ≤ n ≤ 400). Далее идут n строк по n чисел. j-е число в i-ой строке - это ai,j, доход i-ой компании с j-го участка (1 ≤ ai,j ≤ 109).

Выходные данные

В выходной файл OUTPUT.TXT выведите n чисел. i-е число - это участок, на который должна претендовать i-я компания. Если ответ не однозначен, выведите любой.

Пример

INPUT.TXTOUTPUT.TXT
13
5 4 4
5 2 3
2 1 2
1 3 2

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru