1. ЗАВДАННЯ 2-го туру NetOI-2019 (30.11.2019 - 29.12.2019)

Завдання 2-го туру NetOI-2019

(розв'язки приймаються до 0 годин 30 грудня 2019 р.)

Задача SnakeWay Вінницькі зоологи досліджують поведінку норної змії - дуже екзотичної для подільских місцин тварини. Вони помістили одну особину у тераріум з системою підземних ходів і з виходами на поверхню рівно у двох місцях - кутках тераріуму. Поверхня тераріуму поділена на рівні квадрати по 1 дециметру, при чому тераріум має розміри 3хN дециметрів.Науковці помітили, що змія виповзає на поверхню рівно один раз на добу. При цьому змія обповзає усі клітини на поверхні поля, до того ж відтворює маршрут, який пройшла найдавніше (два маршрути вважаються різними, якщо різна послідовність відвідування клітин).Зоологи цікавляться, скільки днів їм треба, щоб побачити один і той же маршрут двічі.

Технічні умови Програма SnakeWay читає з пристрою стандартного введення два рядки. У першому записано натуральне число N  (N < 10⁶) - довжина тераріуму по одній зі сторін. У наступному рядку записано єдину літеру в залежності від розташування виходів у тераріумі. Літера D означає, що тунелі розташовано по діаметрально протилежних кінцях тераріуму, літера S означає, що між тунелями рівно 3 клітини (враховуючи клітини, де знаходяться тунелі), а літера L означає, що між тунелями рівно N клітин (знову-таки, враховуючи клітини, де знаходяться тунелі).Програма  виводить на екран єдине число - кількість днів по модулю 1000000007, які мають очікувати зоологи перш ніж двічі побачити один і той самий маршрут змії. Дні першого і другого спостережень слід враховувати у відповідь. Якщо змія не може проповзти, виконавши умову задачі, слід вивести -1 у якості відповіді.

Приклади

Задача SqStr  “Гарне шифрування - запорука виграшу” - подумав Вася, граючи з рядком з N символів. Для того, щоб зручніше було шифрувати рядок, він перетворив його у послідовність натуральних чисел від 1 до 255. Дуже швидко він придумав прекрасний алгоритм шифрування, який, безумовно, тепер представляє собою державну таємницю, а тому публікувати ми його тут не будемо. Натомість дамо взяти участь у дослідженні властивостей алгоритму. Вася помітив, що алгоритм “гарно” працює на рядках, де добуток кодів символів рівний квадрату деякого натурального числа. Такими рядками є, наприклад, рядки з кодами    (1, 128, 128),  (2, 5, 10), (7, 7, 49). У заданому рядку з N чисел вам необхідно знайти кількість непорожніх підрядків, на яких алгоритм працюватиме “гарно” (тобто підрядки, на яких добуток кодів рівний квадрату деякого натурального числа).

Технічні умови Програма SqStr читає  з пристрою стандартного введення в одному рядку  натуральне число N (N <= 300000) – довжину рядка, а далі через пропуски слідують рівно N натуральних чисел, що за значенням не перевищують 255 - коди символів.

Програма повинна вивести одне ціле число - кількість підрядків, на яких алгоритм працюватиме “гарно”.

Задача Vars2019.  Михась має два мас10иви однакової довжини, які складаються з цілих чисел та змінних. Михась бажає лише одного – замінами змінних на цілі числа досягти, щоб масиви були абсолютно однакові, тобто щоб на відповідних позиціях стояли однакові числа. Допоможіть йому визначити, чи можливо це взагалі.

Технічні умови Програма читає з пристрою стандартного введення число T (1 ≤ T ≤ 10) - кількість тестів. Далі слідують рівно T тестів, кожен з яких представлений трьома рядками. Перший рядок містить рівно одне число N  (N<= 10⁵) - довжину масивів. У наступних двох рядках містяться по N елементів масивів. Кожен елемент - або натуральне число, що не перевищує 1000, або ж ім’я змінної, що складається не більш як з 10 малих літер латиниці.

 Програма виводить на пристрій стандартного виведення у єдиному рядку рівно T літер – відповіді на кожен з тестових прикладів. Це або “Y” (YES), або “N” (NO), в залежності від того, чи можливо прирівняти масиви, чи ні.

Приклад

Задача Megacube.  Андрій – справжній фанат шоколаду, жити без нього не може. Нещодавно йому подарували величезну квадратну плитку молочного шоколаду в прозорій обгортці, яку він вирішив залишити на найкращий день свого життя, а до тих пір лише уявляти смак, споглядаючи на нього крізь плівку. Та одного ранку, прокинувшись, він виявив, що за ніч миші вигризли деякі частинки шоколадки, залишивши на їх місці порожнини. Трохи засмутившись, Андрій вирішив зробити записи про стан шоколадки. Він уважно подивився на кожен з чотирьох торців шоколадки і для кожного рядку записав, скільки квадратиків вигризли миші від краю до першого вцілілого квадратику (там, де миші вигризли шоколадку наскрізь, Андрій записував -1). Це заняття заспокоїло Андрія, тож він зміг піти до школи без зайвих думок. Однак по поверненню він виявив, що миші не тільки повністю доїли залишки його дорогоцінної шоколадки, а і частково попсували папірець з записами. Тепер він хоче зрозуміти, чи вигризли вони щось важливе, або ж дані вціліли і відповідають якій-небудь справжній шоколадці. Допоможіть йому зробити це, поки він остаточно не втратив жагу до життя!

Технічні умови. Програма  Megacube  читає з пристрою стандартного введення число T (1 ≤ T ≤ 10) – кількість тестів. Далі слідують рівно T тестів, кожен з яких поданий п’ятьма рядками:

• перший рядок містить N (1 ≤ N ≤ 10000)  – розмір шоколадки;
• другий рядок містить N чисел L_i (–1 ≤ L_i ≤ N) – записи, отримані при дослідженні лівого торця (у порядку від першого до N-го рядка);
• третій рядок містить аналогічну інформацію для правого торця, в такому самому порядку;
• четвертий рядок містить аналогічні дані (у порядку від першого до N-го стовпчика) щодо верхнього торця;
• п’ятий рядок містить аналогічні записи, отримані при дослідженні нижнього торця шоколадки.

Програма виводить на пристрій стандартного виведення у єдиному рядку рівно T літер – відповіді на кожен з тестових прикладів. Це або “Y” (YES), або “N” (NO).

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

- він є порожнім

- якщо A та B правильні, то AB правильний

- якщо A правильний, то (A) правильний

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

Приклади.

--------------------------------------------------------------------------------------------------------------------------------------------

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