Google Code Jam 2012 资格赛2

  第二题叙述冗长，编程同时考察阅读能力，不认真看描述，可能就写不对程序。

  题目大意：在[0, 30] 的数中，把任意一数拆成一个triplet，使得triplet中三个数之和等于这个数，同时这三个数必须在[0, 10]范围内。这三个数中任意两个数差的绝对值等于0或者1的叫做normal，等于2的叫做surprising，大于2的不允许出现。
  示例：(8, 8, 8) and (7, 8, 7) are not surprising. (6, 7, 8) and (6, 8, 8) are surprising. (7, 6, 9) will never happen.


  现在给出若干个数，要把这若干个数中的每一个都拆分成为triplet，每一triplet中最大的一个数叫做“值”，这一triplet的属性可以是normal或者surprising，但是允许出现surprising的次数有限制，限制已经给出。
  求这若干个数拆成triplet后，“值”大于等于给定数（给定数的范围也是[0, 10]）的triplet出现的总数。（注意surprising的限制）


  这一题目的关键是：0，1，29，30这几个特例，否则程序无法正确。

  普通情况的分析：
  数字n ：
                     normal   surprising
  n % 3 == 0: 18 -> [6,6,6], [5,6,7]       18 // 3 = 6
  n % 3 == 1: 16 -> [5,5,6], [4,6,6]       16 // 3 = 5
  n % 3 == 2: 17 -> [5,6,6], [5,5,7]       17 // 3 = 5

所以结论很简单：数字根据余3的结果分成3类，每一类有一个(normal, surprising) 的数据对，这个数据对是数字除以3所得的商来填写的。
  拿16，17，18举例：
  quotient := 16 // 3 得到数据对就是(quotient + 1, quotient + 1)
  quotient := 17 // 3 得到数据对就是(quotient + 1, quotient + 2)
  quotient := 18 // 3 得到数据对就是(quotient, quotient + 1)


  特殊情况分析：
    0得到(0,0)， 30得到(10, 10)， 1得到(1,1)，29得到(10, 10)


程序清单：

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

import sys


def read_file(fname):
    fd = open(fname)
    times = fd.readline()
    times = int(times.rstrip('\n'))
    content = fd.readlines()[:times]
    fd.close()
    return content

def write_file(result):
    fd = open('b.txt', 'w')
    fd.writelines(result)
    fd.close()

def process(combination, N, S, p):
    total = 0
    for item in combination:
        if item[0] >= p: # normal >= p
            total += 1
        elif item[1] >= p: # surprising >= p
            if S > 0:
                total += 1
                S -= 1
    return total

def control(content):
    result = []
    for i, line in enumerate(content):
        combination = []
        line = line.rstrip('\n').split()
        for item in line[3:]:
            base = int(item) // 3
            if int(item) % 3 == 0:
                if int(item) == 0 or int(item) == 30: # Each triplet of scores consists of three integer scores from 0 to 10 inclusive
                    combination.append((base, base)) # if it is 0 or 30
                else:
                    combination.append((base, base + 1)) # normal, surprising
            elif int(item) % 3 == 1: # 1 don't have surprising
                combination.append((base + 1, base + 1))
            elif int(item) % 3 == 2:
                if int(item) == 29: # 29 don't have surprising, 11 is invalid
                    combination.append((base + 1, base + 1))
                else:
                    combination.append((base + 1, base + 2))
        total = process(combination, int(line[0]), int(line[1]), int(line[2]))
        result.append('Case #' + str(i+1) + ': ' + str(total) + '\n')
    return result

if __name__ == '__main__':

    if len(sys.argv) < 2:
        print('Please set input file as a parameter.')
        sys.exit(1)

    content = read_file(sys.argv[1])
    result = control(content)
    write_file(result)