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


Годинник
 
Задания 1 тура NetOI-2016 (14.10-10.11) 2016 г.

 

Решения принимаются до  0 часов 11 ноября 2016 г.


 

Задача  Matrix2016. Заполним матрицу А размером N*M (N строк, M столбцов) числами от 1 к N*M двигаясь по строкам слева направо. Например, матрица 3*3 будет иметь вид

1

2

3

4

5

6

7

8

9

Заполним матрицу В размера N*M (N строк, M столбцов) числами от 1 к N*M двигаясь по столбцам сверху вниз. Например, матрица 3*3 будет иметь вид

 

 

1

4

7

2

5

8

3

6

9

Нужно посчитать количество одинаковых чисел, стоящих на одинаковых местах в обеих матрицах. Так для приведенных матриц есть три числа, которые стоят на одинаковых местах - 1 (1, 1), 5 (2, 2) и 9   (3, 3).

Технические условия. Программа Matrix2016  читает с устройства стандартного ввода натуральные числа N и M (не больше 106) и выводит на устройство стандартного вывода  единственное число - искомую величину.

Пример

Ввод 3 3

Вывод 3


Задача  SG2016.  Двое играют в следующую игру. На доске записывают дроби 1/n, 2/n, ..., n-1/n. За один ход игрок может выбрать некоторую непустую последовательность дробей (возможно, лишь одну) и сократить числитель и знаменатель каждой из них на целое число, больше 1 (для каждой дроби это число выбирается отдельно). Тот, кто не может сделать ход, проигрывает. Выведите номер победителя при условии, что оба игрока играют оптимально. 

Технические условия. Программа считывает с устройства стандартного ввода единственное целое число n (2 ≤ n ≤106). Программа выводит на устройство стандартного вывода единственное целое число - номер победителя при условии оптимальной игры обоих игроков.

 Примеры

Ввод 3

Вывод 2

Ввод 4

Вывод 1

КомментарийВ первом тесте на доске записано числа 1/3 и 2/3.  Первый игрок не может сделать ход и потому проигрывает. Во втором тесте на доске записано 1/4, 2/4, 3 /4. Единственный возможный ход - сократить дробь 2/4 на 2, после чего второй игрок проигрывает.


Задача Sum2016. Дано натуральное число n. Найдите минимальное натуральное число, которое ровно в n раз больше суммы своих цифр.

Технические условия. Программа читает с устройства стандартного ввода натуральное число n (n<=100000) и выводит на устройство стандартного вывода минимальное натуральное число k такое, что k=n*S(k), где S(k) - сумма цифр числа k. Если ни одного k, удовлетворяющего условию, не существует, выведите 0.

Пример

Ввод  4

Вывод  12


Задача  Barriers. Начинающий бегун преодолевает дистанцию с барьерами. Поскольку он неопытен, пробежав от старта с нормальным перепрыгиванием n1 барьеров, он на следующем спотыкается. Дальше он так же пробегает еще n1 барьеров и на следующем спотыкается - и так до конца дистанции. Пробежав от старта n2 барьеров, он сбивает следующий. Дальше он так же пробегает еще n2 барьеров и сбивает следующий - и так до конца дистанции. Пробежав от старта n3 барьеров, он оббегает следующий. Дальше он так же пробегает еще n3 барьеров и оббегает следующий - и так до конца дистанции.

Есть исключения!

 1. Если найдется барьер, на котором бугун может споткнуться и в то же время  сбить - бегун оббегает этот барьер.

 2. Если найдется барьер, на котором бегун может споткнуться и в то же время  оббежать - иегун сбивает этот барьер.

3. Если найдется барьер, который бегун может сбить и в то же время оббежать, бегун спотыкается на нем.

Эти три исключения действуют на всей дистанции, но! Если он добежал до барьера, который может и сбить, и оббежать и, в то же время, на этом же барьере споткнуться - он прекращает бег перед этим барьером.

Сколько всех барьеров он пробежит? На скольких барьерах он споткнется? Сколько из них он собьет и сколько будет оббегать?

Технические условия. Программа  Barriers  читает с устройства стандартного ввода числа n1, n2, n3 через пробел (все попарно различные и принимают значение от 2 до 100 включительно). Программа выводит  через пропуск на устройство стандартного вывода общее количество барьеров, которые так или иначе пробежал бегун, количество барьеров, на которых он споткнулся, количество барьеров, которые он сбил,  количество барьеров, которые он оббежал.

Пример

Ввод                                                Вывод

2 3 4                                                  59  14  11  10


Задача Snake. В декартовой  системе координат на плоскости обозначены все точки, обе координаты которых - целые числа. Через точки проведены вертикальные и горизонтальные прямые. Змея, находящаяся в начале координат, может перемещаться вдоль этих прямых, причем при прохождении через точку змея всегда изменяет направление скорости на перпендикулярное. Найти минимальную длину пути змеи до указанной точки.

Технические условия. Программа Snake читает с клавиатуры координаты конечной точки маршрута (целые числа, не большие 1000 по абсолютной величине). Числа разделяются пробелом. Программа выводит на экран  единственное число - искомую величину.

Пример
Ввод 0 3
Вывод 5


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

 


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