1. Завдання 10-11 клас (ветерани)

Задача Money. Ярослав та Мирослава мають спільну колекцію з 𝑛 монет. Як символ своєї дружби вони хочуть окремо зберігати таку пару монет, що в сумі номінальна вартість цих двох монет дає особливе число 𝑠. Підрахуйте кількість різних способів вибрати потрібну пару.

Технічні умови. Програма Money читає з пристрою стандартного введення натуральні числа 𝑠 та 𝑛, не менші за 2. У другому рядку - 𝑛 натуральних чисел — номінальні вартості монет із колекції. Усі числа (включно з числами 𝑠 та 𝑛) не перевищують 200 000. Програма виводить на пристрій стандартного виведення єдине число — кількість способів вибрати дві монети з сумарною номінальною вартістю 𝑠. Відомо, що шукана кількість не перевищує 10⁹.

Приклади

- - - - - - - - - - - - - - - - - - - - - - - -

Задача Macrohard. У компанії Macrohard працює n програмістів. Відомо, коли кожен фахівець приходить на роботу, і коли йде з неї. Директор компанії вирішив дізнатися, скільки годин протягом доби на роботі є всі працівники.

Технічні умови. Програма Macrohard читає з пристрою стандартного введення натуральне число n (n ≤ 1000) — кількість програмістів. У наступних n рядках міститься інформація про всіх працівників компанії: в кожному рядку записано по два натуральних числа — година, о котрій деякий програміст приходить на роботу, й час, коли він іде з компанії (саме в такому порядку). Жодне з цих чисел не перевищує 23. Якщо друге число не перевищує перше, це означає, що програміст залишається на ніч і йде додому наступного дня. Програма виводить на пристрій стандартного виведення єдине число — кількість годин (упродовж одного дня), коли всі програмісти перебувають у компанії.

Приклади

Пояснення до прикладу

Всі три фахівці перебувають у фірмі протягом двох годин — із 14-ї до 16-ї.

- - - - - - - - - - - - - - - - - - - - - - - -

Задача CBS. Задано шаблон, що складається з круглих дужок та знаків питання.

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

Правильна послідовність дужок (анлг. Correct Bracket Sequences) - окремий випадок послідовності з круглих дужок, що визначається таким чином:

ε (порожній рядок) є правильною послідовністю дужок;

нехай S - правильна послідовність, тоді (S) є правильна послідовність;

нехай S1, S2 - правильні послідовності, тоді S1S2 є правильна послідовність;

Приклади правильних послідовностей дужок ((()()()())), (())(()())

Технічні умови Програма Cbs читає з пристрою стандартного введення рядок довжиною не більше 10000 символів, виключно круглі дужки та знаки запитання. Програма виводить на пристрій стандартного виведення шукану величину – кількість способів по модулю 10⁹+7.

Приклад

Введення

????(?

Виведення

2

- - - - - - - - - - - - - - - - - - - - - - - -

Задача Figures. Дано набiр з n цифр вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язані використати всi цифри.

Математична підказка:

• Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.

• Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.

Технічні умови. Програма Figures читає з пристрою стандартного введення у першому рядку одне цiле число n (1 ⩽ n⩽5 · 10⁵) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна скласти з цього набору.

Приклади

Зауваження до прикладів

У першому прикладi ми можемо скласти лише одне число 0.

У другому прикладi з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способiв — це скласти наступнi числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.