Задача 1. Розряджений акумулятор

Задача 1. Розряджений акумулятор

Обмеження [Час: 1000ms, Пам’ять: 128MB, Складність: 5%]

Студентка-журналістка Маша, виконуючи завдання редакції вперше потрапила на дуже важливу прес-конференцію, але забула підзарядити акумулятор свого ноутбуку, на якому вона зазвичай друкує усі інтерв’ю та статті. Для енергозбереження вона зробила яскравість екрану мінімальною. Прес-конференція продовжувалась дуже довго але Маша встигла набрати весь текст ще до того як акумулятор розрядився. Щаслива та натхненна юна журналістка дорогою до редакції телефоном запевнила головного редактора, що як тільки дістанеться редакції віддасть статтю до друку. Ввімкнувши ноутбук на зарядку Маша помітила, що текст вона набирала випадково натиснувши клавішу caps lock. Таким чином великі літери були набрані маленькими, а маленькі великими. Інші символи крім літер були набрані вірно.

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

Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний текст, який містить не більше 500 символів.

Формат вихідних даних: вихідний файл має містити виправлений текст.

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

input. txt	output. txt
sCHOOL	School

Задача 2. Зварювальник та арматура

Обмеження [Час: 1000ms, Пам’ять: 128MB, Складність: 10%]

Для армування фундаменту майбутньої споруди, бригаді будівельників знадобилась допомога зварювальника, який мав би зварювати порізані напередодні сталеві стрижні арматури у паралелепіпеди, причому різати стрижні не можна і жоден із стрижнів не повинен виступати за каркас.

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

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

Необхідно за відомими довжинами стрижнів для кожного набору перевірити, чи можна з них зварити каркас паралелепіпеда.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N(1 ≤ N ≤ 100), яке представляє кількість наборів.

Далі йдуть N рядків, кожен з яких містить у собі опис набору стрижнів - дванадцять цілих позитивних чисел, що не перевищують 109.

Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору стрижнів вивести «yes», якщо з нього можливо зварити каркас паралелепіпеда, та «no» якщо не можна.

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

input. txt	output. txt
2	yes no

Задача 3. Микола та дроби

Обмеження [Час: 1000ms, Пам’ять: 128MB, Складність: 15%]

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

Дорогою додому Миколу зацікавила наступна задача. Існують такі дроби, де в чисельнику знаходиться найбільший спільний дільник чисельника та знаменника. Якщо позначити чисельник дробу через x, а знаменник через  y, то можна стверджувати, що для цілого числа n виконується наступна умова 1≤х, y≤n. Микола прагне підрахувати, скільки існує таких звичайних дробів для цілого числа n, щоб у чисельнику знаходився найбільший спільний дільник чисельника та знаменника.

Допоможіть Миколі розв’язати його задачу.

Формат вхідних даних: у першому рядку дано ціле число n (1 ≤ n ≤ 106).

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

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

input. txt	output. txt
1	1
4	8
10	27

Зауваження:

У першому прикладі таким дробом є 1/1, так як найбільший спільний дільник чисельника та знаменника дорівнює 1.

У другому прикладі підходять такі дроби: 1/1, 1/2, 1/3, 1/4, 2/2, 2/4, 3/3, 4/4.

Задача 4. Трикутна коробка

Обмеження [Час: 500ms, Пам’ять: 128MB, Складність: 20%]

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

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

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

Сергій та його подруга потребують Вашої допомоги у розв’язанні цієї задачі.

Вам необхідно по заданих числах N і M знайти число способів складання медальок до коробки із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів медальок.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N - максимальна кількість рядів медальок у коробці і M – кількість учасників свята (1 ≤ N, M ≤ 2*109) відповідно.

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

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

input. txt	output. txt
20 10	4
53 199	0
5	157

Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 105 – не менше 55 балів.

Задача 5. Декорації для театру

Обмеження [Час: 1000ms, Пам’ять: 128MB, Складність: 25%]

Батько Павла працює на швейній фабриці. Нещодавно фабрика отримала велике замовлення на виготовлення декорацій для театру. Тканина з якої будуть виконані декорації має малюнок. Для отримання великих площин тканини необхідно суміщати сусідні полоси тканини не порушивши малюнку. Батько звернувся до Павла як до програміста допомогти розв’язати цю задачу.

Не довго думаючи Павло сформулював для себе задачу в наступному вигляді.

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

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

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа A і B(1 ≤ A ≤ 20, 1 ≤ B ≤ 100000). Наступні A рядків містять по B символів кожна – опис першої полоси тканини. Наступні A рядків містять по B символів кожна – опис другої полоси тканини. Кожен рядок опису тканин містить тільки символи ”.” і ”*”.

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

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

input. txt	output. txt
2 5 .*.*. *.*.* *.*.. .*.**	1
1 5 ***.. *..**	2

Задача 6. Вдалий фокус

Обмеження [Час: 500ms, Пам’ять: 16MB, Складність: 30%]

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

Наприклад, прямокутник що має сторони розміром 1 і 10 можна повністю накрити прямокутником зі сторонами 10 і 3, але неможна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити неможна, відповідно в наборі із цих трьох прямокутників вдалим є тільки один.

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

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000).

У кожному з наступних N рядків міститься два цілих позитивних числа – розміри сторін одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників однакових немає.

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

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

input. txt	output. txt
3 1 10 9 9 10 3	1
4 1 7 2 6 3 5 4 4	0

Задача 7. Місто з багатьма мостами

Обмеження [Час: 1000ms, Пам’ять: 128MB, Складність: 35%]

Руслан працює водієм вантажівки, та займається перевезеннями товарів з різних складів до магазину. Місто у якому працює Руслан дуже красиве та славиться великою кількістю островів та відповідно мостів, перетин деяких з мостів, а саме таких, яких неможливо уникнути є платним. Плата є стандартною та складає 1000 монет.

У місті Руслана знаходиться N складів (на кожному острові один склад), що з’єднані M мостами. Мости розміщено таким чином, щоб ніякі два мости не з’єднували одну й ту саму пару островів.

Магазин знаходиться у пункті, позначеному на карті як 1. Руслан вирушає до магазину зі складу позначеного на карті як S.

Яку суму заплатить Руслан за перетин платних мостів.

Формат вхідних даних:

Перший рядок містить 2 числа N, M (2 <= N <= 105 , 1 <= M <= 105). Інші М рядків містять два числа Xi і Yi, які описують дорогу між складом Xi і складом Yi.

В останньому рядку написано число S (2 <= S <= N) – номер складу, а відповідно й острову з якого на якому знаходиться Руслан.

Формат вихідних даних:

Виведіть в одному рядку єдине число – кількість монет які Руслану необхідно мати при собі для сплати перетину платних мостів, або -1, якщо такого шляху немає.

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

input. txt	output. txt
6 7 1 2 2 3 3 1 3 4 4 5 4 6 5 6 6	1000