Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
98. Игра
Жадные алгоритмыОлимпиадные задачи на русском языке
| 06/10/2006 | Личное первенство Южного Урала (E) |
| 19/11/2011 | Занятие 6 (B) |
| 14/04/2015 | Занятие 21 (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Два игрока по очереди берут по одной карточке из общей кучи. На каждой карточке написано некоторое целое число, которое может быть как положительным, так и отрицательным. Игрок, взявший карточку, может либо забрать её себе, либо отдать сопернику. В начале игры карточек на руках ни у кого нет. Когда игроки разберут все карточки, игра заканчивается и игроки считают сумму чисел на своих карточках. Игроки стараются максимизировать разность между количеством своих очков и количеством очков соперника. Напишите программу, которая определит максимально возможную разность между очками первого игрока и его соперника, если оба игрока будут действовать оптимальным образом.
Ввод
В первой строке входного файла содержится целое число `N\ (1\ ≤\ N\ ≤\ 10000)` – количество различных чисел, записанных на карточках. Далее следует `N` строк, каждая из которых содержит два целых числа `A` и `B`, разделенных пробелом; число `B\ (1\ ≤\ B\ ≤\ 10^8)` означает количество карточек, на которых написано число `A\ (|A|\ ≤\ 10^8)`.
Вывод
Вывести единственную строку, содержащую целое число – разность между количеством очков первого и второго игроков, при оптимальной игре обоих.
Пример ввода
3 1 1 2 1 3 1
Пример вывода
2
