Вітаю Вас, Гість

Задача A. "Цукерки"

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

   На столі стоять три вази з цукерками. В лівій вазі лежить A цукерок, в середній вазі - В цукерок, в правій вазі відповідно С цукерок. Степан зїдає одну цукерку з лівої вази, потім - одну цукерку з середньої вази, потім з правої, середньої, лівої, середньої, правої, середньої і т.д. (зліва направо, потім наліво, знову направо і т.д.).
   Якщо Степан хоче взяти цукерку з якоїсь вази, а там її немає, то він засмучується і йде спати. Визначте скільки цукерок зїсть Степан.

   Вхідні дані:
   Дано 3 цілих невід'ємних числа A, B, C (A+B+C ≤ 2*109) кількість цукерок відповідно в лівій, середній та правій вазі.

   Вихідні дані:
   Oдне число - кількість цукерок, які з'їв Степан.

Приклади

Вхідні дані   Результат роботи
3
3
3
7

 

 

Задача B. "Вступна кампанія"

 

Обмеження часу: 1000 мс
Обмеження пам'яті: 256 M
Ім'я файлу, який містить вхідні дані:
campaign.in
Ім'я вихідного файлу: campaign.out

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

   Вхідні дані:
   Перший рядок вхідного файлу містить два розділених пропуском числа N і M (1 ≤ N ≤ 105, 1 ≤ M ≤ 10) - кількість абітурієнтів та приймальних вікон відповідно.
   Другий рядок вхідного файлу містить N цілих додатних чисел Ai (1 ≤ Ai ≤ 105) - час заповнення анкети i-им абітурієнтом в черзі. Числа розділені одиночними пробілами.
   Третій рядок вхідного файлу містить M цілих позитивних чисел Bj (1 ≤ Bj ≤ 105) - час заповнення електронної форми в j-му приймальному вікні. Числа розділені одиночними пробілами.

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

   Пояснення:
   Перший приклад: Перший абітурієнт пройде в єдине приймальне вікно і подасть документи за 7 одиниць часу. Після цього другий абітурієнт пройде у вікно, що звільнилося і подасть документи за 5 одиниць часу. Приймальне вікно звільниться через 7 + 5 = 12 одиниць часу.
   Другий приклад: Перший і третій абітурієнти пройдуть в перше приймальне вікно, другий - у друге.

 

Приклади

Вхідні дані   Результат роботи
2 1
7 4
5
12

 
3 2
5 7 100
1 10
105

 

 

Задача C. "Красивий ряд"

 

Обмеження часу: 3000 мс
Обмеження пам'яті: 256 M
Ім'я файлу, який містить вхідні дані:
beauty.in
Ім'я вихідного файлу: beauty.out

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

   Вхідні дані:
   В першому рядку вхідного файлу знаходиться число N (2 ≤ N ≤ 20). В наступному рядку записані N цілих невід'ємних чисел, кожне з яких не перевищує 109.

   Вихідні дані:
   Виведіть кількість способів розташувати усі N чисел в красивий ряд.

   Пояснення:
   У прикладі 5 = 123 i 1 = 13, 5 = 1012 i 6 = 1102, тому ряди 1 5 6 і 6 5 1 красиві.

   Оцінювання:
   Для 25% балів N ≤ 4
   Для 50% балів N ≤ 10

Приклади

Вхідні дані   Результат роботи
3
5 1 6
2
 

 

Задача D. "Шоколадна фабрика "ПанСте""

 

Обмеження часу: 1000 мс
Обмеження пам'яті: 256 M
Ім'я файлу, який містить вхідні дані:
factory.in
Ім'я вихідного файлу: factory.out

   Степан придбав вигідно шоколадну фабрику, яку одразу перейменував на "ПанСте". Фабрика виробляє безліч різних солодощів. Іноді Степан роздає солодощі безкоштовно. Перед фабрикою утворюється довжелезний ряд діточок і кожному що-небудь він вручає із солодощів.
   Скоро настане черговий з таких досить рідкісних випадків. На цей раз було вирішено роздавати цукерки. Фабрика виробляє N різних видів цукерок. Степан збирається віддати кожній дитині набір з N-1 штук різних цукерок. Біда тільки в тому, що кількості цукерок різних видів можуть різнитися, і стає важко підрахувати, скільком дітям дістанеться подарунок при такій схемі в найкращому випадку. Ось це вам і доведеться зробити.

   Вхідні дані:
   В першому рядку вхідного файлу знаходиться число N (2 ≤ N ≤ 10000) - кількість різних видів цукерок. i-ий з наступних N рядків містить одне число - кількість цукерок i-ого типу.
   Кількість цукерок одного типу буде в діапазоні від 1 до 500 000 000 включно.

   Вихідні дані:
   Виведіть одне число - максимальну кількість комплектів з N-1 цукерок, яку можна отримати, якщо розподіляти цукерки оптимально.

   Пояснення:
   Пронумеруємо цукерки, починаючи з 0. Можна зробити 10 комплекиів (0, 1) і 3 комплекти (1, 2).

Приклади

Вхідні дані   Результат роботи
3
10
13
4
13


 

 

Задача E. "Дужковедення"

 

Обмеження часу: 200 мс
Обмеження пам'яті: 256 M
Ім'я файлу, який містить вхідні дані:
bracket.in
Ім'я вихідного файлу: bracket.out


   У поточному навчальному році в Ужляндській гімназії №2015 ввели експериментальний факультатив по дужковеденню, головною темою якого є правильні дужкові послідовності.
   Формально правильну дужкову послідовність можна описати наступними правилами:

  • порожня послідовність «» є правильною дужковою послідовністю;
  • якщо «A» і «B» - правильні дужкові послідовності, то і послідовність «АВ», отримана конкатенацією (зчепленням) однієї послідовності до іншої є правильною дужковою послідовністю;
  • якщо «А» - правильна дужкова послідовність, то й «(А)», тобто послідовність, взята в дужки, також є правильною дужковою послідовністю;
  • інших правильних дужкових послідовностей не існує.

   Наприклад, послідовності «()», «(()) ()» і «(() ())» є правильними дужковими послідовностями, а «)», «(((() (» і «(()» - ні.
  Завтра K-й раз проводиться заняття факультативу. Викладач планує запропонувати завдання на обчислення числа способів вибору рівно K дужок, що йдуть поспіль, із заданої (не обов'язково правильної) дужкової послідовності так, щоб отримана послідовність була правильною дужковою послідовністю. На попередніх заняттях ви добре засвоїли навчальний матеріал і хочете потренуватися, щоб на факультативному занятті успішно впоратися із завданням викладача.

   Вхідні дані:
   Перший рядок вхідного файлу містить два розділених пропуском цілих числа N і K (1 ≤ K ≤ N ≤ 105) - довжину дужкової послідовності викладача і порядковий номер завтрашнього заняття.
   Другий рядок вхідного файлу містить послідовність з N символів, кожен з яких відкрита '(' (ASCII 40) або закрита дужка ')' (ASCII 41), - дужкова послідовність викладача.

   Вихідні дані:
   Єдиний рядок вихідного файлу має містити одне ціле число - кількість способів, якими можна вибрати рівно K дужок, що йдуть поспіль, для отримання правильної дужкової послідовності.

   Пояснення:
   Перший приклад: Існує 4 способи вибору 2 дужок, що йдуть поспіль: «((», «()», «))» і «)(». З них тільки одна «()» є правильною дужковою послідовністю.
   Другий приклад: Якщо починати з першої або з третьої дужки, то можна отримати таку правильну дужкову послідовність:«()()»

Приклади

Вхідні дані   Результат роботи
5 2
(())(
1
 
6 4
()()()
2