結果

問題 No.937 Ultra Sword
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:56:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,425 bytes
コンパイル時間 487 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 53,780 KB
最終ジャッジ日時 2025-06-12 18:56:13
合計ジャッジ時間 5,891 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 3 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    n, *rest = map(int, sys.stdin.read().split())
    a = rest[:n]
    sum_total = sum(a)
    
    # Compute GCD of all elements
    g = a[0]
    for num in a[1:]:
        g = math.gcd(g, num)
    
    # Check if GCD can be generated via magic
    s = set(a)
    can_generate = False
    
    # Check XOR condition
    for num in a:
        xor_val = num ^ g
        if xor_val in s and xor_val != num:
            can_generate = True
            break
    
    # Check doubling condition
    if not can_generate:
        for num in a:
            if g % num != 0:
                continue
            q = g // num
            # Check if q is a power of two
            if (q & (q - 1)) == 0 and q != 0:
                can_generate = True
                break
    
    sum_candidate = sum_total // g if can_generate else float('inf')
    
    # Compute minimal sum when using original elements
    min_original = float('inf')
    for x in a:
        current_sum = 1  # x becomes 1
        for num in a:
            if num == x:
                continue
            if num % x == 0:
                current_sum += num // x
            else:
                current_sum += num
        if current_sum < min_original:
            min_original = current_sum
    
    # Determine the answer
    answer = min(sum_candidate, min_original)
    print(answer)

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