|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
24.10.2008, 20:22 | #1 |
Регистрация: 24.10.2008
Сообщений: 5
|
Помогите решить задачу(про самолетик)...
Имя входного файла: g.in
Имя выходного файла: g.out Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта Есть N аэропортов, пронумерованных числами от 1 до N. Запас топлива (в баках) в каждом аэропорту равен номеру этого аэропорта (то есть в первом аэропорту - один бак, во втором - два и т.д.) В аэропорту номер N стоит самолет. В каждом из аэропортов (если, конечно, там еще есть топливо) самолет может заправить бак, и долететь до любого другого аэропорта (летать из аэропорта в него же бессмысленно - это не приносит авиакомпании прибыли). Экипаж хочет совершить как можно больше рейсов. Напишите программу, которая определит, какое наибольшее количество рейсов сможет совершить самолет, и в какие города и в каком порядке он должен для этого летать. Формат входных данных Вводится одно число N - количество городов (2≤N≤100). Формат выходных данных Выведите сначала число M - количество рейсов, которое совершит самолет. Далее выведите M+1 число: номера городов в порядке их посещения самолетом (первое из этих чисел всегда должно быть равно N). Если вариантов маршрута несколько, выведите любой из них. Примеры Ввод____________________Вывод 2_______________________3 ________________________2 1 2 1(через пробел) 3_______________________6 ________________________3 2 3 2 3 1 3 |
24.10.2008, 21:43 | #2 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Если я правильно понял, решение очень простое.
Максимальное количество рейсов = общему количеству топлива. 2 - 3 3 - 6 4 - 10 5 - 15 ... N - N*(N+1)/2 Поскольку можно вывести любую последовательность, достаточно подобрать стратегию при которой будет израсходовано все топливо. Какой будет последовательность видно из предложенных решений. Берем последние два пункта и летаем между ними пока не кончится топливо. Мы всегда окажемся в пункте с большим номером и с одним баком. Поэтому сможем вылететь из него в следующую пару пунктов. Так продолжаем до тех пор пока не останется 0 или 1 пункт. Из первого пункта просто вылетаем в любой другой. По этому алгоритму вывести последовательность чисел не составит труда. Непонятно только зачем нужны 64 Мб. (Для запуска XP ? ) |
24.10.2008, 23:11 | #3 | |
Старожил
Регистрация: 13.10.2007
Сообщений: 2,740
|
Цитата:
|
|
24.10.2008, 23:16 | #4 | |
Пользователь
Регистрация: 24.10.2008
Сообщений: 32
|
Цитата:
___________________________________ ____________
ВОН ВЫГНАТЬ ПРОКЛЯТЫХ СПАММЕРОВ! |
|
24.10.2008, 23:45 | #5 | |
Регистрация: 24.10.2008
Сообщений: 5
|
Цитата:
Если бы все так просто было, я бы к вам не обратился, вот эту последовательность сформировать не получается, т.е. я знаю какая она должна быть, но не знаю как ее написать... макс. кол-во рейсов равно max=1+2+3...+n, т.е. сумма всех чисел до n. а сама последовательность, например для n=5, то посл-ность равна 5454545453232313(т.е. кол-во цифр = мах+1). Для п=4, посл-ность равна 43434342121. Надеюсь закономерность видите. |
|
25.10.2008, 09:15 | #6 | |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Цитата:
N = 7 [N-1 раз (N, N-1)] 767676767676 [Один раз само N] 7 [N = N-2] 54545454 5 [N = N-2] 3232 3 [Окончание] 13 Итого 12+1+8+1+4+1+2 = 29 = (7*8)/2+1 N = 6 [N-1 раз (N, N-1)] 6565656565 [Один раз само N] 6 [N = N-2] 434343 4 [N = N-2] 21 2 [Окончание] 1 Итого 10+1+6+1+2+1+1=22=(6*7)/2+1 Разница только в окончаниях для четных и нечетных N Последний раз редактировалось alexBlack; 25.10.2008 в 09:24. |
|
25.10.2008, 11:41 | #7 |
Регистрация: 24.10.2008
Сообщений: 5
|
Так вот эти вложенные циклы и не получаются, если бы кто нибудь помог бы написать, я был бы оч признателен!!!
|
25.10.2008, 13:07 | #8 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
|
25.10.2008, 22:21 | #9 |
Регистрация: 24.10.2008
Сообщений: 5
|
Паскаль я знаю(не сильно, но знаю), просто не получаестя этот цикл, я вообще это с помощью for делал, а как с while даже не представляю. Можете хотя бы объяснить как его сделать?
|
25.10.2008, 23:13 | #10 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Код:
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Помогите решить задачу! | Алисик | Помощь студентам | 1 | 24.12.2007 01:21 |