e-olymp 176. Выборы вождя

Задача взята с сайта e-olymp

Условие

Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.
Старейшины орков всегда наблюдают за выборами и любят предугадывать кто победит на них. Однако далеко не всегда можно предсказать не то, что общую победу на выборах, но даже победителя в одном конкретном бою. Конечно же все зависит от силы сражающихся – кто сильнее, тот и победит, однако в случае равенства сил может победить любой из них – тут уж как звезды станут.
Старейшины обратились к вам с просьбой написать программу для определения количества претендентов, которые могут стать вождями.

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

В первой строке входного файла записано количество [latex]N[/latex] претендентов на звание вождя в этом году [latex]\left(1 \leq N \leq 1000000 \right)[/latex], а во второй – [latex]N[/latex] целых чисел в пределах от [latex]1[/latex] до [latex]10000[/latex], каждое из которых определяет силу соответствующего кандидата.

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

Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.

Тесты

Inputs Outputs
1 5
1 2 3 4 5
1
2 6
2 2 2 2 2 2
6
3 6
3 2 1 3 1 1
2
4 0 0
5 1
5
1
6 10
712 1056 783 856 783 822 1056 322 543 222
2
7 20
10 30 70 80 90 20 90 40 60 40 80 90 10 30 60 50 30 10 20 30
3

Код

Решение

Условие задачи на первый взгляд довольно устрашающее из-за своего объема, но в нем стоит выделить главный момент — вождем становится самый сильный из орков, так как он победит все поединки, а если сила «орков-победителей» равна, то победить может любой из них. Таким образом, находим самого сильного(сильных) из орков. Для этого при каждом вводе силы орка сравниваем ее с максимальным значением, которое изначально было равно [latex]0[/latex] и если она больше, то присваиваем максимальному значению значение силы. Так же нужна проверка на равенство элементов максимуму, ведь если максимальных элементов будет больше чем один, то кандидатов будет тоже больше одного.

Ссылки

One thought on “e-olymp 176. Выборы вождя

Добавить комментарий