結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー M Mahrus Qusaeri
提出日時 2026-04-18 01:12:58
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 205 ms / 2,000 ms
コード長 2,222 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 866 ms
コンパイル使用メモリ 20,572 KB
実行使用メモリ 35,464 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-18 01:13:39
合計ジャッジ時間 12,822 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import isqrt
input = sys.stdin.readline

def solve():
    N = int(input())

    ref = N - 1

    prods = {} 
    for k in range(N - 1):
        lo, hi = min(k, ref), max(k, ref)
        print(f"? {lo} {hi}", flush=True)
        p = int(input())
        if p == -1:
            return
        prods[k] = p
    
    nonzero_keys = [k for k in range(N-1) if prods[k] > 0]
    
    if len(nonzero_keys) == 0:

        print("! -1", flush=True)
        return
    
    if len(nonzero_keys) == 1:

        k0 = nonzero_keys[0]
        p0 = prods[k0]

        valid = []
        for dr in range(1, 10):
            if p0 % dr == 0:
                dk = p0 // dr
                if 1 <= dk <= 9:
                    valid.append((dr, dk))
        
        if len(valid) == 1:
            dr, dk = valid[0]
            digits = [0] * N
            digits[ref] = dr
            digits[k0] = dk
            X = sum(digits[i] * (10 ** i) for i in range(N))
            print(f"! {X}", flush=True)
        else:
            print("! -1", flush=True)
        return

    k0, k1 = nonzero_keys[0], nonzero_keys[1]
    p0, p1 = prods[k0], prods[k1]
    
    lo, hi = min(k0, k1), max(k0, k1)
    print(f"? {lo} {hi}", flush=True)
    q = int(input())
    if q == -1:
        return
    
    
    if q == 0:
        print("! -1", flush=True)
        return
    
    if (p0 * p1) % q != 0:
        print("! -1", flush=True)
        return
    
    dr2 = p0 * p1 // q
    dr = isqrt(dr2)
    
    if dr * dr != dr2 or not (1 <= dr <= 9):
        print("! -1", flush=True)
        return
    
    digits = [0] * N
    digits[ref] = dr
    ok = True
    for k in range(N - 1):
        if prods[k] == 0:
            digits[k] = 0
        else:
            if prods[k] % dr != 0:
                ok = False
                break
            dk = prods[k] // dr
            if not (0 <= dk <= 9):
                ok = False
                break
            digits[k] = dk
    
    if not ok:
        print("! -1", flush=True)
        return
    
    X = sum(digits[i] * (10 ** i) for i in range(N))
    
    if len(str(X)) != N:
        print("! -1", flush=True)
        return
    
    print(f"! {X}", flush=True)

solve()
0