07/04/2025 04:53:39

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1123. Приз

Ограничения: время – 2s/4s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Наконец пять конкурсов завершились, и перед победителем популярного телевизионного шоу заветные двери, ведущие в сокровищницу. Перед сокровищницей расположено

$N$ длинных коридоров, все коридоры и сокровищница соединены между собой

$M$ дверьми, как показано на рисунке. Игрок находится в первом коридоре. Чтобы добежать до сокровищницы, у него всего

$K$ секунд. Если он не успеет за отведенное время добежать до нее, то он ничего не получает. Отчет времени начнется, когда он выберет одну из

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

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

В первой строке входного файла содержится три целых числа, разделенных пробелами – количество коридоров

$N$ (

$1\ ≤\ N\ ≤\ 50$ ), количество дверей

$M$ (

$1\ ≤\ M\ ≤\ 50$ ) и лимит времени игрока

$K$ (

$N\ ≤\ K\ ≤\ M*(N-1)+1$ ). Далее следует

$N$ строк, в каждой строке

$M$ целых чисел в диапазоне от 1 до

$1000000/N$ , разделенных пробелами – числа на дверях.

$j$ -е число в

$(i+1)$ -й строке входного файла соответствует числу, написанному на

$j$ -й двери в

$i$ -м коридоре.

В первой строке выходного файла вывести

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

$K$ секунд, а сумма чисел на пройденных дверях минимальна.

Пример ввода

4 5 6
250000 100000 150000 200000 200000
100000 150000 250000 100000 250000
150000 250000 100000 100000 1
250000 100000 250000 100000 100000

Пример вывода

3 4 5 5

05/01/2005	Областная олимпиада школьников по информатике (личное первенство) (4)
10/07/2019	Лето 2019 - 5 (B)