結果

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

ソースコード

diff #
raw source code 

import functools
import itertools
import math
import sys


def submit(answer: int):
    print(f"! {answer}")
    sys.exit(0)


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


def find_last_query(candidates, n):
    for i, j in itertools.permutations(range(n - 1), r=2):
        product_to_answer = {
            candidate[n - 1 - i] * candidate[n - 1 - j]: candidate
            for candidate in candidates
        }
        if len(product_to_answer) == len(candidates):
            return sorted((i, j)), {
                key: int("".join(map(str, value)))
                for key, value in product_to_answer.items()
            }
    return None


def solve(n: int):
    assert 2 <= n
    NOT_FOUND = -1
    if n == 2:
        oks = {i**2: 11 * i for i in (1, 5, 7, 8, 9)}
        submit(oks.get(query(0, 1), NOT_FOUND))
    products = [query(i, n - 1) for i in reversed(range(n - 1))]
    gcd = functools.reduce(math.gcd, products, 0)
    candidates = []
    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):
            candidates.append(trying)
    last_query = find_last_query(candidates, n)
    if last_query is None:
        submit(NOT_FOUND)
    indices, product_to_answer = last_query
    submit(product_to_answer.get(query(*indices), NOT_FOUND))


solve(int(input()))
0