Задача Sorting

N карточек пронумерованы от 1 до N (1≤N≤32767). Карточки тасуются и выкладываются на стол слева направо в один ряд. За один ход разрешается поменять местами любые две карточки. Найдите наименьшее количество ходов, необходимых для упорядочения карточек по возрастанию их номеров.

Технические условия:

Программа Sorting должна прочитать с клавиатуры записанные в одну строку через пробел сначала число N, далее, N попарно различных натуральных чисел, не превосходящих N – номера карточек в порядке их выкладывания на стол.

Программа Sorting должна вывести на экран единственное число – искомое количество ходов.

Пример:

Ввод:   5  2  5  1  3  4

Вывод: 4

Задача Sequence

Найдите последовательность, содержащую N последовательных натуральных чисел (N=2k+1), таких, что сумма квадратов первых k+1 чисел равна сумме квадратов последних k чисел. Например, для N=5 искомой будет такая последовательность: 10, 11, 12, 13, 14, поскольку 10² + 11² + 12² = 13² + 14². Последовательность считать найденной, если найден ее первый член.

Технические условия:

Программа Sequence должна прочитать с клавиатуры число N (3≤N<1000). Программа Sequence должна вывести на экран только первый член найденной последовательности, либо  “–1”, если такой последовательности не существует. Если задача имеет несколько решений, необходимо вывести минимально возможное

Пример:

Ввод:   5

Вывод: 10

Задача Plums

Фермер Василий П. вырастил  урожай слив и был очень удивлен тем, что получил  ровно  N²   плодов, да еще и все разного веса. Более того, как выяснила жена Василия,  учительница математики, если сливы отсортировать по весу, то получится последовательность чисел 1, 2, …, N².  Теперь возникла проблема – перевезти  груз на базар для продажи. Сосед Василия согласился перевезти урожай, если всего будет N ящиков по N слив в каждом, и все ящики будут иметь одинаковый вес. Помогите Василию разложить сливы в ящики.

Технические условия:

Программа Plums читает с клавиатуры единственное число N (1 ≤ N ≤ 100). Программа выводит на экран  N строк по N чисел в строке через один пробел. Если существует несколько вариантов размещения слив в ящиках  – вывести произвольный. Если не существует ни одного способа, вывести единственную строку с единственным числом «–1» (без кавычек).

Пример:

Ввод:   2

Вывод: 1 4

               2 3

Задача SumOfPowers

Некоторые натуральные числа (например, 9=3²) сами являются квадратами натуральных чисел; некоторые (например, 17=4²+1²) можно представить как сумму двух квадратов; некоторые (например, 6=2²+1²+1²) — только как сумму минимум трех квадратов; и так далее. Аналогичные подсчеты можно проводить не только для квадратов, но и для других степеней. Например, 17 не является кубом натурального числа и не может быть представлено суммой двух кубов, но может быть представлено суммой трех, как 2³+2³+1³. Напишите программу,  определяющую, в сумму какого минимального количества K-ых степеней натуральных чисел можно разложить каждое из чисел N₁, N₂, …, N_M.

Технические условия:

Программа должна прочитать с клавиатуры сначала показатель степени K (1≤K≤98), затем количество чисел M (1≤M≤9876), для которых нужно найти минимальные количества, затем сами числа N₁, N₂, …, N_M  (каждое 1≤N_i≤987654). Все числа записаны в одной строке и разделены одинарными пробелами. Программа должна вывести на экран в одну строку M разделенных пробелами чисел — минимальные количества K-ых степеней натуральных чисел, в сумму которых можно разложить числа N₁, N₂, …, N_M.

Пример 1:

Ввод:            2 3 9 17 6

Вывод:         1 2 3

Пример 2:

Ввод:            3 3 9 17 6

Вывод:         2 3 6

Задача Platforms

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. В одной из версий данной игры, при прыжке с платформы на соседнюю, у героя уходит |y₂–y₁| энергии, где y₁ и y₂ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3×|y₃–y₁| энергии. Другая версия отличается только тем, что в функциях затрат энергии модули заменены на квадраты, т. е. (y₂–y₁)² при прыжке на соседнюю и 3×(y₃–y₁)² при прыжке через одну. Известны высоты платформ в порядке от левого края до правого. Найдите (для каждой из версий игры) минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней).

Технические условия:

Программа должна прочитать с клавиатуры сначала количество платформ N (2≤N≤50000), затем N чисел в диапазоне от –2000 до +2000 каждое — высоты этих платформ. Программа должна вывести на экран в единственной строке два разделенных пробелом целых числа — минимальные необходимые затраты энергии для первой версии игры и для другой версии игры.

Пример:

Ввод:            3 0 20 11

Вывод:         29 363

Для первой версии оказывается выгоднее прыгать по всем подряд платформам 0→20→11, суммарные затраты 20+9=29. Для второй — перепрыгнуть сразу 0→11 выгоднее (3*11²=363), чем прыгать по всем платформам подряд (20²+9²=481).