Задача 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, поскольку 102 + 112 + 122 = 132 + 142. Последовательность считать найденной, если найден ее первый член.
Технические условия:
Программа Sequence должна прочитать с клавиатуры число N (3≤N<1000). Программа Sequence должна вывести на экран только первый член найденной последовательности, либо “–1”, если такой последовательности не существует. Если задача имеет несколько решений, необходимо вывести минимально возможное
Пример:
Ввод: 5
Вывод: 10
Задача Plums
Фермер Василий П. вырастил урожай слив и был очень удивлен тем, что получил ровно N2 плодов, да еще и все разного веса. Более того, как выяснила жена Василия, учительница математики, если сливы отсортировать по весу, то получится последовательность чисел 1, 2, …, N2. Теперь возникла проблема – перевезти груз на базар для продажи. Сосед Василия согласился перевезти урожай, если всего будет N ящиков по N слив в каждом, и все ящики будут иметь одинаковый вес. Помогите Василию разложить сливы в ящики.
Технические условия:
Программа Plums читает с клавиатуры единственное число N (1 ≤ N ≤ 100). Программа выводит на экран N строк по N чисел в строке через один пробел. Если существует несколько вариантов размещения слив в ящиках – вывести произвольный. Если не существует ни одного способа, вывести единственную строку с единственным числом «–1» (без кавычек).
Пример:
Ввод: 2
Вывод: 1 4
2 3
Задача SumOfPowers
Некоторые натуральные числа (например, 9=32) сами являются квадратами натуральных чисел; некоторые (например, 17=42+12) можно представить как сумму двух квадратов; некоторые (например, 6=22+12+12) — только как сумму минимум трех квадратов; и так далее. Аналогичные подсчеты можно проводить не только для квадратов, но и для других степеней. Например, 17 не является кубом натурального числа и не может быть представлено суммой двух кубов, но может быть представлено суммой трех, как 23+23+13. Напишите программу, определяющую, в сумму какого минимального количества K-ых степеней натуральных чисел можно разложить каждое из чисел N1, N2, …, NM.
Технические условия:
Программа должна прочитать с клавиатуры сначала показатель степени K (1≤K≤98), затем количество чисел M (1≤M≤9876), для которых нужно найти минимальные количества, затем сами числа N1, N2, …, NM (каждое 1≤Ni≤987654). Все числа записаны в одной строке и разделены одинарными пробелами. Программа должна вывести на экран в одну строку M разделенных пробелами чисел — минимальные количества K-ых степеней натуральных чисел, в сумму которых можно разложить числа N1, N2, …, NM.
Пример 1:
Ввод: 2 3 9 17 6
Вывод: 1 2 3
Пример 2:
Ввод: 3 3 9 17 6
Вывод: 2 3 6
Задача Platforms
В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. В одной из версий данной игры, при прыжке с платформы на соседнюю, у героя уходит |y2–y1| энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3×|y3–y1| энергии. Другая версия отличается только тем, что в функциях затрат энергии модули заменены на квадраты, т. е. (y2–y1)2 при прыжке на соседнюю и 3×(y3–y1)2 при прыжке через одну. Известны высоты платформ в порядке от левого края до правого. Найдите (для каждой из версий игры) минимальное количество энергии, достаточное, чтобы добраться с 1-й платформы до n-й (последней).
Технические условия:
Программа должна прочитать с клавиатуры сначала количество платформ N (2≤N≤50000), затем N чисел в диапазоне от –2000 до +2000 каждое — высоты этих платформ. Программа должна вывести на экран в единственной строке два разделенных пробелом целых числа — минимальные необходимые затраты энергии для первой версии игры и для другой версии игры.
Пример:
Ввод: 3 0 20 11
Вывод: 29 363
Для первой версии оказывается выгоднее прыгать по всем подряд платформам 0→20→11, суммарные затраты 20+9=29. Для второй — перепрыгнуть сразу 0→11 выгоднее (3*112=363), чем прыгать по всем платформам подряд (202+92=481).