結果

問題 No.3081 Make Palindromic Multiple
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:58:11
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,112 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 68,276 KB
最終ジャッジ日時 2025-06-12 18:58:23
合計ジャッジ時間 10,983 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

def generate_99_bottles_lyrics():
    lyrics = []
    for num in range(99, 0, -1):
        if num == 2:
            verse = f"{num} bottles of beer on the wall, {num} bottles of beer.\nTake one down and pass it around, 1 bottle of beer on the wall.\n"
        elif num == 1:
            verse = f"{num} bottle of beer on the wall, {num} bottle of beer.\nTake one down and pass it around, no more bottles of beer on the wall.\n"
        else:
            verse = f"{num} bottles of beer on the wall, {num} bottles of beer.\nTake one down and pass it around, {num - 1} bottles of beer on the wall.\n"
        lyrics.append(verse)
    last_verse = "No more bottles of beer on the wall, no more bottles of beer.\nGo to the store and buy some more, 99 bottles of beer on the wall.\n"
    lyrics.append(last_verse)
    return ''.join(lyrics)

h = "Hello, World!"
n = generate_99_bottles_lyrics()
len_h = len(h)
len_n = len(n)

n_str = n  # the 99 Bottles lyrics

def solve():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    S = input[1].strip()
    
    # Case 1: S is exactly h
    if S == h:
        print('H')
        return
    
    # Case 2: S is exactly n
    if S == n:
        print('9')
        return
    
    # Case 3: S is exactly 'Q'
    if S == 'Q':
        print('Q')
        return
    
    # Case 4: B=0, check if S is a concatenation of h and/or n
    dp = [False] * (len(S) + 1)
    dp[0] = True
    for i in range(len(S) + 1):
        if dp[i]:
            # Check for h
            if i + len_h <= len(S):
                substring = S[i:i+len_h]
                if substring == h:
                    dp[i + len_h] = True
            # Check for n
            if i + len_n <= len(S):
                substring = S[i:i+len_n]
                if substring == n:
                    dp[i + len_n] = True
    if dp[len(S)]:
        # Backtrack to find the commands
        commands = []
        pos = len(S)
        while pos > 0:
            if pos - len_h >= 0 and S[pos - len_h:pos] == h:
                commands.append('H')
                pos -= len_h
            elif pos - len_n >= 0 and S[pos - len_n:pos] == n:
                commands.append('9')
                pos -= len_n
        commands.reverse()
        print(''.join(commands))
        return
    
    # Case 5: B=1, check if S ends with 'Q'
    if len(S) >= 1 and S[-1] == 'Q':
        D = S[:-1]
        # Check if D is composed only of 'H', '9', '+'
        valid = True
        for c in D:
            if c not in ['H', '9', '+']:
                valid = False
                break
        if valid:
            # Compute A as the output of D
            A = []
            for c in D:
                if c == 'H':
                    A.append(h)
                elif c == '9':
                    A.append(n_str)
                elif c == '+':
                    pass
            A_str = ''.join(A)
            # Check if A + D + 'Q' equals S
            if A_str + D + 'Q' == S:
                print(D + 'Q')
                return
    
    # If none of the cases apply
    print(-1)

solve()
0