2013年7月6日 星期六

10771 - Barbarian tribes



  Barbarian tribes  



在失落土地上有兩個原始的部落存在,分別為  GaredsKekas。每年夏至他們會彼此競爭決定哪個部落將會在剩下的一年中受到神靈的喜愛,根據一個古老的儀式:


首先,當地長老會選擇三個隨機的整數 n, m, k 表示有 n 個 Gared 的少女(編號 1 ... n) 以及 m 個 Keka 的少女(編號 n+1 ... n+m),她們面朝內排成一圈。接著,由長老開始數 1, 2, ..., 從 Gared 的少女開始數,當第 k 個少女被點時,立即地將她做為祭品奉獻給神,長老將會繼續數 k 個人,然後將這少女也做為祭品。

每當兩個祭品被選出,第二位祭品的位置將會被新的少女替補。而替補的少女由長老決定哪個部落的少女替補。如果兩個祭品來自於同一個部落,將會由 Gared 的少女替補。反之,將會由 Keka 的少女來替補。這個處理將會進行一次又一次,而每次都會從上一次被替補的位置開始點,而每一次將會少一名少女,在 n + m - 1 次之後,將只會剩下一名少女。

根據傳統,最後那位少女所屬部落將會受到神的眷顧。然而,現在寫個程式,根據給定的 n, m, k,印出幸運的部落。



例如 :
n = m = 3, k = 2 ( ``G'' 代表一名 Gared 少女、 ``K''代表一名 Keka 少女、下標是編號)



  1. 一開始圈的內容為 : G1 G2 G3 K4 K5 K6
    從 G1開始數,第一個祭品 G2. 第二個祭品 K4 (被 K7 遞補).
  2. 圈的內容為 : G1 G3 K7 K5 K6
     從 K5開始數,第一個祭品 K6. 第二個祭品 G3 (被 K8 遞補).
  3. 圈的內容為 : G1 K8 K7 K5
    從 K7開始數,第一個祭品 K5. 第二個祭品 K8 (被 G9 遞補).
  4. 圈的內容為 : G1 G9 K7
     從 K7開始數,第一個祭品 G1. 第二個祭品 K7 (被 K10 遞補).
  5. 圈的內容為 : G9 K10
      從 G9開始數,第一個祭品 K10. 第二個祭品 G9 (被 K11 遞補).
  6. 最後只剩下 : K11


Input 

包含多筆測資,每筆測資只有一行三個整數 n, m, k其中  1 \leqslant n + \leqslant 2000 and 1 \leqslant k \leqslant 1000

最後一筆
n = m = k = 0 為結束,此筆測資不用處理。


Output 

根據每組測資,輸出 "Gared""Keka"。表示受到眷顧的部落

Sample Input 

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

Sample Output 

Keka
Gared
Keka



Author: Salvador Roura

沒有留言:

張貼留言