GCJ 2015 – Qualification Problem D – Ominous Omino (计中计) – 解题报告

第四题:计中计 / Ominous Omino

Google Code Jam 2015 比赛记录:http://www.huangwenchao.com.cn/2015/04/gcj-2015-qual.html

题意,我们定义一个 X-俄罗斯方块 (X-Omino) 是由 X 个正方形块边边相接连起来的东东。

然后 Richard 和 Gabriel 在玩一个游戏:

要把若干个 X-Omino 放置到 RxC 的网格里面。

X 和 R, C 都是事先约定好的,然后由 Richard 选出一个 X-Omino (形状由 Richard 选定)。

然后 Gabriel 就要先放一个 X-Omino 到网格里面,然后试图再找任意个形状随意的 X-Omino 放进网格,最终要把网格完全占满。

Richard 和 Gabriel 都是绝顶聪明的人,如果 Gabriel 能够把网格占满那么 Gabriel 胜,否则 Richard 胜。

那么对于给定的 X, R, C,请问谁能赢得游戏。


解题报告:

这题看似复杂,其实是很容易枚举所有的情况的,但是逻辑判断必须非常仔细。

定理一:X >= 7 肯定不行

这是显然的,至少要有 7 个,Richard 就可以构造一个有一个洞的 X-Omino,这样怎么填都不可能填满。

定理二:如果 X > max(R, C) 肯定不行

这是显然的,如果 X 比网格的长宽都长,Richard 构造一个 1 * X 的长条就直接放不下了。

定理三:如果 (X + 1) // 2 > MIN( R, C ) 肯定不行

这个不太显然,但是可以说明:

我们可以通过下图的方式构造一个“最容易撑破短边”的形状。

z-omino

这样构造的形状窄边宽度即为 (X + 1) // 2,如果这个比网格的短边要大,是怎么放也放不下的。

定理四:R * C % X != 0 肯定不行

这个明显,所有的方格的数量必须要被 X 整除。

OK,有了上面这几点,我们就可以排除掉绝大部分情况的失败例子,剩下的例子,逐个枚举就可以了,下面枚举的情况,我们就假设不满足定理一到四的情况已经排除

而且后面我们还添加一个定理五:

定理五:满足定理一至四的前提下,如果将任一个形状放到网格中,网格依然连通,那么这个方案肯定是可以构造出来的

换个说法,只要总格数可以整除,因为剩下的形状任意选取,我们显然可以将整个网格填满。

**

1. X = 1 或 X = 2

肯定可以。

这个明显是可以放得下的

2. X = 3

肯定可以。

对于 X = 3,Richard 只可能构造直棍和 L 字,然后 Gabriel 总是可以将这个放到角落,然后留出的剩余空间就是连续的,也就必然可行了。

3. X = 4

如果 min(R, C) = 2 则不行,否则一定可以。

先看窄边为 2 的情况,如果 Richard 构造一个这样的形状,则必然将剩下的空间分成两份奇数的不连通区域,这就没办法填满了。

除此以外,Gabriel 总是可以将位置摆放成剩余空位是连续的,这样就必然可以填满了。

4-omino

4. X = 5

除了 3 * 5 这种情况都可以。

根据前面定理一至四的筛选,最小的网格大小是 3 * 5。如果短边大于 3,绝对可以将剩余空间构造成连通,有争议的只是短边等于 3 的情况。

5-omino

X = 5 的情况极度特殊,我们仔细看上图枚举不同的 12 种形状。

可以发现 A-G,还有 I 这合共八种形状,在短边为 3 的情况,都是可以贴边放,将剩下的留成连通的;

而 HIJK 这四种,卡在中间之后两边各留两个空位又恰好可以再加一列凑成五格;

唯独最后的 L 这种,在 3 * 5 的情况下,无论如何都无法将剩余的空位填满;

那么当短边为 3,长边大于 5 的情况下,单独讨论 L 这种即可。

可以看到,当长边为 10 的下一个情况(短边为 3 长边必须为 5 的倍数才可以满足定理四),将其移位已经可以将两边的位置凑成 5 的倍数了。

故得除了 3 * 5 之外其他都可以的结论。

5. X = 6

如果 min(R, C) = 3 则不行,否则一定可以。

参考 X = 4 的情况,构造一个下图形状的块,则当窄边为 3 的时候,两边必然均为不能被 3 整除(一边余 1 另一边余 2),故也不可能被 6 整除的两片不连通区域。

6-omino

除此以外,Gabriel 总是可以将位置摆放成剩余空位是连续的,这样就必然可以填满了。

结论:

如是一来,这道题就变成了一个简单的逻辑判断,具体实现参见例程。

不过按上面的分析,这道题用于考察边界条件的判断,可谓一绝,我的大数据应该是交挂了。

例程:
for t in range(int(input())):

    X, R, C = map(int, input().split())

    ans = True

    if X >= 7:
        ans = False
    elif X > R and X > C:
        ans = False
    elif R * C % X != 0:
        ans = False
    elif (X + 1) // 2 > min(R, C):
        ans = False
    elif X in (1, 2, 3):
        ans = True
    elif X == 4:
        ans = min(R, C) > 2
    elif X == 5:
        ans = not(min(R, C) == 3 and max(R, C) == 5)
    elif X == 6:
        ans = min(R, C) > 3

    print('Case #%d:' % (t + 1), 'GABRIEL' if ans else 'RICHARD')

原题内容:

题目链接:https://code.google.com/codejam/contest/6224486/dashboard#s=p0

Problem

An N-omino is a two-dimensional shape formed by joining N unit cells fully along their edges in some way. More formally, a 1-omino is a 1×1 unit square, and an N-omino is an (N-1)omino with one or more of its edges joined to an adjacent 1×1 unit square. For the purpose of this problem, we consider two N-ominoes to be the same if one can be transformed into the other via reflection and/or rotation. For example, these are the five possible 4-ominoes:

omino-4

And here are some of the 108 possible 7-ominoes:

omino-7

Richard and Gabriel are going to play a game with the following rules, for some predetermined values of X, R, and C:

  1. Richard will choose any one of the possible X-ominoes.
  2. Gabriel must use at least one copy of that X-omino, along with arbitrarily many copies of any X-ominoes (which can include the one Richard chose), to completely fill in an R-by-C grid, with no overlaps and no spillover. That is, every cell must be covered by exactly one of the X cells making up an X-omino, and no X-omino can extend outside the grid. Gabriel is allowed to rotate or reflect as many of the X-ominoes as he wants, including the one Richard chose. If Gabriel can completely fill in the grid, he wins; otherwise, Richard wins.

Given particular values X, R, and C, can Richard choose an X-omino that will ensure that he wins, or is Gabriel guaranteed to win no matter what Richard chooses?

Input

The first line of the input gives the number of test cases, T. T lines follow. Each contains three space-separated integers: X, R, and C.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is either RICHARD (if there is at least one choice that ensures victory for Richard) or GABRIEL (if Gabriel will win no matter what Richard chooses). Limits

Small dataset

T = 64. 1 ≤ X, R, C ≤ 4.

Large dataset

1 ≤ T ≤ 100. 1 ≤ X, R, C ≤ 20.

Sample
Input 

4
2 2 2
2 1 3
4 4 1
3 2 3

Output 

Case #1: GABRIEL
Case #2: RICHARD
Case #3: RICHARD
Case #4: GABRIEL

In case #1, Richard only has one 2-omino available to choose — the 1×2 block formed by joining two unit cells together. No matter how Gabriel places this block in the 2×2 grid, he will leave a hole that can be exactly filled with another 1×2 block. So Gabriel wins.

In case #2, Richard has to choose the 1×2 block, but no matter where Gabriel puts it, he will be left with a single 1×1 hole that he cannot fill using only 2-ominoes. So Richard wins.

In case #3, one winning strategy for Richard is to choose the 2×2 square 4-omino. There is no way for Gabriel to fit that square into the 4×1 grid such that it is completely contained within the grid, so Richard wins.

In case #4, Richard can either pick the straight 3-omino or the L-shaped 3-omino. In either case, Gabriel can fit it into the grid and then use another copy of the same 3-omino to fill in the remaining hole.


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2015/04/gcj-2015-qual-d.html【GCJ 2015 – Qualification Problem D – Ominous Omino (计中计) – 解题报告】

《GCJ 2015 – Qualification Problem D – Ominous Omino (计中计) – 解题报告》有3个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注