HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Бинарная биржа

Section problems

• Анаграмма
• Анаграмма
• Асимптотика
• Асимптотика
• Атбаш
• Багетная мастерская
• 1
• Банковский вклад
• Бинарная биржа
• Ближайшее число
• Ближайший больший справа
• Большее число
• Большее число
• Бонни и Клайд
• Босс
• 1
• Бронзовый призёр

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 4000/4000/4000/4000 ms. Memory limit 65536/65536/65536/65536 Kb.

Бинарная биржа
Бинарная биржа
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Бинарная биржа осуществляет операции по обмену валюты по фиксированным курсам. Существуют два варианта курсов валют на бирже:

  • Курс «1 CA = B CB» означает, что количество N валюты CA можно обменять на количество (N × B) валюты CB. Например, 12.5 российских рублей по курсу «1 RUB = 2 JPY» можно обменять на 25 японских йен.
  • Курс «A CA = 1 CB» означает, что количество N валюты CA можно обменять на количество (N / A) валюты CB. Например, 48 российских рублей по курсу «128 RUB = 1 GBP» можно обменять на 0.375 фунта стерлингов.

Особенность бинарной биржи заключается в том, что во всех действующих на ней курсах обмена валют величины A и B являются степенями двойки.

Вы пришли на бинарную биржу, имея при себе один российский рубль (1 RUB). Можете ли вы, правильно обменивая валюту по действующим курсам, получить неограниченно большое количество российских рублей?

Входные данные

Первая строка содержит целое число N (0 ≤ N ≤ 1000) — количество курсов обмена валюты на бинарной бирже.

Следующие N строк описывают курсы обмена валюты. Каждая из них содержит целое число A, идентификатор валюты CA, знак равенства, целое число B и идентификатор валюты CB (1 ≤ A, B ≤ 1024).

Числа A и B являются степенями двойки, по меньшей мере одно из чисел A и B равно 1. Идентификаторы валют состоят из трёх заглавных латинских букв и не совпадают. Каждая упорядоченная пара идентификаторов встречается во входных данных не более одного раза.

Выходные данные

Если на бирже возможна цепочка обменов, позволяющая в итоге обменять 1 рубль на большее количество рублей, выведите YES. В противном случае выведите NO.

Примеры

Входные данные
2
1 USD = 32 RUB
64 RUB = 1 USD
Выходные данные
NO
Входные данные
7
1 CNY = 1 BGN
1 RUB = 4 CNY
32 RUB = 1 BGN
64 RUB = 1 USD
8 CNY = 1 RUB
1 BGN = 16 RUB
1 USD = 8 CNY
Выходные данные
YES

Примечание

В примере #2 можно выполнить следующую цепочку обменов: 1 RUB 0.015625 USD 0.125 CNY 0.125 BGN 2 RUB.

Для отправки решений необходимо выполнить вход.

www.contester.ru