Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Задания 2-го тура NetOI-2011 (22 .11.11-28.12.11)

Задача 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

Фермер Василий П. вырастил  урожай слив и был очень удивлен тем, что получил  ровно  N плодов, да еще и все разного веса. Более того, как выяснила жена Василия,  учительница математики, если сливы отсортировать по весу, то получится последовательность чисел 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

 

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. В одной из версий данной игры, при прыжке с платформы на соседнюю, у героя уходит |y2y1| энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается 3×|y3y1| энергии. Другая версия отличается только тем, что в функциях затрат энергии модули заменены на квадраты, т. е. (y2y1)2 при прыжке на соседнюю и 3×(y3y1)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).

 

 

 

Задания подготовили Боднарь В., Мельник В., Непомнщий Г., Пасихов Ю., Порубльов И.

© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"