gramezi
Захарел и
Бронзарел
играят
следната
игра: N
купчинки от
монети са
поставени на
масата. Дадено
е, че ако
Захарел
избере i-тата
купчинка, той
ще вземе Ai монети
от нея, а ако
Бронзарел
избере същата
купчинка, ще
вземе Bi
монети от
купчинката.
Известно е,
че всяка
купчинка има
поне max(Ai,Bi) монети.
След като
играчът е
взел монети
от някоя
купчинка,
останалите
монети от
купчинката
се изхвърлят.
Двамата
играчи се
редуват да
избират
купчинки и
вземат
монети, докато
ги изчерпят.
Захарел
започва пръв.
На края на
играта
печели този,
който е
събрал повече
монети. Ако
двамата са
събрали по равен
брой монети,
играта
завършва
наравно.
Задача
При
условие, че
Захарел и
Бронзарел
играят оптимално,
определете
броя на
монетите, които
всеки от
играчите ще
събере на края
на играта.
Под
оптимална
игра разбираме,
че всеки
играч се
стреми да
увеличи разликата
между броя на
монетите,
които той ще
събере
накрая и
броя, който
ще събере
противникът
и ако има
няколко
възможности
за това,
всеки се
стреми да
събере
повече монети.
Вход
Първият ред на входния файл gramezi.in съдържа цялото положително число N. Следващите N реда съдържат по две цели положителни числа, разделени с интервал. Тези числа задават съответните стойности на Ai и Bi.
Изход
Първият ред на изходния файл gramezi.out трябва да съдържа две цели положителни числа, разделени с интервал. Тези числа трябва да показват резултатите на Захарел и Бронзарел.
Ограничения
1 <= N <= 30
000
1 <= Ai, Bi <= 30 000
Пример
gramezi.in |
gramezi.out |
Обяснение |
4 |
9 6 |
Има
4 купчинки с
монети. Решението
е: Захарел
взема
купчинка 1 (Захарел
получава 2 монети),
тогава Бронзарел
взема
купчинка 2 (Бронзарел
взема 5 монети).
След това Захарел
взема
купчинка 3 (Захарел
получава 7 монети).
Накрая Бронзарел
взема
купчинка 4 (Бронзарел
получава 1 монета). |
Време
за работа на
програмата: 0.1 секунди
за тест.
bogdanpasoi@yahoo.com
Превод на
български:
Емил
Келеведжиев