Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача G. Самолетик
| Имя входного файла: | g.in |
| Имя выходного файла: | g.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Есть N аэропортов, пронумерованных числами от 1 до N. Запас топлива (в баках) в каждом аэропорту равен номеру этого аэропорта (то есть в первом аэропорту - один бак, во втором - два и т.д.)
В аэропорту номер N стоит самолет. В каждом из аэропортов (если, конечно, там еще есть топливо) самолет может заправить бак, и долететь до любого другого аэропорта (летать из аэропорта в него же бессмысленно - это не приносит авиакомпании прибыли). Экипаж хочет совершить как можно больше рейсов.
Напишите программу, которая определит, какое наибольшее количество рейсов сможет совершить самолет, и в какие города и в каком порядке он должен для этого летать.
Формат входных данных
Вводится одно число N - количество городов (2≤N≤100).
Формат выходных данных
Выведите сначала число M - количество рейсов, которое совершит самолет. Далее выведите M+1 число: номера городов в порядке их посещения самолетом (первое из этих чисел всегда должно быть равно N). Если вариантов маршрута несколько, выведите любой из них.
Примеры
| g.in | g.out | Комментарии |
2 |
3 2 1 2 1 |
В первом городе один бак топлива, во втором - два. Самолет сначала летит из второго города в первый (во втором остается один бак), потом из первого во второй (в первом топлива не остается), и снова из второго в первый. Совершить больше 3-х рейсов самолет заведомо не сможет, т.к. изначально есть топлива только на 3 рейса. |
3 |
6 3 2 3 2 3 1 3 |
Три раза вылетаем из третьего города, два раза из второго, один раз из первого. Приведенный ответ является неединственным возможным. |