задача на пермутацию Опции

[Perfez]

Важно:Сразу прошу вас не пишите готовую программу ,а только объясните сам алгоритм в кратце:
Это задача с онлайн:http://acm.timus.ru/problem.aspx?space=1&num=1535
Преподаватель задал нашёл из интернета и вот задал такую задачу:
1 2 3 4 5 6
То
1*2+2*3+3*4+4*5+5*6
Вот таким способом вычислить максимальное и минимальное умножение как:
6 1 4 3 2 5 (38) Минимум
1 3 5 6 4 2 (80) максимум
что за алгоритм можно применить в этом случае,посоветуйте?

Извините за правку

Сообщение отредактировано: Perfez - 6.03.2007 2:36

[Michael_Rybak]

Сколько чисел максимум в последовательности?

[Гость]

2 ≤ N ≤ 50000

[Perfez]

2 ≤ N ≤ 50000

[Michael_Rybak]

В общем такие задачки на олимпиадах надо решать так. Либо угадать закономерность, либо, что в 99% случаях приводит к положительному результату, написать перебор для маленьких чисел. Почти уверен, что ответы, например для n = 20, имеют вид 1 11 2 12 3 13 .. 10 20, 1 2 3 4 5 .. 20 или типа того.

Для маленьких N (1, 2, 5) оптимальных ответов будет много, но для N = 12 - совсем нет.

Скорее всего, есть небольшая разница для четных и нечетных N, так что запустишь для 12 и для 13.

Перебор напишешь?

P.S. после олимпиады желательно доказать правильность

[Perfez]

По моему пермутация 50000 за 1 секунду...просто невозможно... Прав ли я?

[Michael_Rybak]

На маленьких N ты поймешь закономерность.

Например, ты увидишь, что для N = 13 ответ, к примеру, такой:

1 3 5 7 9 11 13 12 10 8 6 4 2

И поймешь, что в центр ставится n, а дальше по бокам в порядке убывания. И напишешь программу, которая делает то же самое для любого N.

Сообщение отредактировано: Michael_Rybak - 5.03.2007 23:55

[Bard]

Помоему я нашел кратчайший метод вычисления максимального...

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

а насчет минимального надо подумать!!!



Добавлено через 6 мин.
А вот и кстати прога нахождения максимального(работает очень быстро)...

[Алена]

работает очень быстро

Ну, это смотря с каким значением ее запустить... Запусти с 49000, и наслаждайся... Секунд 20-25...

[Bard]

6 1 4 3 2 5 (52) Минимум

уважаемый Perfez,помоему вы делаете какую та ошибку потому что в данном тесте минимум=38
6*1+1*4+4*3+3*2+2*5=6+4+12+6+10=38

Добавлено через 2 мин.

Ну, это смотря с каким значением ее запустить... Запусти с 49000, и наслаждайся... Секунд 20-25...

не 20-25 а 7-9 секунд!!!

[Алена]

Тебе что, скриншот привести, что на FreePascal-е (!!! 32-бита !!!) это работает 18 секунд?

[Perfez]

Алена и arximed,что вы спорите? Толку то какого...задача расчитана на 1 секунду,так что беспокоиться за это не стоит....безполезно по-моему...
P.S.:
Спасибо за деталь, arximed.

[Bard]

Только что проверил на Free Pascale-2.0.0. работает ровно
8 секунд(с лишним...но не как не больше 10-и секунд)...

даже прогнал 50000 и то за 10 секунд прошло...

Добавлено через 3 мин.
что то с минусом не разберусь...
но есть одна деталь:обрати внимание при n=6 разница между числами нечетное а
при-7 мин=7153426 разница-четное...

P.S стараюсь найти для 20 и 21

Добавлено через 6 мин.
нашшшшшшшшеееееелллллллл....

при н=20 минимум=20 1 18 3 16 5 14 7 12 9 10 11 8 13 6 15 4 17 2 19

но есть одна проблема при н=нечетное число логика не соответствует...
тоесть:

при н=21 минимум=21 1 19 3 17 5 15 7 13 11 10 12 8 14 6 16 4 18 2 20...



Добавлено через 4 мин.

Только что проверил на Free Pascale-2.0.0. работает ровно
8 секунд(с лишним...но не как не больше 10-и секунд)...

даже прогнал 50000 и то за 10 секунд прошло...

Добавлено через 3 мин.
что то с минусом не разберусь...
но есть одна деталь:обрати внимание при n=6 разница между числами нечетное а
при-7 мин=7153426 разница-четное...

P.S стараюсь найти для 20 и 21

Добавлено через 6 мин.
нашшшшшшшшеееееелллллллл....

при н=20 минимум=20 1 18 3 16 5 14 7 12 9 10 11 8 13 6 15 4 17 2 19

но есть одна проблема при н=нечетное число логика не соответствует...
тоесть:

при н=21 минимум=21 1 19 3 17 5 15 7 13 9 11 10 12 8 14 6 16 4 18 2 20...

[Bard]

все написал и нахождение минимума теперь их надо собрать в одно целое и вывести единую программу

P.S но помоему будут проблемы со временем

[Алена]

Не знаю, не знаю... (время в миллисекундах)

[Bard]

Не знаю, не знаю... (время в миллисекундах)

да ладно черт со временем самое главное чтобы прога была эффектной...

[Michael_Rybak]

Во-первых, у вас ведь компьютеры разные, как можно спорить, у кого сколько работает

Во вторых программа работает меньше секунды. Даже меньше 0.01 секунды, я думаю.

Время уходит на вывод в консоль. Если перенаправить вывод в файл (а на тимусе, как и везде, вывод перенаправляется в файл, иначе как потом проверять), вы и моргнуть не успеете как она отработает для n = 1000000.

[Perfez]

Ладно с максимум всё понятно,а что с минимум? Есть предложение?

[volvo]

Есть предложение?

На позиции P результирующей последовательности находится число N - P + 1, если P нечетно, и число P - 1, если P - четно ... (по крайней мере при четном N)

[Perfez]

Спасибо за умное предложение

(по крайней мере при четном N)

А что за проблема когда N нечётно?