쁜사의 아틀리에

야찌 게임은 다섯 개의 주사위를 써서 하는 게임으로, 13 라운드에 걸쳐서 주사위를 던지는 게임이다. 스코어 카드에는 13개의 카테고리가 있다. 각 라운드에서는 게임 참가자가 선택한 카테고리에 의해 점수를 딸 수 있는데, 이때 각 카테고리는 한 게임에 한 번만 쓸 수 있다. 13개의 카테고리에서는 다음과 같은 식으로 점수를 딴다.

• 1 - 모든 1들의 합
• 2 - 모든 2들의 합
• 3 - 모든 3들의 합
• 4 - 모든 4들의 합
• 5 - 모든 5들의 합
• 6 - 모든 6들의 합
• 찬스 - 모든 숫자의 합
• 같은 숫자 세 개 - 적어도 세 개가 같은 숫자일 때, 모든 숫자의 합
• 같은 숫자 네 개 - 적어도 네 개가 같은 숫자일 때, 모든 숫자의 합
• 같은 숫자 다섯 개 - 적어도 다섯 개가 같은 숫자일 때, 50점
• 쇼트 스트레이트 - 네 개가 연속된 숫자일 때(1, 2, 3, 4 또는 2, 3, 4, 5 또는 3, 4, 5, 6), 25점
• 롱 스트레이트 - 다섯 개가 연속된 숫자일 때(1, 2, 3, 4, 5 또는 2, 3, 4, 5, 6), 35점
• 풀 하우스 - 세 개가 같은 숫자이고 나머지 두 개가 같은 숫자일 때(예를 들면 2, 2, 5, 5, 5), 40점

마지막 여섯 개의 카테고리는 조건이 만족되지 않으면 0점으로 처리한다.

이 게임의 총점은 13개의 카테고리 각각의 점수를 모두 더한 점수며 첫번째부터 여섯 번째까지의 카테고리 총합이 63점 이상이면 보너스 점수 35점이 추가된다.

여러 라운드가 주어졌을 때 가능한 최고 점수를 계산하라.

입력

각 줄에는 1이상 6 이하의 정수가 다섯 개 있으며 이는 각 라운드에 나온 주사위 다섯개의 숫자를 나타낸다. 매 게임마다 13줄이 입력되며 입력 데이터에 들어있는 게임 횟수에는 제한이 없다.

출력

한 줄에 15개의 숫자를 출력한다. 15개의 숫자는 각 카테고리별 점수(위에 나와 잇는 순서대로)와 보너스 점수(0 또는 35), 그리고 총점이다. 여러 방식으로 카테고리를 적용했을 때 같은 점수가 나오면 그 중 아무 결과나 출력해도 된다.

예제

아래처럼 입력에 대한 출력이 나온다.

해설

해가 지나도록 질질 끌었던 문제다. 룰 적용에 대한 모든 조합을 구하고, 각 조합에 대한 점수를 계산해서 최고 점수를 찾는 것이다. 다만 전체 조합의 수가 13! 이기 때문에 시간이 어마어마하게 걸린다. 이에 대한 해답으로 0점인 룰은 제외해서 조합의 수를 줄이니 어찌어찌 수 분만에 풀이가 가능했다. 

'같은 숫자 세 개'와 '같은 숫자 네 개' 룰의 점수 계산이 헷갈릴 수 있다. 조건이 맞을 때, 숫자 5개의 점수를 모두 더하는 것이다. 처음에는 3개, 4개만 더했더니 자꾸 답이 틀렸는데, 이 부분을 유의하면 좋을 것 같다.

# Quiz 0016, Yahtzee
# written by badsaram

import sys

class Yahtzee(object):
    def __init__(self):
        self.dice_try = []
        self.dice_try_score = []
        self.combination = [0] * 13
        self.combination_count = 0
        self.max_try_count = 13
        self.max_pattern_count = 13
        self.max_combination_count = 0
        self.max_score = 0
        self.max_score_combination = [0] * 13

    def input(self):
        for i in range(0, self.max_try_count):
            str = input()
            tokens = str.split(' ')

            if (len(tokens) > 5):
                print("wrong input number.")
                sys.exit(-1)

            int_tokens = []
            for token in tokens:
                if (int(token) > 6):
                    print("wrong input number.")
                    sys.exit(-1)
                    
                int_tokens.append(int(token))

            self.dice_try.append(int_tokens)

    def test_input1(self):
        for i in range(0, self.max_try_count):
            self.dice_try.append([1, 2, 3, 4, 5])

    def test_input2(self):
        self.dice_try.append([1, 1, 1, 1, 1])
        self.dice_try.append([6, 6, 6, 6, 6])
        self.dice_try.append([6, 6, 6, 1, 1])
        self.dice_try.append([1, 1, 1, 2, 2])
        self.dice_try.append([1, 1, 1, 2, 3])
        self.dice_try.append([1, 2, 3, 4, 5])
        self.dice_try.append([1, 2, 3, 4, 6])
        self.dice_try.append([6, 1, 2, 6, 6])
        self.dice_try.append([1, 4, 5, 5, 5])
        self.dice_try.append([5, 5, 5, 5, 6])
        self.dice_try.append([4, 4, 4, 5, 6])
        self.dice_try.append([3, 1, 3, 6, 3])
        self.dice_try.append([2, 2, 2, 4, 6])

    def calc(self):
        for i in range(0, len(self.dice_try)):
            self.calc_pattern(self.dice_try[i])

        # brutal force
        self.traverse(0)

        # fill empty item
        for i in range(0, len(self.max_score_combination)):
            if (self.max_score_combination[i] == 0):
                for j in range(1, self.max_pattern_count + 1):
                    if (j in self.max_score_combination):
                        pass
                    else:
                        self.max_score_combination[i] = j
                        break

        # print answer
        #print(self.max_score_combination)
        answer = [0] * 15
        for i in range(0, len(self.max_score_combination)):
            pattern = self.max_score_combination[i]
            score = self.dice_try_score[i][pattern]
            answer[pattern - 1] = score

        if (sum(answer[0:6]) >= 63):
            answer[13] = 35
    
        answer[14] = self.max_score

        print(answer)           

    def calc_pattern(self, dices):
        switch = {
            1 : self.calc_pattern_1(dices),
            2 : self.calc_pattern_2(dices),
            3 : self.calc_pattern_3(dices),
            4 : self.calc_pattern_4(dices),
            5 : self.calc_pattern_5(dices),
            6 : self.calc_pattern_6(dices),
            7 : self.calc_pattern_7(dices),
            8 : self.calc_pattern_8(dices),
            9 : self.calc_pattern_9(dices),
            10 : self.calc_pattern_10(dices),
            11 : self.calc_pattern_11(dices),
            12 : self.calc_pattern_12(dices),
            13 : self.calc_pattern_13(dices)
        }

        item = []
        item.append(dices)
        for i in range(1, 14):
            item.append(switch.get(i))

        self.dice_try_score.append(item)

    def calc_pattern_1(self, dices):
        return dices.count(1) * 1
    
    def calc_pattern_2(self, dices):
        return dices.count(2) * 2
    
    def calc_pattern_3(self, dices):
        return dices.count(3) * 3
    
    def calc_pattern_4(self, dices):
        return dices.count(4) * 4
    
    def calc_pattern_5(self, dices):
        return dices.count(5) * 5
    
    def calc_pattern_6(self, dices):
        return dices.count(6) * 6
    
    def calc_pattern_7(self, dices):
        return sum(dices)
    
    def calc_pattern_8(self, dices):
        for i in range(1, 7):
            if (dices.count(i) >= 3):
                return sum(dices)
            
        return 0
    
    def calc_pattern_9(self, dices):
        for i in range(1, 7):
            if (dices.count(i) >= 4):
                return sum(dices)

        return 0

    def calc_pattern_10(self, dices):
        sum = 0

        for i in range(1, 7):
            if (dices.count(i) >= 5):
                sum = 50
                break

        return sum
    
    def calc_pattern_11(self, dices):
        sum = 0

        if (1 in dices) and (2 in dices) and (3 in dices) and (4 in dices):
            sum = 25

        if (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices):
            sum = 25

        if (3 in dices) and (4 in dices) and (5 in dices) and (6 in dices):
            sum = 25

        return sum
    
    def calc_pattern_12(self, dices):
        sum = 35

        if (1 in dices) and (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices):
            sum = 35

        if (2 in dices) and (3 in dices) and (4 in dices) and (5 in dices) and (6 in dices):
            sum = 35

        return sum
    
    def calc_pattern_13(self, dices):
        sum = 0
        meet2 = False
        meet3 = False

        for i in range(1, 7):
            if (dices.count(i) == 2):
                meet2 = True

            elif (dices.count(i) == 3):
                meet3 = True
            
        if ((meet2 == True) and (meet3 == True)):
            sum = 40
        
        return sum
    
    def calc_combination(self, combination):
        total_score = 0
        pattern_1_6_score = 0

        for i in range (0, self.max_try_count):
            pattern = combination[i]
            if (pattern != 0):
                total_score = total_score + self.dice_try_score[i][pattern]
            if (pattern in range(1, 7)): # 1 
                pattern_1_6_score = pattern_1_6_score + self.dice_try_score[i][pattern]

        if (pattern_1_6_score >= 63):
            total_score = total_score + 35  # if score of pattern 1˜6 is greater than 63, bonus 35 is added 

        if (total_score > self.max_score):
            self.max_score = total_score
            self.max_score_combination[:] = combination

        return total_score
    
    def count_combination_length(self, combination):
        return len(list(filter(lambda x: x != 0, combination)))

    def traverse(self, depth):
        if (depth >= self.max_try_count): # depth >= 13
            return

        for i in range(1, self.max_try_count + 1):
            if (i in self.combination):
                continue

            if (self.dice_try_score[depth][i] == 0):
                continue

            self.combination[depth] = i

            if (depth == (self.max_try_count - 1)): # depth == 12
                total_score = self.calc_combination(self.combination)
                self.max_combination_count = self.max_try_count # 13

                self.combination_count = self.combination_count + 1
                #print("%10d | %s | %d" % (self.combination_count, self.combination, total_score))

            self.traverse(depth + 1)
            self.combination[depth] = 0

        combination_len = self.count_combination_length(self.combination)
        if (combination_len >= self.max_combination_count):
            total_score = self.calc_combination(self.combination)
            self.max_combination_count = combination_len

            self.combination_count = self.combination_count + 1
            #print("%10d | %s | %d" % (self.combination_count, self.combination, total_score))

if __name__ == '__main__':
    obj = Yahtzee()

    obj.input()
    #obj.test_input1()
    #obj.test_input2()
    obj.calc()

ACM ICPC에 출전하고 싶다면 점수 계산법을 알아야 한다. 경시 대회에 참가한 팀의 순위는 우선 푼 문제의 개수가 많은 순으로, 그 다음으로는 시간 벌점(penalty time)이 적은 순으로 매겨진다. 이 둘을 모두 고려했는데도 동점 팀이 둘 이상이면 팀 멤버 수가 적은 쪽이 더 높은 순위를 차지할 수 있다. 

제출된 풀이 가운데 정답으로 판정받은 것이 하나라도 있으면 그 문제는 해결된 것으로 인정된다. 시간 벌점은 해당 문제에 대한 첫번째 정답이 제출될 때까지 걸린 시간으로 계산되며 정답이 나오기 전까지 제출된 오답이 있으면 한 개에 20분씩의 시간 벌점이 추가된다. 풀리지 않은 문제에 대해서는 시간 벌점이 전혀 적용되지 않는다.

입력

각 입력은 심사 큐의 스냅샷으로 구성되는데, 여기서는 1번부터 9번까지의 문제를 푸는 1번부터 100번까지의 경시 대회 참가 팀으로부터 입력된 내용이 들어있다. 각 줄은 세 개의 수와 경시 대회 문제 시간 L 형식의 글자 하나로 구성된다. L은 C, I, R, U 또는 E 라는 값을 가질 수 있는데 이 글자들은 각각 Correct(정답), Incorrect(오답), Clarification Request(확인 요청), Unjudged(미심사), Erroneous submission(제출 오류)을 의미한다. 마지막 세 개의 케이스는 점수에 영향을 미치치 않는다. 입력은 제출된 순서대로 입력된다.

출력

각 테스트 케이스에 대해 앞에서 설명한 순서에 의해 정렬된 점수표가 출력된다. 출력되는 각 줄에는 참가팀 번호, 그 팀이 푼 문제, 누적된 시간 벌점이 출력된다. 모든 경시 대회 참가 팀이 풀이를 제출하는 것은 아니므로 실제로 풀이를 제출한 팀의 결과만 표시한다. 그리고 두 개의 서로 다른 케이스에 대한 출력은 빈 줄로 구분한다.

예제

해설

문제를 묘하게 이해하기 힘들었다. "동점 팀이 둘 이상이면 팀 멤버 수가 적은 쪽이 더 큰 순위를 차지할 수 있다" 라는데 입력 어디에도 팀 멤버수가 정의되지 않았다. 이건 무시했다. 점수 집계를 파이썬의 딕셔너리를 사용하다보니, 딕셔너리의 정렬 방법에 대해서 공부가 필요했다. 다른 것은 평이하니 소스 코드를 보면 쉽게 이해가 될 것이다.

# Quiz 0015, Contest Score Board
# written by badsaram

import sys

class CScoreBoard(object):
    def __init__(self):
        self.history_board = []
        self.score_board = {}

    def input(self):
        ret = True

        while True:
            input_str = input()

            if (input_str == ""):
                ret = False
                break

            tokens = input_str.split(" ")

            try:
                team_id     = int(tokens[0])
                quiz_num    = int(tokens[1])
                proc_time   = int(tokens[2])
                result_type = tokens[3].strip().upper()

                if ((team_id <= 0) or (team_id > 100) or (quiz_num <= 0) or (quiz_num >= 10)):
                    ret = False
                    break

                self.history_board.append([team_id, quiz_num, proc_time, result_type])
            except:
                ret = False
                break

        return ret

    def test_input(self):
        self.history_board.append([1, 2, 10, 'I'])
        self.history_board.append([3, 1, 11, 'C'])
        self.history_board.append([1, 2, 19, 'R'])
        self.history_board.append([1, 2, 21, 'C'])
        self.history_board.append([1, 1, 25, 'C'])
        self.history_board.append([9, 1, 10, 'C'])
        self.history_board.append([9, 2, 30, 'C'])
        self.history_board.append([9, 3, 40, 'C'])
        self.history_board.append([4, 1, 10, 'C'])
        self.history_board.append([4, 2, 20, 'C'])

    def run(self):
        for history in self.history_board:
            if ((history[0] in self.score_board) == False):
                self.score_board[history[0]] = [ [], 0 ]

            if (history[3] == 'I'):
                self.score_board[history[0]][1] += 20
            elif (history[3] == 'C'):
                if ((history[1] in self.score_board[history[0]][0]) == False):
                    self.score_board[history[0]][0].append(history[1])

                self.score_board[history[0]][1] += history[2]
            else:
                pass

        d1 = sorted(self.score_board.items(), key = lambda x : (-len((x[1])[0]), (x[1])[1]))

        for item in d1:
            print("%d %d %d" % (item[0], len(item[1][0]), item[1][1]))

if __name__ == '__main__':
    obj = CScoreBoard()

    obj.input()
    #obj.test_input()
    obj.run()

헝가리 출신의 수학자 폴 에르되시(Paul Erdős, 1913-1996)는 20세기의 가장 유명한 수학자 가운데 하나로 꼽힌다. 에르되시와 함꼐 논문을 쓴 경험이 있는 수학자들도 존경을 받을 정도니 그의 명성을 짐작할 수 있을 것이다.

하지만 불행하게도 모든 사람들이 그와 함께 논문을 쓸 기회를 얻을 수 있는 것은 아니었기 때문에 에르되시와 함께 논문을 썼던 사람과 논문을 같이 쓰는 정도로 만족해야 한다. 이런 이유로 인해 에르되시 수라는 것이 생겼다. 에르되시와 함께 논문을 쓴 사람의 에르되시 수는 1이다. 에르되시와 직접 함께 논문을 쓰지 않았지만 에르되시 수가 1인 사람과 함께 논문을 쓴 적이 있는 사람의 에르되시 수는 2다.

주어진 논문과 논문 저자를 바탕으로 에르되시 수를 계산하는 프로그램을 만들어야 한다.

입력

입력의 첫번째 행에는 P와 N이라는 자연수 두 개가 입력된다. 그 다음 줄에는 논문 데이터베이스가 입력되며 각 논문마다 한 줄씩 저자에 대한 정보가 입력된다. 각 논문에 대한 정보는 다음과 같은 식으로 기술된다.

   Smith M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matrices

ő 같은 움라우트는 편의장 'o'로 표기한다. P개의 논문 정보 밑에는 각각 하나씩의 이름이 들어있는 N개의 행이 입력된다. 이름은 다음과 같은 형식으로 입력된다. 이름은 다음과 같은 형식으로 입력된다.

   Martin, G.

출력

입력된 모든 이름에 대해 이름과 에르되시 수를 출력한다. 저자의 이름은 입력된 순서대로 출력된다. 에르되시 수는 시나리오에 들어있는 논문 데이터베이스를 기반으로 계산한다. 데이터베이스에 있는 논문으로 볼 때 에르되시와 전혀 관계가 없는 저자들의 에르되시 수는 "infinity"로 출력한다.

예제

해설

논문 데이터베이스에서 저자들의 이름을 추출하는 것이 제일 어려웠다. 문자열 처리는 늘 골치가 아프다. 우선 에르되시와 1촌인 사람을 먼저 구한다. 그리고 2촌, 3촌 이런 식으로 구해가면 간단히 해결!

# Quiz 0014, Erdos Numbers
# written by badsaram

import sys

class ErdosNumbers(object):
    def __init__(self):
        self.num_thesis = 0
        self.num_author = 0
        self.num_query = 0
        self.thesis_list = []
        self.author_list = []
        self.query_list = []

    def input(self):
        ret = True

        str = input()
        tokens = str.split()

        try:
            self.num_thesis = int(tokens[0])
            self.num_author = int(tokens[1])
        except:
            ret = False

        for i in range(self.num_thesis):
            self.thesis_list.append(input())

        for i in range(self.num_author):
            self.query_list.append(input())

        return ret

    def test_input(self):
        self.num_thesis = 4
        self.num_query = 3

        self.thesis_list.append("Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrix")
        self.thesis_list.append("Erdos, P., Reisig, W.: Stuttering in patri nets")
        self.thesis_list.append("Smith, M.N., Chen, X.: First oder derivates in structured programming")
        self.thesis_list.append("Jablonski, T., Hsueh, Z.: Selfstabilizing data structures")

        self.query_list.append("Smith, M.N.")
        self.query_list.append("Hsueh, Z.")
        self.query_list.append("Chen, X.")

    def run(self):
        for thesis_title in self.thesis_list:
            input_str = thesis_title.split(':')

            # separate authors from thesis title
            input_str = input_str[0].split(".,")
            for word in input_str:
                word = word.strip()
                if word[-1] != '.':
                    word += '.'

                try:
                    self.author_list.index([word, 0])
                except:
                    self.author_list.append([word, 0])

        # find tier-1
        for i in range(len(self.author_list)):
            for thesis in self.thesis_list:
                if (self.isTogether(self.author_list[i][0], "Erdos, P.") == True):
                    self.author_list[i][1] = 1

        # find tier-2, 3
        n = 1
        while True:
            if ((self.isCompleted() == True) or (n >= len(self.author_list))):
                break

            author_zero_indexes = self.getAuthorFilterIndex(0)
            author_n_indexes = self.getAuthorFilterIndex(n)

            for author_zero_index in author_zero_indexes:
                for author_n_index in author_n_indexes:
                    if (self.isTogether(self.author_list[author_zero_index][0],
                                        self.author_list[author_n_index][0]) == True):
                        self.author_list[author_zero_index][1] = n + 1

            n += 1

        for query in self.query_list:
            for i in range(len(self.author_list)):
                if (query == self.author_list[i][0]):
                    print(query + " ", end = "")
                    if (self.author_list[i][1] ==  0):
                        print("infinity")
                    else:
                        print(str(self.author_list[i][1]))


    def isCompleted(self):
        ret = True

        if (len(self.author_list) > 0):
            for author in self.author_list:
                if (author[1] == 0):
                    ret = False
                    break
        else:
            ret = False

        return ret

    def isTogether(self, author1, author2):
        ret = False

        for thesis in self.thesis_list:
            try:
                if ((thesis.index(author1) >= 0) and
                    (thesis.index(author2) >= 0)):
                    ret = True
                    break
            except:
                ret = False

        return ret

    def getAuthorFilterIndex(self, n):
        list = []

        for i in range(len(self.author_list)):
            if (self.author_list[i][1] == n):
                list.append(i)

        return list

if __name__ == '__main__':
    obj = ErdosNumbers()

    obj.input()
    #obj.test_input()
    obj.run()

빅 시티(Big)에는 카지노가 여러 개 있다. 그 중 한 카지노에는 딜러가 속임수를 씁니다. 그녀는 몇 가지 카드 섞는 법을 완벽하게 익혔는데, 그 카드 섞는 법을 사용하면 언제든지 카드를 마음대로 재배치할 수 있습니다. 간단한 예로 '밑장' 섞기를 들 수 있는데, 맨 아래 있는 카드를 꺼내서 맨 위로 올려놓는 방법이다. 그 딜러는 이런 다양한 섞기 방법을 조합해서 원하는 순서대로 카드를 쌓아 올릴 수 있습니다.

카지노의 보안 관리자가 그 딜러를 감시하기 위해 당신을 고용했습니다. 딜러가 섞은 모든 카드 순서가 주어지며 사용된 섞기 방법도 제공됩니다. 이런 정보가 주어졌을 때 몇번의 섞기 작업이 진행된 후의 카드 순서를 예측해야 합니다.

카드 한 벌은 52개의 카드로 구성되며 네 개의 무늬마다 13장의 카드가 있습니다. 카드의 값(숫자)은 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace 중 하나입니다. 그리고 무늬는 Clubs, Diamonds, Hearts, Spades 가운데 하나입니다. 각 카드는 <값> of <무늬>와 같은 식으로 값과 무늬를 써서 유일하게 식별할 수 있습니다. 예를 들면 "9 of Hearts", "King of Spades" 같은 식으로 표현할 수 있습니다. 관례에 따라 새 카드는 우선 무늬를 기준으로 알파벳 순으로, 그리고 위에 나와 있는 값 순서대로 정렬됩니다.

입력

입력은 딜러가 알고 있는 섞이 방법의 개수인 100이하의 정수 n으로 시작됩니다. 그 다음 줄에는 52개의 정수가 n세트 나오는데 각 세트에는 1에서 52까지의 모든 정수가 들어있습니다. 52개의 정수로 구성된 각 세트내에서 j 위치에 i가 있다는 것은 패에서 i번째 카드를 j번째 위치로 이동시킨다는 것을 의미합니다.

그 뒤에는 각각 1 이상 n 이하의 정수 k가 들어있는 행이 여러 개 뒤따릅니다. 입력된 정수 k는 딜러가 k번째 섞기 방법을 썼다는 것을 나타냅니다.

출력

딜러가 위에 기술되어 있는 대로 정렬된 새로운 패를 가지고 시작한다고 가정하고 섞기가 모두 끝난 후에 새로운 순서에 따라서 카드의 이름을 출력합니다. 두 개의 서로 다른 케이스에 대한 출력 결과는 빈 줄로 구분합니다.

예제

2
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 52 51
52 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 1
King of Spades
2 of Clubs
4 of Clubs
5 of Clubs
6 of Clubs
7 of Clubs
8 of Clubs
9 of Clubs
10 of Clubs
Jack of Clubs
Queen of Clubs
King of Clubs
Ace of Clubs
2 of Diamonds
3 of Diamonds
4 of Diamonds
5 of Diamonds
6 of Diamonds
7 of Diamonds
8 of Diamonds
9 of Diamonds
10 of Diamonds
Jack of Diamonds
Queen of Diamonds
King of Diamonds
Ace of Diamonds
2 of Hearts
3 of Hearts
4 of Hearts
5 of Hearts
6 of Hearts
7 of Hearts
8 of Hearts
9 of Hearts
10 of Hearts
Jack of Hearts
Queen of Hearts
King of Hearts
Ace of Hearts
2 of Spades
3 of Spades
4 of Spades
5 of Spades
6 of Spades
7 of Spades
8 of Spades
9 of Spades
10 of Spades
Jack of Spades
Queen of Spades
Ace of Spades
3 of Clubs

해설

문제가 무슨 말을 하는지 몰라서 고생을 했다. 한국말로 써 있는데 한국 말인 것인지 이해가 안됐다. 그러다 1부터 52까지 써 있는 것이 새 카드의 덱(deck)이고, 입력 받은 case의 52개의 숫자와의 Diff로 섞기 방법을 계산하면 의외로 쉬운 문제라는 것을 알게 됐다. 이렇게 Diff로 얻어진 카드의 이동 순서를 기록해두고, 새 카드의(deck)에 순차적으로 적용하면 됐던 평이한 문제였다. 

# Quiz 0013, Stack'em Up
# written by badsaram

import sys

class stackemup(object):
    def __init__(self):
        self.shuffle_list = []
        self.num_cases = 0

    def input(self, testflag):

        if (testflag == True):
            self.num_cases = 2
        else:
            str = input() # input number of test caess
            self.num_cases = int(str)

        for i in range(self.num_cases):
            if (testflag == True):
                if (i == 0):
                    str = "2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 52 51"
                else:
                    str = "52 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 1"
            else:
                str = input()
        
            shf = shuffle()
            ret = shf.input_case(str)
            if (ret == True):
                self.shuffle_list.append(shf)
            else:
                return False

        return True

    def calc(self):
        ret = False

        org_str = "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52"
        dck = deck()
        ret = dck.input_deck(org_str)

        if (len(self.shuffle_list) != 0):
            tokens = org_str.split(' ')

            for shuffle_case in self.shuffle_list:
                dck.shuffle_apply(shuffle_case)

            dck.print_deck()

            ret = True
        else:
            ret = False

        return ret

class deck(object):
    def __init__(self):
        self.deck_org   = ""
        self.deck_calc  = []

    def input_deck(self, str):
        self.deck_org = str

        tokens = self.deck_org.split(' ')
        for i in range(len(tokens)):
            if (tokens[i] != ''):
                self.deck_calc.append(int(tokens[i]))

    def shuffle_apply(self, shf):
        shuffles = shf.get_shuffle()
        deck_copy = self.deck_calc.copy()

        for shuffle in shuffles:
            deck_copy[shuffle[0]] = self.deck_calc[shuffle[1]]

        self.deck_calc = deck_copy

    def print_deck(self):
        if (len(self.deck_calc) != 0):
            for i in range(len(self.deck_calc)):
                self.print_card(self.deck_calc[i])

    def print_card(self, card_num):
        mark = int((card_num - 1) / 13)
        card = int((card_num - 1) % 13)

        mark_string = [ "Clubs", "Diamonds", "Hearts", "Spades" ]
        card_string = [ "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"]

        print("%s of %s" % (card_string[card], mark_string[mark]))

class shuffle(object):
    def __init__(self):
        self.shuffle_org  = ""
        self.shuffle_calc = []

    def input_case(self, str):
        self.shuffle_org = str

        tokens = self.shuffle_org.split(' ')
        if (len(tokens) != 52):
            return False

        for i in range(len(tokens)):
            if ((tokens[i] != '') and (int(tokens[i]) != (i + 1))):
                self.shuffle_calc.append([i, int(tokens[i]) - 1])

        return True

    def print_case(self):
        if (self.shuffle_org != ""):
            tokens = self.shuffle_org.split(' ')

            for i in range(len(tokens)):
                if (tokens[i] != ''):
                    self.print_card(int(tokens[i]))

    def print_card(self, card_num):
        mark = int((card_num - 1) / 13)
        card = int((card_num - 1) % 13)

        mark_string = [ "Clubs", "Diamonds", "Hearts", "Spades" ]
        card_string = [ "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King", "Ace"]

        print("%s of %s" % (card_string[card], mark_string[mark]))

    def print_diff(self):
        if (len(self.shuffle_calc) != 0):
            for diff in self.shuffle_calc:
                print("%d %d" % (diff[0], diff[1]))

    def get_shuffle(self):
        return self.shuffle_calc

if __name__ == '__main__':
    obj = stackemup()

    obj.input(True)
    obj.calc()

텍스트를 암호화는 방법 중에 보안상 취약하긴 하지만 흔하게 쓰이는 방법으로 알파벳 글자를 다른 글자로 돌리는 방법이 있다.

즉 알파벳의 각 글자를 다른 글자로 치환한다. 암호화된 것을 다시 원래대로 되돌릴 수 있으려면 두 개의 서로 다른 글자가 같은 글자로 치환되지 않아야 한다.

암호화된 텍스트가 한 줄 입력되는데, 이 때 매 시도마다 서로 다른 치환 방법이 적용된다.

암호화 이전의 텍스트에 있는 단어는 모두 주어진 사전에 들어있는 단어라고 가정하고, 암호화 된 텍스트를 해독하여 원래 텍스트를 알아내자.

입력

입력은 한 개의 정수 n이 들어 있는 행으로 시작되며 그 다음 줄부터는 한 줄에 하나씩 n개의 소문자로 쓰인 단어들이 입력된다.

이 n개의 단어들은 복호화된 텍스트에 들어갈 수 있는 단어로 구성된 사전이다. 사전 뒤에는 몇 줄의 텍스트가 입력된다. 

각 줄은 앞에서 설명한 방법에 따라서 복호화 된다.

사전에 들어갈 수 있는 단어의 수는 1000개를 넘어가지 않는다. 단어의 길이는 16 글자를 넘지 않는다. 

암호화된 텍스트에는 소문자와 스페이스만 들어가며 한 줄의 길이는 80 글자를 넘어가지 않는다.

출력

각 줄을 복호화하여 표준 출력으로 출력한다. 여러 문장으로 복호화 할 수 있다면 그 중 아무 결과나 출력하면 된다. 

가능한 풀이가 없다면 모든 문자를 아스테리스크(*)로 바꾸면 된다.

예제

6

and

dick

jane

puff

spot

yertle

bjvg xsb hsxn xsb qymm xsb rqat xsb pnetfn

dick and jane and puff and spot and yertle

해설

꽤 좌절을 겪은 문제다. 이래저래 2달 정도 걸린 것 같다. 내가 생각한 풀이는 다음과 같다.

1. 입력으로 받은 사전과 암호화 된 단어의 '알파벳'을 기준으로 치환 가능한 모든 '조합'을 구한다.

2. 구해진 '조합'으로 암호화 된 단어를 복호화 해서 원본 단어가 모두 있으면 출력

3. 하나라도 원본 단어가 없다면 모든 단어를 아스테리스크(*)로 출력

재귀 호출(Recursive Call)을 이용해서 '하노이 탑' 문제 풀듯이 했는데, 방법 자체는 맞는 것 같다.

다만 문제가 시간이 기하급수적으로 오래 걸린다는 것이다. '조합'을 구하는데 알파벳 수의 Factorial 만큼 걸리는데 어마어마한 수가 나온다.

일단 답은 올린다. 시간만 오래 걸리는거 빼고는 잘 동작하는 것 같다.

다시 이 문제를 찬찬히 읽어보니, 알파벳이 아니라 그냥 단어 단위로 쉽고 무식하게 풀면 될 것 같긴한데 너무 처음에 어렵게 생각한 걸까?

기회가 되면 2번째 풀이를 이 글에 올려보겠다~

# Quiz 0012, Crypt Kicker
# written by badsaram

import sys

class CryptKicker(object):
    def __init__(self, dbgMode):
        self.numDictionary = 0
        self.dictionary = []

        self.cryptFrom  = []
        self.cryptTo    = []

        self.cryptMatrix = []

        self.dbgMode = dbgMode

    def inputDictionary(self):
        str = input()
        if ((str.isdigit() != True) or (int(str) <= 0) or (int(str) > 1000)):
            print("Please Input Correct Number (0 < n <= 1000).")
            sys.exit(-1)

        self.numDictionary = int(str)

        for i in range(0, self.numDictionary):
            str = input()
            if ((len(str) > 16) or (str.isalpha() == False)):
                print("Please Input String Under 16 Characters. You should input %d strings" % (self.numDictionary))
                sys.exit(-1)

            self.dictionary.append(str)

        self.makeSymbolArray(self.dictionary, self.cryptFrom)

    def makeSymbolArray(self, words, cryptArray):
        # make cryptFrom
        for word in words:
            for ch in word:
                try:
                    cryptArray.index(ch)
                except:
                    cryptArray.append(ch)

    def isEmpty(self, ch):
        ret = False

        if (ch.isalpha() == True):
            ret = False
        else:
            ret = True

        return ret

    def insertCryptMatrix(self, cryptPattern):
        dup_flag = False

        for pattern in self.cryptMatrix:
            sameCnt = 0

            for i in range(len(pattern)):
                if (pattern[i] == cryptPattern[i]):
                    sameCnt += 1
                else:
                    break

            if (sameCnt == len(pattern)):
                dup_flag = True
                break

        if (dup_flag == False):
            self.cryptMatrix.append(cryptPattern.copy())
            if (self.dbgMode == True):
                print(cryptPattern)

    def makeCryptMatrix(self, cryptMatrix, n):
        for i in range(len(self.cryptFrom)):
            cryptPattern = [ '' for i in range(len(self.cryptFrom)) ]

            for j in range(len(self.cryptTo)):
                try:
                    cryptPattern.index(self.cryptTo[j])
                except:
                    cryptPattern[i] = self.cryptTo[j]

                    self.makeCryptMatrixRecursive(cryptPattern, n + 1)
                    cryptPattern[i] = ''

    def makeCryptMatrixRecursive(self, cryptPattern, n):
        if ( (n >= len(self.cryptFrom)) or (n >= len(self.cryptTo)) ):
            self.insertCryptMatrix(cryptPattern)
            return

        for i in range(len(self.cryptFrom)):
            if (self.isEmpty(cryptPattern[i]) == False):
                continue

            for j in range(len(self.cryptTo)):
                try:
                    cryptPattern.index(self.cryptTo[j])
                except:
                    cryptPattern[i] = self.cryptTo[j]

                    self.makeCryptMatrixRecursive(cryptPattern, n + 1)
                    cryptPattern[i] = ''

    def decodeChar(self, pattern, ch):
        index = pattern.index(ch)

        return self.cryptFrom[index]

    def tryDecode(self):
        successFlag = False

        strInput = input()

        encodedWords = strInput.split(" ")
        self.makeSymbolArray(encodedWords, self.cryptTo)

        if (len(self.cryptTo) > len(self.cryptFrom)):
            successFlag = False
        else:
            self.makeCryptMatrix(self.cryptMatrix, 0)
            if (self.dbgMode == True):
                print(self.cryptMatrix)

            for pattern in self.cryptMatrix:
                successFlag = True

                decodedResult = []

                for word in encodedWords:
                    temp = list(word)  # string is immutable

                    for i in range(len(word)):
                        temp[i] = self.decodeChar(pattern, word[i])

                    decodedWord = ''.join(temp)
                    if (self.dictionary.count(decodedWord) > 0):
                        if (self.dbgMode == True):
                            print("%s is found" % (decodedWord))

                        decodedResult.append(decodedWord)
                    else:
                        successFlag = False
                        break

                if (successFlag == True):
                    break

        if (successFlag == True):
            if (self.dbgMode == True):
                print("found")

            self.printDecodedWord(decodedResult)
        else:
            if (self.dbgMode == True):
                print("not found")

            self.printNotDecodedWord(encodedWords)

    def printDecodedWord(self, decodedResult):
        for word in decodedResult:
            print(word, end=' ')

    def printNotDecodedWord(self, encodedWords):
        for word in encodedWords:
            for i in range(len(word)):
                print("*", end='')

            print(" ", end='')

if __name__ == '__main__':
    dbgMode = False

    obj = CryptKicker(dbgMode)

    obj.inputDictionary()
    obj.tryDecode()

방글라데시의 정당들은 자신의 세를 과시하기 위해 정기적인 동맹 휴업(파업)을 추진한다고 합니다.

이 문제는 동맹 휴업 지수(hartal parameter)라고 부르는 h라는 양의 정수로 나타낼 수 있습니다. 이 값은 한 동맹 휴업과 다른 동맹 휴업 사이의 기간을 날짜 수로 표시한 값입니다.

세 개의 정당이 있다고 생각해봅시다. i 번째 당의 동맹 휴업 지수를 h(i) 라고 할 때, h(1) = 3, h(2) = 4, h(3) = 8 이라고 가정합니다. N일(N=14)일 동안의 세 당의 행보를 시뮬레이션하면 다음과 같이 표시할 수 있습니다. 시뮬레이션은 항상 일요일에 시작하며 금요일이나 토요일에는 동맹 휴업이 없습니다.

이 결과를 보면 14일 동안 정확하게 다섯 번의 동맹 휴업(3, 4, 8, 9, 12일)이 있음을 알 수 있습니다. 6일은 금요일이기 때문에 동맹 휴업이 일어나지 않습니다. 결국 2주 동안 근무 일수로 5일의 동맹 휴업이 실시됩니다.

몇 정당의 동맹 휴업 지수와, 어떤 정수 N이 주어졌을 때, N일 가운데 동맹 휴업으로 인해 일을 하지 않은 근무 일수를 계산해봅시다.

입력

입력의 첫째 줄에는 한 개의 정수 N(7 ≤ N ≤ 3,650)이 들어있으며 시뮬레이션을 돌릴 기간(날 수)를 나타냅니다. 그 다음 줄에는 정당의 개수를 나타내는 정수 P(1 ≤ P ≤ 100) 가 들어갑니다. 그 다음부터 시작하는 P개의 줄 가운데 i 번째 줄(1≤ i ≤ P) 에는 i번째 동맹 휴업 지수를 나타내는 양의 정수 h(i)가 들어있습니다. 이때 h(i) 값은 7의 배수가 아닙니다.

출력

각 입력에 대해 손실된 근무 일수를 한 줄에 하나씩 출력합니다.

예제

해설

기간을 입력 받고 그 갯수만큼 리스트(배열) 할당. 이 후에는 각 정당별로 휴업 일수마다 '1'로 Marking.

Marking시 금요일, 토요일일때는 수행하지 않고 건너뛰도록 해준다. 모든 정당에 대해서 수행한 뒤, 나중에 Marking된 '1'의 갯수가 몇개인지 확인하면 끝.

# Quiz 0011, Hartal
# written by badsaram

import sys

class Hartal(object):
    def __init__(self):
        self.working_day = 0
        self.member_count = 0
        self.working_states = []
        self.hartal_parameters = []

    def input(self):
        # input days
        str = input()
        if (str.isdigit() == False):
            print("Please input number for working days")
            sys.exit(-1)

        working_day = int(str)
        if ((working_day < 7) or (working_day > 3650)):
            print("Please input working days in 7 - 3650 range.")
            sys.exit(-1)

        # input member count
        str = input()
        if (str.isdigit() == False):
            print("Please input number of member count")
            sys.exit(-1)

        member_count = int(str)
        if ((member_count < 1) or (member_count > 100)):
            print("Please input member count in 1 - 100 range.")
            sys.exit(-1)

        hartal_parameters = []

        # input hartal parameter
        for i in range(member_count):
            str = input()
            if (str.isdigit() == False):
                print("Please input number for hartal parameters.")
                sys.exit(-1)

            hartal_parameters.append(int(str))

        working_states = [ 0 for i in range(working_day) ]

        self.working_day        = working_day
        self.member_count       = member_count
        self.working_states     = working_states
        self.hartal_parameters  = hartal_parameters

    def calc(self):
        if ((self.hartal_parameters == []) or (self.working_states == [])):
            print("There is no hartal parameters and working states.")
            return

        for hartal_parameter in self.hartal_parameters:
            for day in range(0, self.working_day, hartal_parameter):
                if (((day % 7) != 6) and ((day % 7) != 7) and (day != 0)):
                    self.working_states[day - 1] = 1

        print("%d" % (self.working_states.count(1)))

if __name__ == '__main__':
    obj = Hartal()

    obj.input()
    obj.calc()