|
5 тур - з 14.11.16 по 20.11.2016
точка входу для відправлення розв'язків
http://134.249.159.199//cgi-bin/new-client?contest_id=37
Задача 1. Олімпіада з математики (20 балів)
|
Максимальний час роботи на одному тесті:
|
1 секунда
|
|
Максимальний об’єм пам’яті:
|
64 Мб
|
|
Ім’я вхідного файлу:
|
input.txt
|
|
Ім’я вихідного файлу:
|
output.txt
|
|
|
|
Прокинувшись вранці, Петро Павлович вирішив замінити задачу складного рівня шкільної олімпіади з математики на досить просту (з метою отримання вищих результатів учнями). Прийшовши в школу, він написав умову задачі на аркуші в одному екземплярі та попросив учня Сашка до початку олімпіади зробити ще N копій. В його розпорядженні є два ксерокси, один з яких робить копію за х секунд, а другий – за y. (Дозволяється використовувати як один ксерокс, так і обидва одночасно; копію можна робити як з оригіналу, так і з копії). Допоможіть Сашкові з’ясувати, який мінімальний час йому буде потрібен, щоб виконати завдання вчителя.
Формат вхідних даних
У вхідному файлі записано три натуральних числа N, x и y, які розділені пробілом (1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).
Формат вихідних даних
Виведіть одно число – мінімальний час в секундах, необхідний для того, щоб зробити N копій.
Наприклад,
|
Вхідні дані
|
Вихідні дані
|
|
4 1 1
|
3
|
|
5 1 2
|
4
|
Задача 2. Домашня робота з математики (100 балів)
|
Максимальний час роботи на одному тесті:
|
2 секунди
|
|
Максимальний об’єм пам’яті:
|
256 Мб
|
|
Ім’я вхідного файлу:
|
input.txt
|
|
Ім’я вихідного файлу:
|
output.txt
|
Сашко не дуже любить робити домашні завдання, але на попередньому уроці математики Петро Павлович задав учням n різних завдань. Причому, робити деякі домашні завдання можна було лише після того, як виконано інші.
Для кожного завдання Сашко визначив, скільки хвилин йому потрібно, щоб його виконати. Після цього Сашко зрозумів, що виконати всі завдання він точно не встигне. Отож він вирішив зробити всі завдання окрім одного – за одне невиконане завдання вчитель нічого не скаже.
Тепер Сашку слід вибрати, яке завдання не виконувати. Допоможіть Сашку вибрати завдання, яке можна не виконувати, щоб інші завдання виконати якомога швидше.
Формат вхідного файлу
Перший рядок вхідного файлу містить цілі числа n и m — кількість завдань і кількість залежностей між завданнями (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Другий рядок містить n цілих чисел: t1, t2, . . . , tn. Число ti означає кількість хвилин, необхідних Сашку для виконання i-го завдання (1 ≤ ti ≤ 1000). Далі іде m рядків, кожен з яких містить два цілих числа. Числа a и b означають, що
завдання a слід виконати раніше аніж завдання b. Гарантується, що всі завдання можна виконати.
Формат вихідного файлу
Вивести одне число – мінімальну кількість хвилин, необхідних Сашку для виконання всіх завдань крім одного.
Наприклад
|
Вхідні дані
|
Вихідні дані
|
|
5 5
1 2 3 4 5
1 2
5 3
1 3
3 4
2 4
|
11
|
В даному прикладі Сашко може не виконувати четверте завдання. Всі інші завдання він виконає за 11 хвилин.
|
