結果

問題 No.3081 Make Palindromic Multiple
ユーザー qwewe
提出日時 2025-05-14 13:07:31
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,909 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 67,896 KB
最終ジャッジ日時 2025-05-14 13:09:21
合計ジャッジ時間 11,187 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read input N and S
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()

    # Precompute prefix information:
    # q_count[i] stores the count of 'Q' characters in the prefix S[0...i-1].
    # has_H[i] is True if the prefix S[0...i-1] contains the character 'H'.
    # has_9[i] is True if the prefix S[0...i-1] contains the character '9'.
    # Note: Since the problem states S contains only alphabet characters, '9' will never appear.
    # The check for '9' is technically redundant but kept for logical completeness based on HQ9+ rules.
    q_count = [0] * (N + 1)
    has_H = [False] * (N + 1)
    has_9 = [False] * (N + 1) # This will always remain False for inputs following problem constraints

    for i in range(N):
        # The values for prefix length i+1 are based on prefix length i
        q_count[i+1] = q_count[i]
        has_H[i+1] = has_H[i]
        has_9[i+1] = has_9[i]
        
        # Update based on the character S[i]
        current_char = S[i]
        if current_char == 'Q':
            q_count[i+1] += 1
        elif current_char == 'H':
            has_H[i+1] = True
        # This case `current_char == '9'` will not happen based on problem constraints.
        # elif current_char == '9': 
        #     has_9[i+1] = True

    # Find all divisors of N. These are the potential values for k.
    divisors = []
    sqrt_N = int(N**0.5)
    for k_cand in range(1, sqrt_N + 1):
         if N % k_cand == 0:
             # Add the divisor k_cand
             divisors.append(k_cand)
             # If N is not a perfect square, add the corresponding divisor N // k_cand
             if k_cand * k_cand != N:
                 divisors.append(N // k_cand)
    
    # Variable to track if a solution is found
    found_solution = False

    # Iterate through each divisor k
    for k in divisors:
        # If k is the number of repetitions, the potential source code P
        # must have length NP = N / k.
        NP = N // k
        
        # The potential source code P would be the prefix of S of length NP.
        # P = S[0...NP-1]

        # We need to check three conditions for P to be a valid source code generating S:
        
        # Condition 1: S must be formed by repeating P exactly k times.
        # This is equivalent to checking if S has a period of length NP.
        # We check this by comparing S[i] with S[i - NP] for relevant indices.
        is_periodic = True
        # Loop runs from index NP up to N-1. If NP=N (k=1), loop range is empty.
        for i in range(NP, N):
            if S[i] != S[i - NP]:
                is_periodic = False
                break
        
        # If S is not P repeated k times, this k is not valid. Skip to the next divisor.
        if not is_periodic:
            continue

        # Condition 2: The number of 'Q' characters in P must be exactly k.
        # We use the precomputed q_count array for efficiency. QP is count of Q in S[0...NP-1].
        QP = q_count[NP]
        if QP != k:
            continue

        # Condition 3: P must not contain 'H' or '9'.
        # Check using precomputed flags for prefix S[0...NP-1].
        # Since '9' is not an alphabet character, has_9[NP] will be False based on constraints.
        # We primarily need to check for 'H'.
        if has_H[NP] or has_9[NP]: # has_9[NP] check is technically redundant
            continue

        # If all three conditions are met, P = S[0...NP-1] is a valid HQ9+ source code.
        # Output the found source code P.
        sys.stdout.write(S[:NP] + '\n') 
        found_solution = True
        # Break the loop since we only need to find one valid source code.
        break 

    # If the loop completes without finding any valid source code
    if not found_solution:
        # Output -1 as required.
        sys.stdout.write("-1\n")

# Call the main solve function
solve()
0