Задача T1Z1

Заочна олімпіада з інформатики в Хмельницькій області проходить вже 10 років. Маємо надію, що вона буде готувати «інформатиків» ще гугол років.
Нехай відомо число N – кількість днів до певної заочної олімпіади з інформатики в далекому майбутньому. В який день тижня відбудеться ця олімпіада, якщо сьогодні четвер (15.10.2009).

Формат вхідних даних: в одному рядку – натуральне число N – кількість днів. (N<=365*10^100).

Формат вихідних даних: слово маленькими латинськими літерами – день тижня.

Приклад вхідних та вихідних даних:
Вхідні дані:
365

Вихідні дані:
friday

Список днів тижня англійською:
monday – понеділок  
tuesday - вівторок
wednesday - середа
thursday - четвер
friday - п’ятниця
saturday - субота
sunday – неділя

Задача 1 "Унікальна ціна"

Фермер Дієтенко запровадив рекламну акцію, метою якої є розигриш головного призу – кролика. Головний приз дістанеться тому, хто запропонує найменшу ціну на кролика і вона буде єдиною. Таку ціну назвемо – унікальною ціною. Допоможіть фермеру автоматизувати обробку отриманих пропозицій, тобто знайти унікальну ціну, яка подана у копійках.

Вхідні дані: у текстовому файлі price.in через пропуск записані натуральні числа, які не перевищують 50 000.
Вихідні дані: у текстовий файл price.out записати єдине число – унікальну ціну. Якщо такої ціни немає, то вивести «No»

Приклад 1:
Вхідний файл: price.dat
1 6 23 4 63 1 3 1 3 6
Вихідний файл: price.sol
4
Приклад 2:
Вхідний файл: price.dat
2 3 4 3 2 4
Вихідний файл: price.sol
No

Задача 2 "Площа земельної ділянки"

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

Обмеження: 3<=N<=50000. Координати по модулю не перевищують 20000. Час 1с. Сторони багатокутника без само перетинів та не мають спільних точок (окрім сусідніх – у вершинах )

Вхідні дані: у текстовому файлі square.in у першому рядку записане число N – кількість вершин багатокутника, а у наступних N рядках пари чисел – координати вершини.

Вихідні дані: у текстовий файл square.out записати єдине число – площу земельної ділянки. Результат вивести з одним знаком після коми.

Приклад 1:
Вхідний файл: square.in
4
5 0
0 5
-5 0
0 -5
Вихідний файл: square.out
50.0

Задача 3 "Виставка"

Кожної осені Хмельницька обласна адміністрація проводить сільськоосподарську виставку, на яку приїздять поважні фермери, щоб себе показати і на людей подивитися. На таку виставку поїхали наші герої Дієтенко та Вампіров зі своїми кроликами. Їхній транспорт має обмежену вантажопідйомність. Ось вони задумалися над тим, яку мінімальну та максимальну суми вони отримають, реалізувавши свій товар. Їм відома Е -маса автомобіля не навантаженого, F – повна маса атомобіля, маса одного кролика Мi та його вартість Рi Допоможіть їм знайти максимальну та мінімальну суми, які вони можуть отримати.

Вхідні дані: у текстовому файлі market.in у першому рядку записані числа E i F: 1<=E<=F<=10000. У другому рядку – число N: 1<=N<=500 - кількість кроликів, а у наступних N рядках пари чисел Мi та Рi : 1<=Pi<=50000, 1<=Mi<=10000, які розділені пропуском. Всі числа натуральні.

Вихідні дані: у текстовий файл market.out записати через пропуск два числа: максимальну та мінімальну суми. Якщо автомобіль не може мати точно задану вагу при умові, що він навантажений заданими кроликами, то вивести «This is impossible.».

Приклад 1:
Вхідний файл: market.in
1000 1100
2
1 1
5 2

Вихідний файл: market.out
250 100

Приклад 2:
Вхідний файл: market.in
1000 2000
1
10 3

Вихідний файл: market.out
This is impossible.

Задача 1 "Game"

Ліміт часу: 300мс
Ліміт пам'яті: 32 Мбт

Вовочка любить на уроках математики грати різні інтелектуальні ігри – не байдикувати ж зовсім. Недавно він захопився такою простою грою. Спочатку для гри вибирає деяке натуральне число N і малює на папері кружечок. Потім малює ще один і з’єднує його з першим лінією. Після цього малює наступний кружечок і з’єднує його з одним із попередніх. Так він робить до тих пір, поки на листку не буде рівно N кружечків. Свої кружечки Вовочка нумерує в довільному порядку числами від 1 до N. Складіть програму, що визначить скільки різних малюнків може зробити Вовочка для вибраного N. Малюнки вважаються різними, якщо існують такі кружечки з номерами i та j, що на одному малюнку вони з’єднанні, а на іншому – ні.

Формат вхідних даних. У першому рядку вхідного файлу game.in міститься K (0<K<=10) – кількість тестів. Наступні K рядків містять натуральне число N (0<N<=100) для кожного тесту.

Формат вихідних даних. Для кожного тесту у вихідний файл game.out вивести залишок від ділення кількості різних малюнків на число 2000000011.

Приклад вхідних та вихідних даних.
game.in
3
1
2
3

game.out
1
1
3

Задача 2 "Cubes"

Ліміт часу: 200мс
Ліміт пам'яті: 32 Мбт

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

Формат вхідних даних. Перший рядок вхідного файлу cubes.in  містить натуральне число N (1<N<=1000) – кількість кубиків у наборі Вовочки. Дальше у наступних N рядках описані кольори граней кожного кубика за допомогою шести великих літер латинського алфавіту, що позначають відповідний колір (A - Azure Blue, B - Blue, C - Cyan, G - Green, O - Orange, R - Red, S - Sun Yellow, V - Violet, W - White, Y - Yellow). Грані кубика ідуть у наступному порядку:  передня, права, ліва, задня, верхня, нижня.

Формат вихідних даних. У вихідний файл cubes.out вивести найбільшу висоту вежі, що може бути побудована за описаними правилами з кубиків Вовочки.

Приклад вхідних та вихідних даних.
cubes.in
4
GYVABW
AOCGYV
CABVGO
OVYWGA

cubes.out
3

Задача 3 "Decoder"

Ліміт часу: 300мс
Ліміт пам'яті: 32 Мбт

Вовочка з Васильком жили в різних будинках і під час осінніх канікул, що дорослі їх назвали Карантином, придумували собі різні забави. Пропоную вашій увазі одну з них. Вовочка відправляє Васильку SMS із словом із N символів. Василько здійснює над словом X (0<=X<N) циклічних зсувів (циклічний зсув – це коли останній символ переходить на місце першого) і відправляє слово назад до Вовочки. Вовочка повинен визначити скільки циклічних зсувів зробив Василько або чи зробив він помилку при цих зсувах. При невеликих словах ця гра була досить простою, але із збільшенням кількості символів її складність зросла.

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

Формат вхідних даних. У першому рядку вхідного файлу decoder.in  міститься натуральне число N (1 <= N <= 250000) – кількість символів у слові. Другий рядок містить перше слово. Третій рядок містить слово, що було отримане в результаті циклічних зсувів. Слова складаються із символів таблиці ASCII з кодами від 33 до 255.

Формат вихідних даних. У вихідний файл decoder.out вивести найменшу кількість циклічних зсувів, що їх треба зробити щоб із першого слова отримати друге або «-1» без лапок у випадку, коли це зробити неможливо.

Приклад вхідних та вихідних даних.
decoder.in
8
karantyn
tynkaran

decoder.out
3

Задача 1 "Свиноманія"

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

Він склав карту міста. Карта являє собою прямокутник розмірами 1000x1000 з сторонами паралельними осям координат.
Південна вулиця має координати (0,0) – (0,1000) . Північна має координати (1000,0) – (1000,1000)
Він склав програму яка визначає чи є безпечний шлях з вулиці Північної ( на якій він мешкає), до вулиці Південної (де мешкає його кохана Марічка) і продемонстрував це мамі. Вася впорався з завданням і зараз спілкується зі своєю коханою, а вам слабо?

Вхідні дані:
В першому рядку вхідного файлу porkflu.in міститься ціле число T – кількість наборів даних (1<=T<=10).
Далі йдуть самі набори. Перший рядок кожного набору містить одне число N – кількість уражених майданчиків (0<=N<=1000).
Кожен з наступних N рядків описує уражений майданчик (круг) і містить 3 числа: Xi, Yi, Ri – координати центру і радіус ураження.

Вихідні дані:
Для кожного набору даних виведіть в окремий рядок вихідного файлу porkflu.out слово YES якщо, можна дістатись з північної до південної вулиці без ризику бути ураженим вірусом, та NO в іншому випадку.

Приклад вхідних даних:
3
500 500 499
0 0 999
1000 1000 200

Приклад вихідних даних.
YES

Задача 2 "Ділки"

На боротьбу з примарою свинячого грипу ділки з фірми “А1H1 Ltd” вибили фінансування з державного бюджету. Тепер вони займаються дослідами і намагаються виявити вірус в різних матеріалах і речовинах. Вони розробили прилад, який за зразком проби переводить її у цифровий код – KOD - послідовність цілих позитивних чисел.
Тепер вони переймаються пошуком підпослідовності VIRUS - чисел які йдуть підряд у послідовності KOD і мають таку властивість: VIRUS[1] > VIRUS[2] < VIRUS[3] > VIRUS[4] < VIRUS[5] ….
Дослідники впевнені, що чим більша послідовність VIRUS тим більше імовірність наявності вірусу свинячого грипу у пробній речовині.

Вхідні дані:
У вхідному файлі business.in перше число – N (1<=N<=14000). Далі N різних позитивних цілих чисел не більших за 30000.

Вихідні дані:
У вихідний файл business.out вивести єдине число – довжину найбільшої підпослідовності VIRUS в послідовності KOD

Приклад віхдних даних:
5 2 4 1 3 5

Приклад вихідних даних:
3

Задача 3 "Факторіали"

Факторіал числа N (позначається N! ) визначається наступною рекурентною формулою:
При N=0 , N! = 1
При N>0 , N! = (N-1)! * N

Необхідно визначити найменше число факторіал якого закінчується рівно на K нулів.

Вхідні дані:
У вхідному файлі factorial.in дано ціле число K , (0<=K<=500000000)

Вихідні дані:
У вихідний файл factorial.out вивести  найменше число, факторіал якого закінчуєтсья рівно на K нулів.

Приклад вхідних даних:
2

Приклад вихідних даних:
10

Задача 1 "Цікаві числа"

Існують натуральні числа, що закінчуються цифрою N, такі, що перенесення цифри N на початок числа приводить до збільшення числа в N разів.
Наприклад,  число 102564, N=4, 410256=102564*4.

Формат вхідних даних: у єдиному рядку вхідного файлу задано натуральне число N (2<=N<=9).

Формат вихідних даних: єдиний рядок вихідного файлу повинен містити одне число - найменше натуральне число, що задовольняє дану умову.

Приклад вхідних та вихідних даних:

Задача 2 "Дивні числа"

Вася називає число дивним, якщо кількість його дільників непарна, наприклад число 4 – дивне, воно має 3 дільники: 1,2,4. Задано список чисел, Вася хоче знайти кількість дивних чисел у ньому. Так як Вася не вміє програмувати, то це завдання було доручене Вам.

Формат вхідних даних: у першому рядку вхідного файлу заданий розмір списку – натуральне число N (1<=N<=100). У наступних N рядках записані натуральні числа без ведучих нулів, які не перевищують 10^20.

Формат вихідних даних: єдиний рядок вихідного файлу повинен містити одне число - кількість дивних чисел у заданому списку.

Приклад вхідних та вихідних даних:

Задача 3 "Прогулянка по місту"

У Кракові, недалеко від берега Вісли стоїть Дракон: кам’яний, з пухирчастим тілом, величезними лапами, до неба піднятою головою. Місто Краків – улюблене місто туристів, які з’їжджаються сюди звідусіль. Петрик – один із них. Карта Кракова являє собою таблицю, розміром NxM, клітинками якої є квартали, деякі з яких доступні для руху, а деякі ні. Також на карті відмічені цікаві місця, причому це також квартали, по яких можливий рух. Вася вибрав маршрут для ознайомлення з містом. Він почне з клітинки (1;1), прийде в клітинку (N;M), а потім знову повернеться туди звідки прийшов (в клітинку (1;1)). Звичайно, Петрик хоче переглянути якнайбільше різних цікавих місць. Так як Петрик знає Краків дуже погано, та й взагалі заблукати тут дуже небажано, він вирішив, що на шляху до клітинки (N;M) буде завжди іти вправо, або вниз (відносно карти), а на зворотнім – вліво, або вверх. Допоможіть Петрикові знайти максимальну кількість різних цікавих місць, в яких він може побувати.

Формат вхідних даних: у першому рядку вхідного файлу міститься два числа – N та M (1<=N,M<=100). В наступних N рядках міститься опис карти – рядок з M літер, причому “#” означає квартал недоступний для руху, “*”  – місце для перегляду, а “.” (точка) – квартал доступний для руху, який слугує Васі лише клітинкою для руху. Гарантується, що клітинки (1;1) й (N;M) не будуть позначені символом “#”.

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

Приклад файлів вхідних і вихідних даних: