Вівторок, 19.03.2024, 06:49
Головна Реєстрація Вхід
Вітаю Вас, Гость · RSS
Меню сайту
Статистика

Онлайн всього: 1
Гостей: 1
Користувачів: 0
Форма входу
 Умови
Задача А. "Степанові будильники"

Бали за задачу: 120
Обмеження часу: 100 мс
Обмеження пам'яті: 64 M
Ім'я вхідного файлу: alarm-clock.in
Ім'я вихідного файлу: alarm-clock.out

   Степан живе в гуртожитку, і як "гарний" студент дуже часто просипає пари. Щоб хоч якось вплинути на ситуацію батьки вирішили подарувати Степану аж два будильники. Тепер Степан ставе обидва будильники на один і то й же час, оскільки сигналу одного будильника замало, щоб його розбудити. До того, батьки передбачили, що Степан може все ж таки проспати, тому перший будильник буде дзвонити кожні n хвилин, а другий - кожні m хвилин. Напишіть програму, яка допоможе визначити, через скільки хвилин обидва будильники задзвонять одночасно вдруге.
Вхідні дані:
   Єдиний рядок вхідного файлу містить два числа n, m (1≤n, m≤109).
Вихідні дані:
   Виведіть одне число - час у хвилинах, через який обидва будильники задзвонять одночасно вдруге.

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
2 36
6 21
42

Задача B. "STEPS-777"

Бали за задачу: 120
Обмеження часу: 100 мс
Обмеження пам'яті: 64 M
Ім'я вхідного файлу: steps-777.in
Ім'я вихідного файлу: steps-777.out

   Степан є офіційним розповсюджувачем програми "STEPS-777". Нещодавно він отримав замовлення на велику кількість копій програми, кожна копія розміщена на одному CD -диску. На складі вже підготували N ящиків до відправки. Ящик з номер i містить Ai копій програми, при цьому його місткість Pi копій (0≤A≤Pi). Але там не знали, що замовниками є військові, а вони люблять точність. Вони замовили рівно K копій продукту, ні більше, ні менше. У зв'язку з цим Степану доведеться перед відправкою повозитися на складі. Оскільки він не знає, як скоро військові приїдуть за замовленням, то дуже нервує, тому він за одну хвилину може розпакувати тільки один ящик, покласти або дістати звідти один диск і запакувати ящик. Так як він дуже панікує, то дістає (кладе) завжди рівно по одній копії.
   Природньо, так як Степан є розповсюджувачем, та ще й офіційним, у нього є необмежений запас копій. Ми повинні заспокоїти його тим, що порахуємо мінімальний час, за який можливо підготувати замовлення до відправки. Степан в кожен момент часу знає, скільки копій знаходиться в кожному ящику. Відповідно ніколи не відкриватиме порожній ящик для того, щоб дістати звідти диск, а також відкривати вже повністю заповнений ящик для того, щоб покласти туди диск. Степану необхідно таким чином упакувати диски в наявні ящики, щоб сумарна кількість дисків у них була рівна К. Гарантується, що сумарна місткість усіх наявних ящиків не менше К.
Вхідні дані:
   Перший рядок вхідного файлу містить два цілих числа N, K (1≤N≤100, 1≤K≤1000) - кількість ящиків, які підготували на складі, і кількість копій, яка потрібна замовнику відповідно.
   Наступні N рядків містять по два цілих числа Ai, Pi (1≤Pi≤1000, 0≤Ai≤Pi) - кількість копій в i-му ящику і його місткість відповідно. Ящики нумеруються послідовно, в порядку їх введення, починаючи з одиниці.
Вихідні дані:
   Перший рядок вихідного файлу має містити одне ціле число М - мінімальну кількість хвилин, яка буде потрібно Степану для підготовки замовлення.
   У наступних М рядках повинні міститися цілі числа Хi. |Хi| номер ящика, з яким належить возитися Степану на i-й за рахунком хвилині, якщо Хi менше нуля, то з ящика дістається одна копія програмного продукту, інакше в ящик додається одна копія програмного продукту.
   Треба врахувати, що в будь-який момент часу в кожному ящику має бути невід'ємна кількість копій, і кількість копій в ящику не повинна перевищувати місткість ящика. Якщо рішень декілька, то виведете будь-яке з них.

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
4 10
0 1
0 2
0 3
0 4






10
1
2
3
2
3
4
4
3
4
4
4 10
1 1
2 2
3 3
5 5
1
-4



2 1
1 1
1 1
1
-1


Задача C. "Будівництво"

Бали за задачу: 120
Обмеження часу: 200 мс
Обмеження пам'яті: 64 M
Ім'я вхідного файлу:
placing.in
Ім'я вихідного файлу:
placing.out

   У Степана після будівництва дачі залишилось N дерев’яних дошок, довжини яких L1, ..., LN(м), з яких він вирішив побудувати на озері кладку для риболовлі.
   Степан вважає - чим довша кладка, тим більше риби!
   Більш того, Степан, як і усі рибалки, дуже забобонний і вірить в усі прикмети. Одна з них - кладка може бути збудована тільки із суцільник дошок (дошки можна розрізати, але не можна склеювати).
   Тепер Степана цікавить яка максимальна довжина кладки D отримається, за умови що йому потрібно М дошок.
Вхідні дані:
   У вхідному файлі записані цілі числа N, M, Li (1≤N≤1000, 1≤M, Li≤2*109) - наявна кількість дошок, кількість дошок необхідна Степану і довжини дошок відповідно.
Вихідні дані:
   У вихідний файл виведіть ціле число D – максимально можлива довжина кладки або число 0 (нуль).

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
4 4 5 5 3 63
4 60
15
25
13
6
0





Задача D. "Студентський календар"

Бали за задачу: 120
Обмеження часу: 200 мс
Обмеження пам'яті: 64 M
Ім'я вхідного файлу:
calendar.in
Ім'я вихідного файлу:
calendar.out

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

Рис.1. У новому календарі роки з номерами 9 і 13 високосні, а з номерами 12 і 7 - ні.

   Тепер перед перед Степаном постало завдання перевірити, наскільки точний новий календар. Для цього він вибрав контрольний інтервал років від A до B включно.
   Вам необхідно надати допомогу Степану, розробивши програму, яка за заданими числами A і В зможе визначити кількість високосних років на заданому інтервалі за правилами нового календаря.
Вхідні дані:
   Рядок вхідного файлу містить два цілих числа відокремлених пропуском A і B (1≤A≤B≤1018) - межі інтервалу, в якому Вам необхідно знайти кількість високосних років за новим календарем.
Вихідні дані:
   Вихідний файл повинен містити одне ціле число N - кількість високосних років за новим календарем в заданому інтервалі.
Пояснення до прикладів:
   У першому прикладі високосними вважаються роки номер 5 і 9.
   У другому прикладі високосними вважаються роки номер 19, 23, 25, 27 і 29.
   У третьому прикладі високосним вважається рік номер 2015.

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
1 102
19 305
2015 2015
1

Задача E. "Оранка"

Бали за задачу: 120
Обмеження часу: 3 с
Обмеження пам'яті: 64 M
Ім'я вхідного файлу:
field.in
Ім'я вихідного файлу:
field.out

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

   На жаль, кінь слабкий і може виявитися не в змозі провести заплановану борозну до кінця - знесилений, він може впасти. Допускати цього не можна! Після оранки однієї борозни кінь відпочиває, так що перед початком проведення чергової борозни його сила дорівнює K.
   Селянин добре знає своє поле, зокрема, йому відомо, що для оранки квадрата (i, j) потрібно витратити tij одиниць сили коня.
   Допоможіть селянинові, розрахувати мінімальну кількість борозен, які треба провести йому, щоб зорати все поле.
Вхідні дані:
   Перший рядок файлу містить значення величин K, N і M (1≤N, M≤2000, 1≤K≤ 2000000000). Кожен з наступних N рядків містить M чисел tij (1≤tij≤100000). Гарантується, що можна знайти послідовність оранки, при якій кінь не гине.
Вихідні дані:
   Єдиний рядок вихідного файлу має містити одне число - шукану кількість борозен.
Пояснення до прикладу:
  
   одна з можливих послідовностей оранки поля для прикладу показана на малюнку.

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
12 6 4
6 0 4 8 0 5
0 4 5 4 6 0
0 5 6 5 6 0
5 4 0 0 5 43
8





Задача F. "Гарні підрядки"

Бали за задачу: 120
Обмеження часу: 2 с
Обмеження пам'яті: 64 M
Ім'я вхідного файлу:
goodstring.in
Ім'я вихідного файлу:
goodstring.out

   Дано рядок S, │S│= n. Підрядок рядка S задається парою із початку і кінця (l, r), до того ж підрядки, які відповідають різним парам, вважаються різними. Розглядаються тільки непусті підрядки, і завжди вірно, що 1≤l≤r≤n. Підрядок називається гарним, якщо у ньому немає домінуючого символа. Символ називається домінуючим, якщо його відсотковий вміст у рядку строго більший за p, де p – деяке ціле число в межах від 50 до 99.
   Необхідно знайти кількість різних гарних підрядків даного рядка.
Вхідні дані:
   У першому рядку вхідного файлу записано даний рядок, непустий і не більше чим із 105 маленьких латинських букв. У другому рядку задано ціле число 50≤p≤99.
Вихідні дані:
   У вихідний файл виведіть одне число – кількість гарних підрядків даного рядка.

Приклад вхідних та вихідних даних.
Приклад вхідних даних: 
Приклад вихідних даних:
mama
50
4

aaabaaa
80

12

MVI
Copyright MyCorp © 2024
Пошук
Календар
«  Березень 2024  »
ПнВтСрЧтПтСбНд
    123
45678910
11121314151617
18192021222324
25262728293031
Архів записів
Друзі сайту
Обдаровані діти

Хмельницькі олімпіади

НМЦ ІКТ і ДН

Портал ХОІППО

Створити безкоштовний сайт на uCoz