UVa 10771

From Algorithmist
Jump to navigation Jump to search

10771 - Barbarian Tribes[edit]


There are two tribes: Gareds and Kekas. Gared maids and Keka maids are placed in a circle.

Two persons from the circle are selected (by a complicated process), and replaced by another person. If both persons were from the same tribe, the new person will be a Gared. If they were from different tribes, it will be a Keka. This process is repeat until only one person remains.

Given values of and , determine which tribe's person will remain at the end.


It is possible to answer this problem without even knowing exact details of selection process. Notice this invariant: after each elimination step, the parity of the number of Kekas maids does not change.

So, if there was an odd number of Kekas at the beginning, there'll be an odd number of them at the end, i.e. just one Keka. And if the initial number was even, no Kekas will remain.


3 3 2
4 2 2
0 1 7
0 0 0