Четвер, 28.03.2024, 18:08
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 68
ІІІ ЕТАП ВСЕУКРАЇНСЬКОЇ УЧНІВСЬКОЇ ОЛІМІПАДИ З ІНФОРМАТИКИ 2012-2013 НАВЧАЛЬНОГО РОКУ
8-11 клас
ІІ тур

А – Арифметика
Ім'я файлу, який містить вхідні дані:count.in
Ім'я вихідного файлу:count.out
Обмеження часу:100 мс
Обмеження пам'яті:128 M

Молодший брат Степана Мишко навчається в першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану. Напишіть програму, яка визначає кількість різних цифр у числі Мишка.
Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 101000), записане Мишком.
Формат вихідних даних: вихідний файл має містити одне число – кількість різних цифр у числі.
Приклади
Вхідні дані розміщені у файлі count.in Результат роботи знаходиться у файлі count.out
12333
Ідея розв’язку задачі
Так як число багатоцифрове (>255 символів), то скористаємося прийомом читання цифр числа посимвольно. Для початку створимо рядкову величину, яка буде містити всі 10 цифр. А потім будемо з неї видаляти цифри, які є в даному числі. Кількість цифр, що залишаться в рядковій величині потрібно відняти від числа 10 – це і буде шукана кількість цифр.
Розв’язок


B – Степан і сірники
Ім'я файлу, який містить вхідні дані:matches.in
Ім'я вихідного файлу:matches.out
Обмеження часу:100 мс
Обмеження пам'яті:128 M

Степан дуже полюбляє гратись із сірниками. Але він не балується ними, не розпалює вогонь, а розв'язує різні головоломки. Наприклад, він уміє прирівнювати число дев'ять до числа одинадцять, переклавши лише один сірник. Нещодавно батьки Степана подарували йому декілька наборів, кожен з яких складається з дванадцяти сірників. Хлопчик почав збирати з них різні геометричні фігури. Він уже зібрав багато різних фігур, але тепер йому стало цікаво: з яких наборів можливо склеїти каркас паралелепіпеда за допомогою дванадцяти сірників з набору та клею? Ламати сірники не можна і жоден із сірників не повинен виступати за каркас.
Ваше завдання полягає в тому, щоб за відомими довжинами сірників для кожного набору перевірити, чи можна з них склеїти каркас паралелепіпеда.
Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 100), яке представляє кількість наборів. Далі йдуть N рядків, кожен з яких містить у собі опис набору сірників – дванадцять цілих додатніх чисел не перевищують 109.
Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору сірників виведіть “yes”, якщо з нього можливо склеїти каркас паралелепіпеда, і “no” в іншому випадку.
Приклади
Вхідні дані розміщені у файлі matches.in Результат роботи знаходиться у файлі matches.out
2
1 1 1 1 2 2 2 2 3 3 3 3
1 1 1 1 2 2 2 2 3 3 3 4
yes
no
Ідея розв’язку задачі
Як відомо, паралелепіпед має 12 ребер – по 4 на кожен вимір. Отже, паралелепіпед можна склеїти з сірників, якщо є 3 групи по 4 рівних сірники. Відсортуємо розміри сірників за зростанням, і перевіримо, щоб сірники з 1-го по 4-й, з 5-го по 8-й та з 9-го по 12-й були рівними.
Розв’язок


C – Задача від Степана
Ім'я файлу, який містить вхідні дані:task.in
Ім'я вихідного файлу:task.out
Обмеження часу:750 мс
Обмеження пам'яті:128 M

Перебираючи свої дитячі іграшки, Степан знайшов набір із N різних прямокутників і згадав задачу, яку йому колись задав старенький учитель математики. Назвемо прямокутник маленьким, якщо знайдеться інший прямокутник з даного набору, яким можна повністю накрити цей прямокутник. При цьому прямокутники можна повертати, але відповідні сторони мають бути паралельними.
Наприклад, прямокутник зі сторонами 1 і 10 можна повністю накрити прямокутником 10 і 3, але не можна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити не можна, відповідно в наборі із цих трьох прямокутників тільки один маленький. Напишіть програму, яка вирішить згадану Степаном задачу – визначити кількість маленьких прямокутників у даному наборі.
Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000). У кожному з наступних N рядків міститься два цілих додатних числа – розміри одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників немає однакових.
Формат вихідних даних: вихідний файл має містити одне ціле число – кількість маленьких прямокутників у даному наборі.
Приклади
Вхідні дані розміщені у файлі task.in Результат роботи знаходиться у файлі task.out
3
1 10
9 9
10 3
1



4
1 7
2 6
3 5
4 4
0




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


D – Штрафи
Ім'я файлу, який містить вхідні дані:penalty.in
Ім'я вихідного файлу:penalty.out
Обмеження часу:500 мс
Обмеження пам'яті:128 M

Степан нещодавно купив автомобіль, але водійські права ще не отримав. У зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить у ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що ДАІ стоять не на всіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (у країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 карбованців. Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.
Формат вхідних даних: Перший рядок містить два числа N, M (2 ≤ N ≤ 105 , 1 ≤ M ≤ 105). Інші М рядків містять два числа Xi і Yi, які описують дорогу між містом Xi і містом Yi. В останньому рядку написано число A (2 ≤ A ≤ N) – місто в якому живе Степан.
Формат вихідних даних: Виведіть в одному рядку єдине число – кількість карбованців, які Степан має мати при собі.
Приклади
Вхідні дані розміщені у файлі penalty.in Результат роботи знаходиться у файлі penalty.out
6 7
1 2
2 3
3 1
3 4
4 5
4 6
5 6
6
1000








Ідея розв’язку задачі
Ідея розв’язку задачі полягає в пошуку «мостів» графа на шляху від вершини 1 до міста проживання Степана. Міст графа – це ребро, видалення якого збільшує число зв’язних компонентів графа. Малюнок до умови задачі.
Розв’язок


E – Ремонт
Ім'я файлу, який містить вхідні дані:repair.in
Ім'я вихідного файлу:repair.out
Обмеження часу:1 с
Обмеження пам'яті:64 M

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд усе просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати малюнки на сусідніх смугах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином. Кожну смугу шпалер можна описати її частиною – прямокутником довжиною N і шириною M (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось N рядків і М стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами ”.” і ”*” (крапка і зірочка), по одному символу в кожній клітинці.
Вам дано опис двох смуг шпалер. Допоможіть Степану. Напишіть програму, яка визначатиме, на яку мінімальну кількість клітинок потрібно змістити другу смугу вправо, щоб її малюнок співпав із малюнком на першій смузі. Степан придбав такі шпалери, що гарантовано завжди можна це зробити.
Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N і M(1 ≤ N ≤ 20, 1 ≤ M ≤ 100000). Наступні N рядків містять по М символів кожна – опис першої смуги шпалер. Наступні N рядків містять по М символів кожна – опис другої смуги шпалер. Кожен рядок опису шпалер містить тільки символи ”.” і ”*”.
Формат вихідних даних: вихідний файл має містити одне число – на яку мінімальну кількість клітинок потрібно змістити другу смугу вправо, щоб її малюнок співпав із малюнком на першій смузі.
Приклади
Вхідні дані розміщені у файлі repair.in Результат роботи знаходиться у файлі repair.out
2 5
.*.*.
*.*.*
*.*..
.*.**
1




1 5
***..
*..**
2


Розв’язок

Наверх