結果

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

ソースコード

diff #
raw source code 

import sys
import math

def ask(a: int, b: int) -> int:
    print(f"? {a} {b}", flush=True)
    line = sys.stdin.readline()
    if not line:
        sys.exit(0)
    v = int(line)
    if v == -1:
        # Invalid query format / exceeded limit / judge terminated
        sys.exit(0)
    return v

def answer(val):
    print(f"! {val}", flush=True)
    sys.exit(0)

def main():
    line = sys.stdin.readline()
    if not line:
        return
    N = int(line)
    msd = N - 1  # most significant digit index

    y = [0] * (N - 1)
    nz = []

    # Query products with the most significant digit.
    for i in range(N - 1):
        p = ask(i, msd)
        y[i] = p
        if p > 0:
            nz.append(i)

    digits = [0] * N

    if len(nz) >= 2:
        a, b = nz[0], nz[1]
        z = ask(a, b)  # x_a * x_b
        if z <= 0:
            answer(-1)

        num = y[a] * y[b]
        if num % z != 0:
            answer(-1)

        c2 = num // z
        c = math.isqrt(c2)
        if c * c != c2 or not (1 <= c <= 9):
            answer(-1)

        digits[msd] = c
        for i in range(N - 1):
            if y[i] % c != 0:
                answer(-1)
            d = y[i] // c
            if not (0 <= d <= 9):
                answer(-1)
            digits[i] = d

        ans = "".join(str(digits[i]) for i in range(N - 1, -1, -1))
        answer(ans)

    elif len(nz) == 1:
        i = nz[0]
        p = y[i]

        cand = []
        for c in range(1, 10):
            if p % c == 0:
                d = p // c
                if 1 <= d <= 9:
                    cand.append((c, d))

        if len(cand) != 1:
            answer(-1)

        c, d = cand[0]
        digits[msd] = c
        digits[i] = d
        ans = "".join(str(digits[k]) for k in range(N - 1, -1, -1))
        answer(ans)

    else:
        # All y[i] are 0 -> x_i=0 for all i<N-1, but leading digit c is unknown.
        answer(-1)

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