Помогите решить задачу(про самолетик)...

[22Striker22]

Имя входного файла: 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

[alexBlack]

Если я правильно понял, решение очень простое.
Максимальное количество рейсов = общему количеству топлива.

2 - 3
3 - 6
4 - 10
5 - 15
...
N - N*(N+1)/2

Поскольку можно вывести любую последовательность, достаточно подобрать стратегию при которой будет израсходовано все топливо.
Какой будет последовательность видно из предложенных решений. Берем последние два пункта и летаем между ними пока не кончится топливо. Мы всегда окажемся в пункте с большим номером и с одним баком.
Поэтому сможем вылететь из него в следующую пару пунктов. Так продолжаем до тех пор пока не останется 0 или 1 пункт. Из первого пункта просто вылетаем в любой другой.

По этому алгоритму вывести последовательность чисел не составит труда.
Непонятно только зачем нужны 64 Мб. (Для запуска XP ? )

[puporev]

Непонятно только зачем нужны 64 Мб.

Это же Паскаль и естественно ненавистные 64 Кб. Уже не первый раз вижу что пишут Мб. Видимо не могут врубиться, как это память в килобайтах? И на всякий случай пишут Мб. Мне так кажется.

[sverhuVniz]

Сообщение от alexBlack

Если я правильно понял, решение очень простое.
Максимальное количество рейсов = общему количеству топлива.

2 - 3
3 - 6
4 - 10
5 - 15
...
N - N*(N+1)/2

Поскольку можно вывести любую последовательность, достаточно подобрать стратегию при которой будет израсходовано все топливо.
Какой будет последовательность видно из предложенных решений. Берем последние два пункта и летаем между ними пока не кончится топливо. Мы всегда окажемся в пункте с большим номером и с одним баком.
Поэтому сможем вылететь из него в следующую пару пунктов. Так продолжаем до тех пор пока не останется 0 или 1 пункт. Из первого пункта просто вылетаем в любой другой.

По этому алгоритму вывести последовательность чисел не составит труда.
Непонятно только зачем нужны 64 Мб. (Для запуска XP ? )

а можно по подробнее об алгоритме последовательности перелёта самолёта по пунктам?

[22Striker22]

Сообщение от alexBlack

Если я правильно понял, решение очень простое.
Максимальное количество рейсов = общему количеству топлива.

2 - 3
3 - 6
4 - 10
5 - 15
...
N - N*(N+1)/2

Поскольку можно вывести любую последовательность, достаточно подобрать стратегию при которой будет израсходовано все топливо.
Какой будет последовательность видно из предложенных решений. Берем последние два пункта и летаем между ними пока не кончится топливо. Мы всегда окажемся в пункте с большим номером и с одним баком.
Поэтому сможем вылететь из него в следующую пару пунктов. Так продолжаем до тех пор пока не останется 0 или 1 пункт. Из первого пункта просто вылетаем в любой другой.

По этому алгоритму вывести последовательность чисел не составит труда.
Непонятно только зачем нужны 64 Мб. (Для запуска XP ? )

Если бы все так просто было, я бы к вам не обратился, вот эту последовательность сформировать не получается, т.е. я знаю какая она должна быть, но не знаю как ее написать...

макс. кол-во рейсов равно max=1+2+3...+n, т.е. сумма всех чисел до n.
а сама последовательность, например для n=5, то посл-ность равна 5454545453232313(т.е. кол-во цифр = мах+1). Для п=4, посл-ность равна 43434342121.
Надеюсь закономерность видите.

[alexBlack]

Сообщение от 22Striker22

Если бы все так просто было, я бы к вам не обратился, вот эту последовательность сформировать не получается, т.е. я знаю какая она должна быть, но не знаю как ее написать...

макс. кол-во рейсов равно max=1+2+3...+n, т.е. сумма всех чисел до n.
а сама последовательность, например для n=5, то посл-ность равна 5454545453232313(т.е. кол-во цифр = мах+1). Для п=4, посл-ность равна 43434342121.
Надеюсь закономерность видите.

По-моему пара вложенных циклов:

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

[22Striker22]

Так вот эти вложенные циклы и не получаются, если бы кто нибудь помог бы написать, я был бы оч признателен!!!

[alexBlack]

Сообщение от 22Striker22

Так вот эти вложенные циклы и не получаются, если бы кто нибудь помог бы написать, я был бы оч признателен!!!

Что конкретно не получается ? Цикл While не можете написать ? Почитайте любую книжку по Паскалю. Начните с задач попроще. Не ждите готового решения.

[22Striker22]

Паскаль я знаю(не сильно, но знаю), просто не получаестя этот цикл, я вообще это с помощью for делал, а как с while даже не представляю. Можете хотя бы объяснить как его сделать?

[alexBlack]

var M, N, i, c:integer;
begin
   N := 6;

   M := N; c := 0;
   while M > 1 do begin
     for i := 1 to M - 1 do begin
       write(M);    inc(c);
       write(M-1);  inc(c);
     end;
     write(M);      inc(c);
     dec(M, 2);
   end;
   write(1); inc(c);
   if N mod 2 <> 0 then begin
      write(3); inc(c);
   end;

   writeln(' ', c);
   readln;