結果

問題 No.295 hel__world
ユーザー gew1fw
提出日時 2025-06-12 12:53:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,565 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 179,288 KB
最終ジャッジ日時 2025-06-12 12:56:57
合計ジャッジ時間 5,326 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    # Read S_alpha
    S_alpha = list(map(int, sys.stdin.readline().split()))
    T = sys.stdin.readline().strip()
    
    # Compute T_compressed
    T_compressed = []
    prev = ''
    for c in T:
        if c != prev:
            T_compressed.append(c)
            prev = c
    
    # Check if all characters in T_compressed have S_alpha >=1
    for c in T_compressed:
        idx = ord(c) - ord('a')
        if S_alpha[idx] < 1:
            print(0)
            return
    
    # Check if the number of blocks for each character in T_compressed <= S_alpha[c]
    char_count = defaultdict(int)
    for c in T_compressed:
        char_count[c] += 1
    for c, cnt in char_count.items():
        idx = ord(c) - ord('a')
        if cnt > S_alpha[idx]:
            print(0)
            return
    
    # Split T into runs and check if the characters match T_compressed
    runs = []
    prev = ''
    run_char = []
    for c in T:
        if c != prev:
            runs.append(c)
            prev = c
    if runs != T_compressed:
        print(0)
        return
    
    # Now, for each character c in T_compressed, compute the product
    total_product = 1
    log_total = 0.0
    hel_threshold = 62 * 0.69314718056  # ln(2^62) = 62*ln(2)
    overflow = False
    
    # Count the number of blocks for each character in T_compressed
    char_blocks = defaultdict(int)
    for c in T_compressed:
        char_blocks[c] += 1
    
    for c in T_compressed:
        # To avoid processing the same character multiple times
        if c not in char_blocks:
            continue
        m_c = char_blocks[c]
        idx = ord(c) - ord('a')
        S_c = S_alpha[idx]
        sum_min = m_c  # since each block requires at least 1
        if sum_min > S_c:
            print(0)
            return
        rem_c = S_c - sum_min
        base = rem_c // m_c
        extra = rem_c % m_c
        
        # Compute the product contribution for this character
        # (base +1) ** (m_c - extra) * (base +2) ** extra
        # Compute in log space to check overflow
        contrib = 1
        log_contrib = 0.0
        if base + 1 > 0:
            log_contrib += (m_c - extra) * (base + 1).bit_length()
        if base + 2 > 0 and extra > 0:
            log_contrib += extra * (base + 2).bit_length()
        # Check if the product exceeds 2^62
        # But better to compute in logarithms
        # Using natural logarithm
        for _ in range(m_c - extra):
            term = base + 1
            if term == 0:
                continue
            log_total += (term).bit_length() * 0.69314718056  # Approximation ln(2^x) = x*ln(2)
        for _ in range(extra):
            term = base + 2
            if term == 0:
                continue
            log_total += (term).bit_length() * 0.69314718056
        if log_total >= hel_threshold:
            overflow = True
        
        # Compute actual product if not overflow
        if not overflow:
            part1 = pow(base + 1, m_c - extra)
            part2 = pow(base + 2, extra)
            contrib = part1 * part2
            if total_product > (1 << 62) // contrib:
                overflow = True
            else:
                total_product *= contrib
                if total_product > (1 << 62):
                    overflow = True
        
        # Remove the character to avoid reprocessing
        del char_blocks[c]
    
    if overflow:
        print("hel")
    else:
        print(total_product)

if __name__ == "__main__":
    main()
0