結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー arahi10
提出日時 2026-09-30 16:57:05
言語 Python3
(3.14.7 + numpy 2.5.2 + scipy 1.18.0 + ACL)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 1,108 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 55 ms
コンパイル使用メモリ 15,104 KB
実行使用メモリ 11,264 KB
平均クエリ数 11.21
最終ジャッジ日時 2026-09-30 16:57:16
合計ジャッジ時間 7,718 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19 WA * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
import sys


def quit():
    print("! -1")
    sys.exit(0)


def query(x, y):
    print(f"? {x} {y}")
    output = int(input())
    if output == -1:
        sys.exit()
    return output


def solve(n: int):
    assert 2 <= n
    if n == 2:
        if query(0, 1) == 1:
            print("! 11")
        else:
            quit()
        return
    products = [query(i, n - 1) for i in range(n - 1)]
    products.reverse()
    gcd = products[0]
    for product in products:
        gcd = math.gcd(gcd, product)
    if gcd == 0:
        quit()
    candidates = []
    last_query = query(0, 1)
    for first_digit in range(1, 10):
        if gcd % first_digit != 0:
            continue
        trying = [first_digit]
        trying.extend(product // first_digit for product in products)
        if (
            all(0 <= digit <= 9 for digit in trying)
            and last_query != trying[-1] * trying[-2]
        ):
            candidates.append(trying)
    if len(candidates) != 1:
        quit()
    else:
        print(f"! {candidates[0]}")


if __name__ == "__main__":
    solve(int(input()))
0