Back to home

Google Jam 2014 资格赛

简介

Google 每年的线上编程赛。https://code.google.com/codejam/

Problem A. Magic Trick

参与者在摆放好的卡牌中选择一张卡牌,告诉你那张卡牌的行数,然后再来一轮。你就根据出现的频次输出可能的卡牌。也有可能参与者给了错误的行数(存在多种可能性)或者作弊(两次报数的卡牌行中没有重复出现的)。

1 ≤ T ≤ 100. 1 ≤ both answers ≤ 4. Each number from 1 to 16 will appear exactly once in each arrangement.

输入:

  • 例子数

    • 第一轮
    • 选得第几行
    • 卡牌内容
    • 第二轮
    • 选得第几行
    • 卡牌内容
3
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 5 4
3 11 6 15
9 10 7 12
13 14 8 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

解题(直接使用Python内置的set集合,得到重复出现的卡牌):

#!/usr/bin/env python
# encoding: utf-8


import sys


def main():
    times = int(sys.stdin.readline())
    for case_n in xrange(1, times+1):
        r = int(sys.stdin.readline())
        cards1 = set([map(int, sys.stdin.readline().split()) for i in xrange(4)][r-1])
        r = int(sys.stdin.readline())
        cards2 = set([map(int, sys.stdin.readline().split()) for i in xrange(4)][r-1])
        diff = cards1.intersection(cards2)
        diff_len = len(diff)
        if diff_len == 1:
            print "Case #%d: %d" % (case_n, diff.pop())
        elif diff_len > 1:
            print "Case #%d: Bad magician!" % case_n
        else:
            print "Case #%d: Volunteer cheated!" % case_n


if __name__ == "__main__":
    main()

Problem B. Cookie Clicker Alpha

一个之前很火网页游戏,点击网页上的饼干,你就能获得一定数量(初始速率为2)饼干。消除癖玩家最爱三点,消除,得分,成就感。
还有一个可选策略,拿一定数量的饼干兑换一个饼干农场以增加饼干获得速率。于是你的问题就是为了在最短的时间内获得一定数量的饼干,到底是直接获得饼干,还是兑换成饼干农场增加获取速率呢?

1 ≤ T ≤ 100.

Small dataset

1 ≤ C ≤ 500. 1 ≤ F ≤ 4. 1 ≤ X ≤ 2000. Large dataset

1 ≤ C ≤ 10000. 1 ≤ F ≤ 100. 1 ≤ X ≤ 100000.

输入:

  • 例子数
    • 兑换成农场的饼干开销,农场生产速率,需要得到多少饼干
4
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0

解题(假设一开始购买的农场数为0,然后计算总共达到目的数量的耗时,然后依次增加农场数量,计算时间,比较后取最短):

#!/usr/bin/env python
# encoding: utf-8


from __future__ import division


import sys


def counter():
    n = 0
    while True:
        yield n
        n += 1


def dbuy(c, f, x, N=2):
    # 30, 1, 2
    cost = None
    ctime = c/N
    cost_tb = [0]
    for i in counter():
        prod = N+f*i
        ctime = cost_tb[-1]
        if cost is None:
            cost = x/prod + ctime
        elif cost >= x/prod + ctime:
            cost = x/prod + ctime
        else:
            break
        cost_tb.append(c/prod+ctime)
    return cost


def main():
    times = int(sys.stdin.readline())
    for case_n in xrange(1, times+1):
        c, f, x = map(float, sys.stdin.readline().split())
        print "Case #%d: %0.7f" % (case_n, dbuy(c, f, x))


if __name__ == "__main__":
    main()

Problem C. Minesweeper Master

扫雷。要求给出的长宽和雷数,要求输出一种点击一次就能通关的布局。

比如有这样一种布局,*是雷,.是空白(八个相邻位置有几个雷就显示几的数字),c是点击位置

*..*...**.
....*.....
..c..*....
........*.
..........

在点击后出现的结果是(周围有雷的空白位置不能再次展开,所以导致无法一键通关。

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此题没做,因为看到通过率较低(45%),所以跳过了。我的目标是拿25pt入围即可。:)
思路是围绕c块贴片,先贴空白片再贴雷,然后优化边角策略。

0 ≤ M < R * C. Small dataset

1 ≤ T ≤ 230. 1 ≤ R, C ≤ 5. Large dataset

1 ≤ T ≤ 140. 1 ≤ R, C ≤ 50.

Problem D. Deceitful War

Naomi和Ken两个人,分别给定一定数量的含重( (0.0, 1.0) kg 之间)木头,双方木头不重复且相互不知道对方木头重量,二者分别出木头,Naomi先出,Ken后出。谁重谁得分。Naomi能够作弊,偷窥Ken的木头得到木头重量,并且在Ken不发现的情况下谎报木头重量(比如为了逼迫Ken用掉0.965重量的木头,Naomi可以谎报0.1重量的木头为0.965重)。问Naomi可能的作弊得分和不作弊得分。Ken始终采用对自己最佳的方案(在有序的情况下,有大于Naomi的木头就出,没有就用最小的木头替换)

“今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。” - 《田忌赛马》

输入:

  • 例子数
    • 木块数
    • Naomi的木头
    • Ken的木头
4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458

解题:

#!/usr/bin/env python
# encoding: utf-8


import sys


def strategy(cand, i):
    c = filter(lambda x: x > i, cand)
    if c:
        c_min = min(c)
    else:
        c_min = min(cand)
    return c_min


def war(naomi_mood, ken_mood):
    normal_war_ken_mood = list(ken_mood)
    naomi_score_normal = 0
    for i in naomi_mood:
        c = strategy(normal_war_ken_mood, i)
        if i > c:
            naomi_score_normal += 1
        #print i, c
        #print "*****"
        normal_war_ken_mood.remove(c)


    cheat_war_naomi_mood = list(reversed(naomi_mood))
    naomi_score_cheat = 0
    for i in reversed(ken_mood):
        c = cheat_war_naomi_mood[0]
        if c > i:
            cheat_war_naomi_mood.remove(c)
            naomi_score_cheat += 1
        else:
            cheat_war_naomi_mood.pop()
    return naomi_score_cheat, naomi_score_normal


def main():
    times = int(sys.stdin.readline())
    for case_n in xrange(1, times+1):
        total = int(sys.stdin.readline())
        naomi_mood = sorted(map(float, sys.stdin.readline().split()))
        ken_mood = sorted(map(float, sys.stdin.readline().split()))
        #print "====================="
        print "Case #%d:" % case_n, "%d %d" % war(naomi_mood, ken_mood)


if __name__ == "__main__":
    main()

总结

刷刷水题,在工作之余,娱乐身心。