1549. Варварские племена

В потерянной земле существуют два примитивных племени: Гаред и Кека. Каждый день летнего солнцестояния они собираются вместе чтобы решить, какое племя будет фаворитом богов в течении следующего года. Решение принимается по результату следующего старого ритуала:

Сначала местный духовный наставник произвольным образом выбирают три числа: n, m и k. Затем n служанок племени Гаред (на позициях 1, 2, ..., n) и m служанок из Кека (на позициях n + 1, n + 2, ..., n + m) располагаются по кругу лицом внутрь круга. Потом наставник начинает считать 1, 2, ..., k начиная с первой служанки Гаред. Как только счет дойдет до k-ой служанки, ее сразу же приносят в жертву богам. Наставник продолжает счет 1, 2, ..., k начиная со служанки, которая следует за принесенной в жертву. И снова при достижении k-ой служанки ее приносят в жертву. После принесения в жертву двух служанок, на место второй жертвы ставится новая служанка. Для установления племени, из которой будет взята новая служанка, наставник смотрит на головы только что убитых (больше ничего от них не осталось). Если головы принадлежат одному племени, то новая служанка берется из племени Гаред. Если головы принадлежат служанкам из разных племен, то новая служанка берется из Кека. Процесс жертвоприношения продолжается дальше (процесс счета и жертвоприношения происходит дважды, процесс замены происходит один раз) начиная со служанки, стоящей после той которая была вставлена в круг. Так как на каждой итерации количество служанок уменьшается на одну (два жертвоприношения и одна замена), то после n + m – 1 шагов останется только одна служанка.

Согласно традиции, племя, которому принадлежит последняя выжившая служанка, является фаворитом богов. (что сделает духовный наставник с последней служанкой – Вам знать не следует). По заданным n, m и k Вам следует установить какое племя станет фаворитом богов.

Например, вот что произойдет при n = m = 3 и k = 2 (буква "G" обозначает служанку из племени Гаред, а "K" служанку из Кека; индексы указывают на порядок, в котором служанки появляются в кругу):

1. Начальное расположение круга: G₁ G₂ G₃ K₄ K₅ K₆

Начинаем счет с G₁. Первая жертва: G₂. Вторая жертва: K₄ (заменяется на K₇).

2. Содержимое круга: G₁ G₃ K₇ K₅ K₆

Начинаем счет с K₅. Первая жертва: K₆. Вторая жертва: G₃ (заменяется на K₈).

3. Содержимое круга: G₁ K₈ K₇ K₅

Начинаем счет с K₇. Первая жертва: K₅. Вторая жертва: K₈ (заменяется на G₉).

4. Содержимое круга: G₁ G₉ K₇

Начинаем счет с K₇. Первая жертва: G₁. Вторая жертва: K₇ (заменяется на K₁₀).

5. Содержимое круга: G₉ K₁₀

Начинаем счет с G₉. Первая жертва: K₁₀. Вторая жертва: G₉ (заменяется на K₁₁).

6. Конечное содержимое круга: K₁₁

Вход. Состоит из нуля или нескольких тестов. Каждый тест состоит из трех натуральных чисел: n, m и k. Известно, что 1 ≤ n + m ≤ 2000 и 1 ≤ k ≤ 1000. Последний тест содержит n = m = k = 0 и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести "Gared" или "Keka".

Пример входа	Пример выхода
3 3 2 4 2 2 0 1 7 0 0 0	Keka Gared Keka

РЕШЕНИЕ

математика - полуинвариант

Анализ алгоритма

После каждого раунда количество людей в кругу уменьшается на 1. Посмотрим, как будет изменяться количество людей из племен в кругу после каждого раунда.

типы раундов	превая жертва	вторая жертва	введенный	изменение Гаред	изменение Кека
1	Гаред	Гаред	Гаред	-1	0
2	Гаред	Кека	Кека	-1	0
3	Кека	Гаред	Кека	-1	0
4	Кека	Кека	Гаред	+1	-2

После каждого раунда количество мужчин из племени Кека изменяется либо на 0, либо на 2. То есть их четность не меняется. В конце ритуала остается один человек. Следовательно, если последним останется представитель Кека, то изначально количество мужчин из Кека было нечетным. С другой стороны в конце останется представитель Гаред, если только число людей из Кека в начале было четным.

Пример

Рассмотрим входные данные для первого теста. Изначально в кругу стоят GGGKKK (G – Гаред, K – Кека). Последовательность раундом жертвоприношений приведена в таблице (человек, с которого начинается отсчет, подчеркнут):

состояние круга	первая жертва	вторая жертва	новый введенный
GGGKKK	GGGKKK	GGGKKK	GGKKK
GGKKK	GGKKK	GGKKK	GKKK
GKKK	GKKK	GKKK	KKK
KKK	KKK	KKK	KG
KG	KG	KG	K

Реализация алгоритма

Ответ задачи зависит от четности количества людей в круге, представимых от племени Кека. То есть достаточно проверить на четность значение m и вывести результат.

while(scanf("%d %d %d",&n,&m,&k),n+m+k)

{

if (m % 2) printf("Keka\n");

else printf("Gared\n");

}