結果

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

ソースコード

diff #
raw source code 

import itertools
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 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)), product_to_answer
    return None


def solve(n: int):
    assert 2 <= n
    if n == 2:
        oks = {i**2: 11 * i for i in (1, 5, 7, 8, 9)}
        product = query(0, 1)
        if product in oks:
            print(f"! {oks[product]}")
        else:
            quit()
        return
    products = [query(i, n - 1) for i in reversed(range(n - 1))]
    gcd = 0
    for product in products:
        gcd = math.gcd(gcd, product)
    if gcd == 0:
        quit()
    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:
        quit()
    indices, product_to_answer = last_query
    product = query(*indices)
    if product not in product_to_answer:
        quit()
    else:
        answer = product_to_answer[product]
        print(f"! {''.join(map(str, answer))}")


solve(int(input()))
0