UmmaeWiki

올해 코드쨈에서는 티셔츠를 받을 수 있을까? 얼마전 열린 한국지역 코드쨈에서는 하나 얻었지만, 코드쨈은 쉽지 않을듯..

요즘 탑코더 리뷰를 거의 못하고 있다. 거진 6-7개는 밀린듯.. 탑코더할 시간까지 못낼순 없지만 짬내서 리뷰하는 시간까지는 힘들다. 강의가 어느정도 끝나면 가능할 것 같은데, 끝나는 강의보다 새로 시작하는 강의다 더 많으니.. ㅋㅋ

코드쨈 예선 당일도, 강의 듣느냐, 결혼식 모임가느냐 시간이 없는 관계로, 예선 통과 점수인 20점만 빠르게 획득하고 관뒀다. 예전 같으면 예선 24시간 내내 풀 수 있는 문제는 다 풀었을텐데.. 그래서 좀 빨리 풀고자, Python을 사용했다.

총 4문제였고, A번은 small만, 나머지 B,C,D는 small/large로 나뉘어져있었다. A, B small/large만 풀고 접었다. 35점 받고 통과.

A. Speaking in Tongues

• Problem Link

재밌는 문제였다. Googlerese라는 언어가 있는데, 영어에서 각 알파벳이 다른 알파벳으로 매핑된 형태로 표현가능하다. 문제는 영어의 각 알파벳이 어느 알파벳으로 매핑이 되야 Googlerese언어가 되는지 모른다는건데, 지문에는 3개의 규칙만 주어지고 나머지는 예제에서 찾아야한다.

함정이 하나있다. 예제를 샅샅이 살펴보아도 2 알파벳에 대한 매핑 정보는 알 수 없다. ㅋㅋ 결국 submit할때 받는 input파일을 보고 잽싸게 판단해서 2개의 알파벳 정보를 추가해야한다. 그렇지 않으면 1 wrong. 처음에 이 두 개의 알파벳이 빠진걸 모르고 input을 다운받고 답을 출력해보니 뭔가 이상해서 눈치를 챘다. 코드쨈은 input파일을 다운 받은 후에 small은 4분, large는 6분 안에 제출해야하므로 잽싼 코드 수정 스킬이 필요하다.

import sys
rl = sys.stdin.readline
n = int(rl().strip())

rules = {' ': ' ', 'a': 'y', 'c': 'e', 'b': 'h', 'e': 'o', 'd': 's', 'g': 'v', 'f': 'c', 'i': 'd', 'h': 'x', 'k': 'i', 'j': 'u', 'm': 'l', 'l': 'g', 'o': 'k', 'n': 'b', 'p': 'r', 's': 'n', 'r': 't', 'u': 'j', 't': 'w', 'w': 'f', 'v': 'p', 'y': 'a', 'x': 'm', 'z': 'q', 'q':'z'}

for i in xrange(n):
    line = rl().strip()
    tkn = [ t for t in line ]
    for j in range(len(tkn)):
        tkn[j] = rules[tkn[j]]

    print 'Case #%d: %s' % (i+1, "".join(tkn))

B. Dancing With the Googler

• Problem Link

구글러들이 댄스를 하는 파티를 열었다. 3명의 심사자들은 춤을 춘 구글러에 대해서 0점에서 10점사이의 점수로 평가를 한다. 3명의 심사자들은 기준이 매우매우 흡사해서, 각 심사자들이 평가한 점수는 2점이상 차이가 날 수 없다. 예를 들어, (6,7,8), (8,8,8)와 같은 평가점수는 있을 수 있지만, (1,6,9), (4,4,7)과 같은 평가점수는 있을 수 없다.

한가지 특별한 경우가 있다. 3명의 심사자들이 평가한 점수중에 “2″점이상 차이나는 점수가 있는 평가점수를 “놀라운 케이스”라고 부른다. (4,4,6)은 놀라운 케이스이고, (5,5,6)은 아니다.

문제는, 3명의 심사자들이 각 구글러를 평가한 점수들이 주어지는게 아니라, 각 구글러에 평가된 3개의 점수의 합이 주어진다는 것이다. 예를 들어 3명의 구글러가 댄스에 참여 했다면, 20, 14, 30 이런식으로 입력이 주어진다.

진짜 문제는ㅋㅋ. N명의 구글러가 받은 점수의 총합 Score={s1, s2, … sn}이 주어졌을 때, 조건 1) N명 중에 “놀라운 케이스”인 구글러가 정확히 p명일때, 조건 2) 각 구글러가 받은 평가 점수가 상수 q를 넘는 구글러의 수를 출력 하는 것이다. 이 조건을 만족하는 경우의 수가 여러개일 경우에, 상수 q를 넘는 구글러의 수가 최대가 되는 경우를 출력하면된다.

import sys
rl = sys.stdin.readline

n = int(rl().strip())

ot = [i for i in range(0,11) ] # one to ten
for i in range(n):
    tkn = rl().strip().split()
    nn = int(tkn[1])
    ns = int(tkn[2])
    p = int(tkn[3])
    numSuprise = 0
    numGreater = 0
    for j in range(3, len(tkn)):
        num = int(tkn[j])
        isSuprise=False
        greaterThan=False
        sample = set()
        for a in ot:
            for b in ot:
                if abs(a-b) > 2: continue
                for c in ot:
                    if abs(a-c) > 2: continue
                    if abs(b-c) > 2: continue
                    if a+b+c == num:
                        if abs(a-c)==2 or abs(a-b) == 2 or abs(b-c) == 2:
                            isSuprise=True
                        if a>=p or b>=p or c>=p:
                            greaterThan=True
                        sample.add( (isSuprise, greaterThan) )
                        isSuprise, greaterThan = False, False
        if (False, True) in sample :
            numGreater += 1
        elif (True, True) in sample:
            numSuprise += 1
    ans = numGreater
    ans = ans + min(numSuprise, ns)
    print 'Case #%d: %d' % (i+1, ans)