結果

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

ソースコード

diff #
raw source code 

import sys
import math

def solve():
    input = sys.stdin.readline
    N = int(input())
    L = N - 1  # leading digit position (10^L place), always nonzero
    
    # Phase 1: Query (j, L) for all j < L → get d[j]*d[L]
    products = {}
    for j in range(L):
        print(f"? {j} {L}", flush=True)
        p = int(input())
        if p == -1:
            return
        products[j] = p
    
    nonzero = [j for j in range(L) if products[j] > 0]
    
    # Case: no non-zero non-leading digits → leading digit unknown
    if len(nonzero) == 0:
        print("! -1", flush=True)
        return
    
    # Case: exactly one non-zero → only one query result, may be ambiguous
    if len(nonzero) == 1:
        j1 = nonzero[0]
        p1 = products[j1]  # = d[j1] * d[L]
        solutions = [(a, p1//a) for a in range(1,10) 
                     if p1 % a == 0 and 1 <= p1//a <= 9]
        if len(solutions) == 1:
            dj1, dL = solutions[0]
            digits = [0] * N
            digits[L] = dL
            digits[j1] = dj1
            X = sum(digits[i] * (10**i) for i in range(N))
            print(f"! {X}", flush=True)
        else:
            print("! -1", flush=True)
        return
    
    # Case: 2+ non-zero positions → can determine d[L] exactly
    j1, j2 = nonzero[0], nonzero[1]
    print(f"? {j1} {j2}", flush=True)  # = d[j1]*d[j2]
    q12 = int(input())
    if q12 == -1:
        return
    
    # d[L]^2 = (d[j1]*d[L]) * (d[j2]*d[L]) / (d[j1]*d[j2])
    dL_sq = products[j1] * products[j2] // q12
    dL = round(math.isqrt(dL_sq))
    
    digits = [0] * N
    digits[L] = dL
    for j in range(L):
        digits[j] = products[j] // dL if products[j] > 0 else 0
    
    X = sum(digits[i] * (10**i) for i in range(N))
    print(f"! {X}", flush=True)

solve()
0