2013年7月9日 星期二

11311 - Exclusively Edible


Problem E

EXCLUSIVELY EDIBLE

Hansel 和 Gretel 很喜歡蛋糕,特別是 Wolfgang Puck 餐廳所賣的 "格子蛋糕",它擁有 mn 塊不同的蛋糕,可以當作是一個 2D m x n 的蛋糕,如上圖所示。

Hansel 和 Gretel 唯獨不喜歡格子蛋糕上有一塊上有 Scrumptious Caramel Topping (如上圖咖啡色的就是美味的焦糖蛋糕),Wolfgang Puck 繼承他的已經去逝曾曾祖母的焦糖蛋糕,這就是為什麼焦糖蛋糕會出現在他的食譜中。


Hansel 和 Gretel 都不希望得到那個"壞"蛋糕(指得是焦糖蛋糕),因此他們會根據下面的方始決定誰會拿到那塊壞蛋糕:首先由 Hansel 在格子線上切一刀,並且兩個人互相交換做這個舉動,直到焦糖蛋糕被迫被其中一個人拿走。

例如:有一個 2 x 3 的格式蛋糕,下面的圖示將會根據以下的操作步驟。


  • I.   Hansel 切最左邊的那列 (column). (換 Gretel 切 2 x 2 的蛋糕)
  • II.  Gretel 切最左邊的那列(column). (換 Hansel 切 1 x 2 的蛋糕.)
  • III. Hansel 切掉最下面的那塊. (Gretel 只能拿焦糖蛋糕)



    一系列的操作將決定 Hansel 或 Gretel 誰拿到壞蛋糕

    Hansel 和 Gretel 已經吃過很多格子蛋糕,同時也玩過這遊戲好幾次,因此他們在開始前就知道誰將會拿走壞蛋糕。事實上,如果 Gretel 知道有策略可確保 Hansel 拿到壞蛋糕,而 Gretel 便會這麼做,同理 Hansel 也知道這個策略。

    給一個蛋糕以及焦糖蛋糕的位置,問誰將會拿到壞蛋糕。

    Input

    第一行 有一個整數 t (1 ≤ t ≤ 100),表示接下來會有多少組測資。

    每組測資有四個整數  m n r c (以空白區隔),m, n (2 ≤ m, n ≤ 48) 表示蛋糕的寬長,而 (r, c) (0 ≤ rm-1, 0 ≤ cn-1) 表示焦糖蛋糕的位置。

    Output

    對於每組測資輸出一行名字, 誰將會拿到壞蛋糕。Hansel 動第一次刀,而 Hansel 和 Gretel 總會使用最佳策略去切蛋糕,每一次 "切" 的時候一定是直線,且確保一定會分成兩塊。

    Sample Input

    2
    2 3 0 2
    11 11 5 5
    

    Output for the Sample Input

    Gretel
    Hansel
    

    Darko Aleksic
    Calgary Collegiate Programming Contest 2007
  • 沒有留言:

    張貼留言