1 тур - з 6.11 по 13.11.2017
точка входу для відправлення розв'язків http://134.249.159.199//cgi-bin/new-client?contest_id=43
(скачати)
Задача 1. Сума дробів (20 балів)
Ім'я вхідного файлу: input.txt
Ім'я вхідного файлу: output.txt
Ліміт часу: 1с.
Визначте суму двох правильних дробів a / b та c / d, чисельник та знаменник яких є цілим числом. Результат подайте у вигляді правильного нескоротного дробу - чисельник та знаменник. Якщо в результаті отримується ціле число, то запишіть єдине число.
Вхідні дані
В одному рядку містяться a, b, c, d - чисельники та знаменники дробів. Усі числа цілі, додатні та не перевищують 1000.
Вихідні дані
Чисельник та знаменник шуканого дробу або ціле число.
Приклад 1
|
Приклад 2
|
Вхідні дані
|
Вхідні дані
|
1 2 1 4
|
3 4 1 4
|
Вихідні дані
|
Вихідні дані
|
3 4
|
1
|
Задача 2. Скарбничка (100 балів)
Ім'я вхідного файлу: input.txt
Ім'я вхідного файлу: output.txt
Ліміт часу: 1с.
Задано вагу E пустої скарбнички та її F з монетами. У скарбничці можуть знаходитись монети N видів, для кожного виду відома цінність Pi і вага Wi однієї монети. Знайти мінімальну і максимальну суми грошей, які можуть знаходитись у скарбничці.
Вхідні дані
У першому рядку знаходяться числа E і F, у другому - число N, у наступних N рядках - по два числа, Pi и Wi. 1 ≤ E ≤ F ≤ 10000, 1 ≤ N ≤ 500, 1 ≤ Pi ≤ 50000, 1 ≤ Wi ≤ 10 000, всі числа цілі.
Вихідні дані
Виводяться два числа через пропуск - мінімальна і максимальна суми. Якщо скарбничка не може мати точно задану вагу при умові, що вона наповнена монетами заданих видів, - вивести "This is impossible.".
Приклад 1
|
Приклад 2
|
Приклад 3
|
Вхідні дані
|
Вхідні дані
|
Вхідні дані
|
1000 1100
|
1000 1010
|
1000 2000
|
2
|
2
|
1
|
1 1
|
6 3
|
10 3
|
5 2
|
2 2
|
|
|
|
|
Вихідні дані
|
Вихідні дані
|
Вихідні дані
|
100 250
|
10 16
|
This is impossible.
|
|
|
|
|