Розв'язки  приймаються до 0 годин 12 лютого 2020 р.

==============================================

Задача Train2020.  Укрзалізниця активно розширює міжнародне сполучення. Для збільшення кількості маршрутів було придбано надсучасні поїзди класу Інтерсіті++. Пробна серія включала рівно один локомотив (з номером 1) та N-1 вагон з номерами від 2 до N.

Після придбання було виявлено, що особливості будови механізму зчеплення вагонів дозволяють зчіплювати лише ті вагони, номери яких мають спільний дільник, відмінний від одиниці. Виключення стосується лише локомотива - він може бути причеплений лише попереду потяга і має можливість зчепитися з будь-яким вагоном.

Від кількості вагонів у рухомому складі залежить прибуток компанії, а тому керівництво просить вас про допомогу - визначити максимальну кількість вагонів (з урахуванням локомотива), які можна сполучити послідовно у рухомий склад.

 

Технічні умови Програма Train2020 зчитує з пристрою стандартного введення єдине число N - кількість отриманих вагонів (N≤105). Програма повинна виводити рівно одне число - максимальну довжину рухомого складу.

Приклади

Введення

Виведення

Коментар

3

2

Вагони 2 та 3 сполучити не можна, а тому рухомий склад буде або 1-2,

або ж 1-3

6

5

Можливий варіант рухомого складу наступний:

1-2-4-6-3

 

Задача Game2020. Улюблена справа колядників - ділити зароблені солодощі та гроші. Олесь та Михась отримали купу цукерок, а крім того грошову купюру певного номіналу. Звісно що ця купюра представляє для хлопців найбільший інтерес, а дорослих, які б могли розміняти суму порівно, немає. Тому старшим братом було запропоновано зіграти у наступну гру.

Кожному з гравців по черзі доводиться обирати деякий непорожній набір кошиків з ряду (таких, що стоять поруч), а далі з кожного необхідно забрати щонайменше по одній цукерці. Такі дії гравці роблять, поки у когось не залишиться можливості зробити хід - тоді цей гравець програє і гроші дістаються переможцю.

Михась вже розклав цукерки по кошикам, але Олесь підозрює, що брат заздалегідь точно знає, що зможе виграти. Олесь, як молодший брат, ходить першим і просить у вас допомоги - чи зможе має він деяку виграшну стратегію для заданого набору цукерок?

Технічні умови З першого рядку стандартного пристрою введення програма Game2020 зчитує єдине число T (1 ≤ T ≤ 10) - кількість тестів. Далі, у T парах рядків слідують вхідні дані у вигляді:

  • У першому в парі - число N (1 ≤ N ≤ 106) - кількість кошиків з цукерками
  • У другому в парі -  N чисел Ai (0 ≤ Ai ≤ 105) - кількість цукерок у кошиках

Програма має вивести рядок з рівно N символів - відповіді на кожен з тестів у тій самій послідовності, що і у вхідних даних. Програма має вивести Y, якщо у Михась точно має стратегію для перемоги і N у іншому випадку.

Приклади

Введення

Виведення

Коментар

3

3

1 0 1

4

1 5 6 1

5

1 0 1 1 1

YNN

У першому випадку Олесь має опорожнити один з кошиків, після чого Михась забере цукерку з іншого і виграє.

У другому випадку Олесь може забрати усі цукерки одразу, чим забезпечить перемогу.

У третьому випадку Олесь може опорожнити два з трьох кошиків, що йдуть підряд, після чого Михасю доведеться взяти цукерку з одного з кошиків, що залишились, що дасть перемогу Олесю.

 

Задача Wall2020

На ідеально гладенькій горизонтальній поверхні нерухомо стоїть куб з масою m1. Неподалік від кубу височіє, стіна, площина якої паралельна одній з бокових граней куба. З протилежного від стіни боку з деякою швидкістю ковзає у напрямку стіни куб з масою m2,. Швидкість перпендикулярна до стіни та бокових граней обох кубів Усі удари абсолютно пружні. Зрозуміло, що після зіткнення перший куб почне ковзати у напрямку стіни, після чого відіб’ється. і, вірогідно, ще раз стикнеться з другим. Вам потрібно визначити загальну кількість зіткнень, що відбудуться в системі.

Технічні умови.   Програма Wall2020 читає з пристрою стандартного введення два цілих числа m1 та m2 - маси кубів (1 ≤ m1 ≤ m2 ≤ 103). Програма має виводити єдине ціле число - кількість ударів.

Введення

Виведення

Коментар для тих, хто не має часу вивчати шкільну фізику

1 10

10

Абсолютно пружний удар – взаємодія тіл без втрат ними сумарної  механічної енергії

10 10

3

 

 

 

 

 

 

Задача  Trunks. Скрудж Макдак знайшов печеру, де в один ряд стояли скрині. На стіні печери написано:

  • З першої скрині можна взяти рівно K монет;
  • З кожноі наступної скрині можна взяти довільну кількість монет, але хоча б одну;
  • Не можна брати з наступної скрині стільки ж монет, що і з попередньої;
  • Якщо з чергової (останньої на цей час)  скрині взяти менше монет, ніж з передостанньої, то з наступної треба взяти більше, ніж з останньої;
  • Якщо з останньої скрині взяти більше монет, ніж з передостанньої, то з наступної треба взяти менше, ніж з останньої;
  • Загалом можна взяти рівно N монет.

Допоможіть Скруджу підрахувати, скількома способами він зможе винести з печери монети. Вважайте, що скринь, а також монет у кожній скрині достатньо.

Технічні умови. Програма Trunks читає з пристрою стандартного введення числа N і K (1≤N≤5000, 1≤K≤N) і виводить на пристрій стандартного виведення остачу при ділення шуканої кількості на 109+7.

Приклади

Введення 3 3

Виведення 1

Введення 6 2

Виведення 4

Пояснення. Для другого прикладу можливі способи: [2,1,2,1], [2,1,3], [2,3,1], [2,4].

 

Задача Kingdoms2020. Автори казок знають, що є ще царства окрім Тридев'ятого, і вони характеризуються як (N,K) - Царства. Але існувати (N,K) - Царство може лише тоді, коли K може бути представлено у вигляді суми не більше ніж N простих чисел.

Наприклад, (3,9) - (Тридев’яте) Царство існує, тому що 9 = 2 + 7 (ще варіанти: 9 = 3 + 3 + 3 і 9 = 2 + 2 + 5). Також має право на існування і (2,10)- (Двадесяте) Царство, так як 10 = 5 + 5. У той же час (2,27)-е (Двадвадцатьсьоме) Царство існувати не може, оскільки 27 неможливо представити у вигляді суми не більше чим двох простих чисел.

Знайдіть кількість існуючих (N, K)-царств за умови, що числа N і K можуть змінюватися в деякому діапазоні: a ≤ N ≤ b, c ≤ K ≤ d.

Технічні умови. Програма Kingdoms2020 читає з пристрою стандартного введення чотири цілі числа в одному рядку через пропуски: a і b - нижнє і верхнє обмеження на N. Та цілі числа c і d - нижнє і верхнє обмеження на K. Програма виводить на пристрій стандартного виведення єдине  число, рівне кількості існуючих (N, K)-царств, для яких a ≤ N ≤ b і c ≤ K ≤ d. Розмір тексту розв’язку не повинен бути більшим 16 Кб.

Обмеження:

1.       Число a від 1 до 1000000 включно.

2.       Число b від a до a + 1000 включно.

3.       Число c від 1 до 1000000 включно.

4.       Число d від c до c + 1 000 включно.

Приклади

Введення

Виведення

Коментарі

1 1 2 10

4

У цьому прикладі нам необхідно знайти числа K, які представляються у вигляді суми не більше 1-го простого числа, тобто є простими. На відрізку від 2 до 10 включно є 4 простих числа - 2, 3, 5 і 7.

1 2 20 30

12

(N, K)-царства існують:

  • при N = 1 - для K = 23, 29

  • при N = 2 - для K = 20, 21, 22, 23, 24, 25, 26, 28, 29, 30

Всього маємо 2 + 10 = 12 царств.

2 4 45 64

58

 

1 20 469588 470425

15701

 

Додаткова інформація

Цитата з однієї, дуже відомої, «казки»:  «Натуральне число X, більше одиниці, називається простим, якщо воно не ділиться без остачі ні на які числа, окрім 1 і X

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

 

 

 

 

© LIKT 1998-2018