Problem E

EXCLUSIVELY EDIBLE

Hansel and Gretel like cakes, but especially the so called �grid cake" served in Wolfgang Puck's restaurants. It is made of mn pieces of different cakes, resembling a 2D m-by-n grid when looked at from above (hence the name).

The only thing that Hansel and Gretel do not like about grid cakes is that each of them has to contain a piece of the Scrumptious Caramel Topping cake. (Image of a three-by-four grid cake with brown Scrumptious Caramel Topping cake is shown) It turns out that the only reason Wolfgang Puck has the Scrumptious Caramel Topping cake in his recipe book is because he inherited it from his late great-great-grandmother.

Neither Hansel nor Gretel want to have the "bad" piece in their portion of the cake, so they came up with the following way to decide who gets the bad piece: first Hansel cuts a piece of the cake along the grid lines, then Gretel does the same and they keep alternating until there is only the Scrumptious Caramel Topping cake piece left and one of them is forced to take it.

For example, with a two-by-three grid cake, the illustrations below show the following steps:

I. Hansel cuts the leftmost column. (Gretel is left with a two-by-two grid cake.)

II. Gretel cuts the leftmost column. (Hansel is left with a one-by-two grid cake.)

III. Hansel cuts the bottom square off. (Gretel is left with the piece of Scrumptious Caramel Topping cake.)

A sequence of cuts to determine whether Hansel or Gretel is getting the bad piece.

Hansel and Gretel have eaten many grid cakes together and have played this game so many times that they know who will take the bad piece before starting. In fact, if they observe Hansel will take the bad piece, then Gretel knows a strategy to ensure Hansel takes the bad piece. Hansel also knows this strategy.

Given the original cake and position of the Scrumptious Caramel Topping cake piece in the grid, who will take the bad piece?

Input

The first line of the input file contains a number t (1 ≤ t ≤ 100), the number of test cases. Then t lines follow, each containing m n r c (separated by spaces) where m and n (2 ≤ m, n ≤ 48) are the width and the length of the cake and (r,c) is the zero-based position of the Scrumptious Caramel Topping cake piece in the grid cake (0 ≤ r ≤ m-1, 0 ≤ c ≤ n-1).

Output

For each test case print the name of the person that gets the bad piece assuming that Hansel makes the first cut and that Hansel and Gretel always cut the cake at an optimal location (trying not to get the Scrumptious Caramel Topping cake piece). Note that "cut" here refers to a straight line cut (along a grid line) that separates the cake into two pieces.

Sample Input

2
2 3 0 2
11 11 5 5

Output for the Sample Input

Gretel
Hansel

考慮一下狀態，共有 [50][50][50][50] 蛋糕的長寬，以及焦糖蛋糕位置。

窮舉每一刀的切割位置，進行轉移。

#include <stdio.h>
#include <string.h>
char dp[50][50][50][50] = {};
char used[50][50][50][50] = {};
char dfs(int n, int m, int r, int c) {
    if(n == 1 && m == 1)
        return 0;
    if(used[n][m][r][c])
        return dp[n][m][r][c];
    used[n][m][r][c] = 1;
    char &val = dp[n][m][r][c];
    int i;
    for(i = 1; i < n; i++) {// 0...i-1, i...n-1
        if(r < i)
            val |= !dfs(i, m, r, c);
        else
            val |= !dfs(n-i, m, r-i, c);
        if(val) return val;
    }
    for(i = 1; i < m; i++) {// 0...i-1, i...m-1
        if(c < i)
            val |= !dfs(n, i, r, c);
        else
            val |= !dfs(n, m-i, r, c-i);
        if(val) return val;
    }
    return val;
}
int main() {
    int testcase;
    int n, m, r, c;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d %d", &n, &m, &r, &c);
        char flag = dfs(n, m, r, c);
        puts(flag ? "Gretel" : "Hansel");
    }
    return 0;
}

我要檢舉

#11311#Exclusively Edible#博弈

台長： Morris

您可能對以下文章有興趣

[UVA][IDA*] 11163 - Jaguar King

[UVA] 11140 - Little Ali's Little Brother

[UVA][dp] 12001 - UVa Panel Discussion

[UVA][二分圖圖色] 11080 - Place the Guards

人氣(1,090) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][maxflow] 11419 - SAM I AM
此分類上一篇:[UVA] 11348 - Exhibition

回應(0)