Это простая версия задачи. Единственное отличие состоит в том, что в этой версии каждый должен дать конфеты ровно одному человеку и получить конфеты ровно от одного человека. Обратите внимание, что посылка не может пройти обе версии задачи одновременно. Вы можете делать взломы, только если обе версии задачи решены.
После экзамена Daniel и его друзья собираются устроить вечеринку. Все придут с конфетами.
На вечеринке будут присутствовать \(n\) человек. Изначально у \(i\)-го человека есть \(a_i\) конфет. Во время вечеринки они будут обмениваться конфетами. Для этого они выстроятся в произвольном порядке и каждый из них сделает следующее ровно один раз:
- Выберет целое число \(p\) (\(1 \le p \le n\)) и неотрицательное целое число \(x\), затем даст \(2^{x}\) конфет \(p\)-му человеку. Заметим, что человек не может отдать больше конфет, чем у него есть в данный момент (он мог получить конфеты от кого-то другого), и он не может отдать конфеты самому себе.
Daniel любит справедливость, поэтому он будет счастлив тогда и только тогда, когда каждый получит конфеты от ровно одного человека. В то же время его друг Tom любит среднее, поэтому он будет счастлив тогда и только тогда, когда у всех людей будет одинаковое количество конфет после всех обменов.
Определите, существует ли способ обменяться конфетами так, чтобы Daniel и Tom были счастливы после обменов.
Выходные данные
Для каждого набора входных данных выведите «Yes» (без кавычек), если существует способ обменяться конфетами так, чтобы Daniel и Tom были счастливы, и выведите «No» (без кавычек) в противном случае.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительный ответ.
Примечание
В первом наборе входных данных:
- Первый человек даёт \(1\) конфету третьему человеку;
- Второй человек даёт \(2\) конфеты первому человеку;
- Третий человек даёт \(1\) конфету второму человеку.
Тогда у всех трёх человек есть по \(3\) конфеты.
Во втором наборе входных данных:
- Пятый человек даёт \(4\) конфеты первому человеку, и теперь у первого человека есть \(5\) конфет;
- Первый человек даёт \(2\) конфеты третьему человеку;
- Третий человек даёт \(2\) конфеты пятому человеку;
- Четвёртый человек даёт \(2\) конфеты второму человеку;
- Второй человек даёт \(1\) конфету четвёртому человеку.
Тогда у всех трёх людей есть по \(3\) конфеты. Обратите внимание, что вначале первый человек не может дать \(2\) конфеты третьему человеку, потому что у него есть только \(a_1=1\) конфета. Но после того, как пятый человек дал ему \(4\) конфеты, он может это сделать, потому что сейчас у него есть \(1+4=5\) конфет.
В третьем наборе входных данных невозможно сделать так, чтобы у всех людей было одинаковое количество конфет.
В четвёртом наборе входных данных первый человек даёт второму человеку \(1024\) конфеты, и второй также даёт \(1024\) конфеты первому человеку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
2 4 3
5
1 2 3 4 5
6
1 4 7 1 5 4
2
20092043 20092043
12
9 9 8 2 4 4 3 5 1 1 1 1
6
2 12 7 16 11 12
|
Yes
Yes
No
Yes
No
No
|