Задача 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). Програма повинна вивести на екран лише перший член знайденої послідовності або “–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
Завдання підготували В.Боднар, В.Мельник, Г.Непомнящий, Ю.Пасіхов, І.Порубльов