ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2008, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Банковский кризис

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Межбанковский кредитный рынок оказывает большое влияние на функционирование всех банков. На этом рынке банки могут получить краткосрочный кредит у других банков под самый низкий процент. Когда этот рынок был парализован, многие банки столкнулись с проблемой исполнения текущих обязательств. Центральные банки всех стран договорились поддержать мировую финансовую систему путём предоставления банкам неограниченных кредитов. Не обошлось и без протекционистских мер — центральный банк каждой конкретной страны обязался предоставлять такие кредиты только банкам, зарегистрированным в этой же стране. Более того, чтобы избежать спекуляций, решено было поддержать только «ответственные» банки, то есть те, что кредитуют банки в той же стране. Но спекулятивные банки нашли лазейку, позволяющую им получить такой статус. Они просто выкупили долги местных банков, сделанные до даты оглашения плана.
Зная ситуацию на межбанковском рынке на эту дату, определите максимальное количество банков, которые могут получить дополнительную ликвидность от центральных банков. Вы можете считать, что определяющим качеством каждого банкира является жадность, поэтому он всегда согласится на деньги сегодня, даже если это лишит его больших денег завтра. Банки могут выкупать долги других банков только целиком.

Исходные данные

В первой строке записано число n — общее количество банков, представленных на межбанковском рынке (2 ≤ n ≤ 1000). Каждая из следующих n строк содержит пары чисел ci, vi — код страны (1 ≤ ci ≤ 100) и размер свободных средств (0 ≤ vi ≤ 109) i-го банка. В следующей строке указано число m — количество активных контрактов на межбанковском рынке (0 ≤ m ≤ 10000). В следующих m строках перечислены эти контракты в формате: порядковый номер банка-кредитора в предыдущем списке, порядковый номер банка-должника, сумма (на сумму распространяются те же ограничения, что и на размер свободных средств). Покупать долги банки могут только на свободные средства, имеющиеся у них изначально; на средства, вырученные от продажи долга, покупать долги нельзя.

Результат

Выведите одно число — максимальное количество банков, удовлетворяющих требованиям плана спасения экономики.

Пример

исходные данныерезультат
5
1 100000
1 200000
1 300000
2 400000
2 500000
4
1 2 200000
1 3 200000
2 4 500000
3 5 500000
3

Замечания

В данном примере изначально только банк 1 является «ответственным». Банк 2 может выкупить долг банка 3 банку 1 — у него для этого достаточно свободных средств. В результате банк 3 будет должен 200000 банку 2, а банк 2 — 200000 банку 1. После этого банк 1 останется «ответственным», так как он по-прежнему кредитует банк 2. Также «ответственным» может стать банк 5 — для этого ему нужно выкупить долг банка 4 банку 2.
Автор задачи: Павел Атнашев
Источник задачи: NEERC 2008, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1652. Банковский кризис