結果

問題 No.3081 Make Palindromic Multiple
ユーザー lam6er
提出日時 2025-04-16 15:27:19
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,409 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 81,820 KB
実行使用メモリ 67,256 KB
最終ジャッジ日時 2025-04-16 15:29:18
合計ジャッジ時間 10,842 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

def generate_song():
    s = []
    for i in range(99, 0, -1):
        line1 = f"{i} bottle{'s' if i > 1 else ''} of beer on the wall, {i} bottle{'s' if i > 1 else ''} of beer."
        s.append(line1)
        next_num = i - 1 if i - 1 else 'no more'
        plural = 's' if (i - 1 != 1 and i - 1 != 0) else ''
        line2 = f"Take one down and pass it around, {next_num} bottle{plural} of beer on the wall."
        s.append(line2)
    s.append("No more bottles of beer on the wall, no more bottles of beer.")
    s.append("Go to the store and buy some more, 99 bottles of beer on the wall.")
    return '\n'.join(s) + '\n'

H_str = "Hello, World!"
song_str = generate_song()

def can_split_into_h_and_song(s, h_str, song_str):
    len_h = len(h_str)
    len_song = len(song_str)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(n):
        if dp[i]:
            if i + len_h <= n and s[i:i+len_h] == h_str:
                dp[i+len_h] = True
            if i + len_song <= n and s[i:i+len_song] == song_str:
                dp[i+len_song] = True
    return dp[n]

def generate_hq9_code(s):
    if s == H_str:
        return 'H'
    if s == song_str:
        return '9'
    if s == 'Q':
        return 'Q'
    if can_split_into_h_and_song(s, H_str, song_str):
        code = []
        i = 0
        len_h = len(H_str)
        len_song = len(song_str)
        while i < len(s):
            if s.startswith(H_str, i):
                code.append('H')
                i += len_h
            elif s.startswith(song_str, i):
                code.append('9')
                i += len_song
            else:
                return '-1'
        return ''.join(code)
    if len(s) >= 2 and s[0] == 'Q':
        remaining = s[1:]
        code_candidate = 'QH'
        if s.startswith(code_candidate) and remaining[len(code_candidate)-1:] == H_str:
            return code_candidate
        code_candidate = 'Q9'
        if s.startswith(code_candidate) and remaining[len(code_candidate)-1:] == song_str:
            return code_candidate
    if len(s) >= 2 and s.startswith('QH'):
        remaining = s[2:]
        if remaining == H_str:
            return 'QH'
    if len(s) >= 2 and s.startswith('Q9'):
        remaining = s[2:]
        if remaining == song_str:
            return 'Q9'
    return '-1'

n = int(input())
s = input().strip()

result = generate_hq9_code(s)
print(result)
0