gcj2014

Google Code Jam 2014 – Qualification Round

GCJ 应该是算法比赛里面实质上做的最好玩的一个,个人觉得,为了每年都必须保持有的衣服,虽然工作很忙,还是要参与的。

不过今年的 GCJ Qualification Round 还比较好搞,虽然最终 Large Case 的结果未出,但是基本可以确定满贯了,题目比较容易,就是第三题扫雷稍微卡壳了一下,WA 了一次。代码和数据在这里。

A. Magic Trick (6pt)

这道送分题,数字 1-16 排成 4×4,先给一个行数,打乱,再给一个行数。问两次都出现在指定行的数字,按情况输出。

太简单不解释,用 Python 写更是舒心省事。

import sys

sys.stdin = open('A-small-attempt0.in', 'r')
sys.stdout = open('a-small.out', 'w')

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

    k = int(input())
    r = [set(map(int, input().split())) for i in range(4)][k-1]

    k = int(input())
    r &= [set(map(int, input().split())) for i in range(4)][k-1]

    print('Case #%d: %s' % (
        t + 1,
        'Volunteer cheated!' if len(r) == 0
        else r.pop() if len(r) == 1
        else 'Bad magician!'
    ))

sys.stdin.close()
sys.stdout.close()

B. Cookie Clicker Alpha (8pt/11pt)

这道题也不难,单线贪心问题。刚开始你有 0 财富,每秒会产生 2 财富(连续产生非离散),给出 C/F/X,随时可以花掉 C 块钱来使得财富产生速率增加 F/秒,问最快多少时间可以积累到 X 财富。

这是一个简单的贪心过程,也没有什么技术含量,不解释直接上代码:(Python 真是舒心省事!)

import sys

sys.stdin = open('B-large.in', 'r')
sys.stdout = open('b-large.out', 'w')

for c in range(int(input())):

    (C, F, X) = map(float, input().split())
    f = 2
    t = 0
    ans = X / f
    while t < ans:
        t += C / f
        f += F
        ans = min(ans, X / f + t)

    print('Case #%d: %.7f' % (c + 1, ans))

sys.stdin.close()
sys.stdout.close()

C. Minesweeper Master (11pt/24pt)

扫雷,给出一个 RxC 的尺寸,以及雷数 M,求构造一个一击通关的雷阵。

最后的构造法很简洁,但是想出来有点慢。分情况讨论:

1. 如果 min(R, C) = 1 或者 R*C-M=1(安全格数仅一格),必然可行直接构造
2. 剩下的情况肯定是至少两行,至少两列,至少两安全格的情况:

我们通过构造可以发现最小的通关单元是角落上 4×4 的空位,而且不难发现,2, 3, 5, 7 这几个数字都构造不了的,先作排除。

其他情况我们按照这样的方法来构造:如(R=6, C=8):

gcj-2014-Q-1

我们先把 RxC 填满雷,灰色的是雷。

然后如上图我们构造 rr, cc 满足 2 <= rr <=R, 2 <= cc <= C。

我们可以看到,如果把绿色部分全部都标记为安全格,那么肯定是 OK 的。并且,这时候我们任意从上到下从左到右将黄色的地区的雷拿走(我们开始的时候),拿走的部分肯定也保证是安全的(仔细斟酌一下就知道了)。

gcj-2014-Q-2

如上图,我们在 rr 和 cc 定下来之后往黄色区域填了6 个格子,这样就构造了一个 R=6/C=8/M=24 的雷阵(绿色橙色是安全格,灰色黄色是雷区。)

此外,我们可以发现,只要 rr 和 cc 确认了,就可以产生任意一个安全格数在 (rr+cc-2)2 到 rrcc 范围的雷阵。

另外,如果 rr=2 或者 cc=2,这个范围就只有一个数(等于 2rr 或者 2cc),也就是说明如果只有两列的情况,如果是奇数是行不通的。

其他情况,所有的雷数都可以构造!

那么我们只需要遍历一下 rr 和 cc,看看 RC-M 是否在 [(rr+cc-2)2, rr*cc] 这个区间内,如果是,直接按照这个方法构造即可。

这样复杂度不会很高啦,不仔细分析了。下面是代码:

import sys

sys.stdin = open('C-large.in', 'r')
sys.stdout = open('c-large.out', 'w')


def solve(R, C, M):
    G = [['*'] * C for r in range(R)]
    if min(R, C) == 1 or R*C-M == 1:
        for m in range(R*C-M):
            G[m % R][m // R] = '.'
        G[0][0] = 'c'
        return G
    else:
        (rr, cc) = (0, 0)
        for r in range(2, R+1):
            for c in range(2, C+1):
                if r+r+c+c-4 <= R*C-M <= r*c:
                    (rr, cc) = (r, c)
                    break
            if rr:
                break
        if rr or cc:
            for r in range(rr):
                G[r][0] = G[r][1] = '.'
            for c in range(2, cc):
                G[0][c] = G[1][c] = '.'
            rem = R*C-M-rr-rr-cc-cc+4
            for r in range(2, rr):
                for c in range(2, cc):
                    if rem > 0:
                        G[r][c] = '.'
                    rem -= 1
            G[0][0] = 'c'
            return G
    return None

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

    result = solve(*map(int, input().split()))

    print('Case #%d:' % (t+1))
    if result:
        for line in result:
            print(''.join(line))
    else:
        print('Impossible')

sys.stdin.close()
sys.stdout.close()

D. Deceitful War (14pt/16pt)

最后一道题,其实还没 C 难,是一个纯粹贪心的问题,田忌赛马升级版,直接就按照田忌赛马版解释题目吧:

我是田忌,对方是齐威王,我们各有 N 匹马。正常的游戏规则是:我先出马,要将真实的战斗力告诉齐威王,然后齐威王拿一个马跟我比,谁的马赢了得一分。

本来如果正常游戏,齐威王只要足够聪明,我是占不到便宜的,先在这样的情况下算一下这样我最多能得到多少分 y。

但是我会作弊,我偷窥了所有齐威王的马的战斗力,然后我出马的时候可以报一个假的数,但是原则是齐威王按照“最优策略”出一个马跟我比的时候,输赢结果必须跟那个马真的就是这个战斗力的情况一样(譬如说我报战斗力是 0.5,齐威王出个 0.6 的马跟我比输了,这样是不行的)。再算一下在作弊的情况下我最多能得多少分 x。

注:上面的 x, y 符号跟原题不同,以我代码里面的符号编号为准。

解法:

首先正常情况下很容易处理,先把两个战斗力数组排一下序,然后遍历我的马,然后齐威王在自己可以战胜的马里面挑一个最差的拿出来比,赢不了就随便拿一个(因为这样的话剩下的一个都赢不了了),这样算出来的就 OK 了。

然后,作弊的情况下,如果我要赢,我就必须先用最差的马把齐威王的最强的马消耗掉,消耗完之后剩下的马就从强到弱出。

但是我们计算的顺序跟出马的顺序不一样,我们只关心实际比赛的匹配,顺序先不管:从小到大遍历我的马,如果能够至少赢得到齐威王的任一只马,我们就加一分,然后两只马一起拿走(最终我们控制顺序肯定可以让最后实际比的就是这一对)。如果一只都赢不了,那我们可以唬齐威王拿最强的马干掉我最弱的马,这样的话把这只马跟齐威王最强的马一起拿走,我不加分。

这样的话操作也很简单,由于时间充裕,也没有怎么做查找的又花了(本来在常规模式下应该用 map 之类的结构,在作弊模式下应当用 deque 之类的结构才能保证效率最好,但我的代码里面直接没有管,但不影响结果),代码如下:

import sys

sys.stdin = open('D-large.in', 'r')
sys.stdout = open('d-large.out', 'w')

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

    N = int(input())
    A = sorted(map(float, input().split()))
    B = sorted(map(float, input().split()))

    x = 0
    _B = B.copy()
    for a in A:
        if a > _B[0]:
            _B.pop(0)
            x += 1
        else:
            _B.pop()

    y = 0
    _B = B.copy()
    for a in A:
        lose = False
        for i in range(len(_B)):
            if _B[i] >= a:
                lose = True
                _B.pop(i)
                break
        if not lose:
            y += 1
            _B.pop()

    print('Case #%d: %d %d' % (t + 1, x, y))

sys.stdin.close()
sys.stdout.close()

然后这次比赛如无意外应该满贯了,希望是个好的开头,今年顺利把 Google 衣服拿到手。


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

原文链接:https://www.huangwenchao.com.cn/2014/04/gcj-2014-qual.html【Google Code Jam 2014 – Qualification Round】

《Google Code Jam 2014 – Qualification Round》有2个想法

  1. 楼主想问下,第二题得t<ans是什么意思啊。 我打印下了所有的时间 以例题中的C=30.0, F=2.0, X=100为例 其中all_time 是循环中的x/f+t 即总时间 t=0.000000,f=2,ans=50.000000, in loop,t=15.000000,f=4,ans=50.000000,all_time=40.000000 in loop,t=22.500000,f=6,ans=40.000000,all_time=39.166667 in loop,t=27.500000,f=8,ans=39.166667,all_time=40.000000 in loop,t=31.250000,f=10,ans=39.166667,all_time=41.250000 in loop,t=34.250000,f=12,ans=39.166667,all_time=42.583333 in loop,t=36.750000,f=14,ans=39.166667,all_time=43.892857 in loop,t=38.892857,f=16,ans=39.166667,all_time=45.142857 in loop,t=40.767857,f=18,ans=39.166667,all_time=46.323413 循环到第三次就出结果,之后的循环是什么意思? 我得思路是计算下一次循环后的总时间如果t(n)<t(n-1) n就是最后要买农场的个数,通过不等式变换得n<= xf-2c/cf , 然后计算买n个农场后 总时间

发表评论

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