Важно:Сразу прошу вас не пишите готовую программу ,а только объясните сам алгоритм в кратце:
Это задача с онлайн: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) максимум
что за алгоритм можно применить в этом случае,посоветуйте?

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

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

2 ≤ N ≤ 50000

2 ≤ N ≤ 50000

В общем такие задачки на олимпиадах надо решать так. Либо угадать закономерность, либо, что в 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. после олимпиады желательно доказать правильность

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

Только что проверил на 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 мин.

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

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

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

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

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

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

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

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

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

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

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

Странный ты какой-то. Напиши и посмотри.

Michael_Rybak,это странность называется просто ленивостью....признаю и извиняюсь Порок

Скажи честно, ты понял что я предлагаю сделать? Там ведь нефиг писать.

Возьмём вариант когда n нечётно, а после будем продвигаться по видоизменённому алгоритму volvo, то еcть:
1-ый индекс = P нечётно, N-P+1=3-1+1=3
2-ой индекс = P чётно, то скорее всего P=2
3-ий индекс = P нечётно, N-P+1=3-3+1
Я прав?

Задачу можно будет считать решенной полностью, когда ты не только угадаешь ответ, а и докажешь его правильность. А угадал ты или нет можно проверить на тимусе.

Но я и задачу к тому же изначально неправильно понял:

то есть при N=4,путь таков:
1 2 3 4 1
из этого выходит что позиции первого и последнего индекса неизменяемы.Решение задачи повернулось на 90 градусов
Будем продолжать испытания...

Перебор пишется 5, от силы 10 минут. Пишешь перебор и никаких экспериментов.

Извини но я не знаю как делать полный перебор ...не проходили... и я сам особо вариантами не блещу...

огромное спасибо за терпение к этой проблеме,Michael_Rybak.

Тебе нужно для данного набора чисел узнать, как их расставить лучше всего, т.е. какая расстановка даст максимальную/минимальную сумму попарных произведений соседних элементов.

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

Код, генерящий все перестановки данного множества чисел, берешь в ФАКе. Оценочную функцию пишешь сам. Давай, начни, рад буду помочь с проблемами.