Емблема центру  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


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


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