結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー ,
提出日時 2026-04-18 20:12:55
言語 Bash
(Bash 5.2.37)
コンパイル:
true
実行:
/usr/bin/bash _filename_
結果
WA  
実行時間 -
コード長 1,911 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 130 ms
コンパイル使用メモリ 6,400 KB
実行使用メモリ 35,700 KB
平均クエリ数 10.89
最終ジャッジ日時 2026-04-18 20:13:27
合計ジャッジ時間 13,445 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 63 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/bin/bash

read N
L=$((N - 1))

declare -a products

# Phase 1: Query (j, L) for all j < L
nonzero=()
for ((j=0; j<L; j++)); do
    echo "? $j $L"
    read p
    if [ "$p" = "-1" ]; then
        exit 0
    fi
    products[$j]=$p
    if [ "$p" -gt 0 ]; then
        nonzero+=($j)
    fi
done

# Case: no non-zero non-leading digits
if [ ${#nonzero[@]} -eq 0 ]; then
    echo "! -1"
    exit 0
fi

# Case: exactly one non-zero
if [ ${#nonzero[@]} -eq 1 ]; then
    j1=${nonzero[0]}
    p1=${products[$j1]}
    
    count=0
    sol_a=0
    sol_b=0
    for ((a=1; a<=9; a++)); do
        if [ $((p1 % a)) -eq 0 ]; then
            b=$((p1 / a))
            if [ "$b" -ge 1 ] && [ "$b" -le 9 ]; then
                count=$((count + 1))
                sol_a=$a
                sol_b=$b
            fi
        fi
    done
    
    if [ "$count" -eq 1 ]; then
        # Unique factorization
        declare -a digits
        for ((i=0; i<N; i++)); do digits[$i]=0; done
        digits[$L]=$sol_b
        digits[$j1]=$sol_a
        
        X=0
        pow=1
        for ((i=0; i<N; i++)); do
            X=$((X + digits[i] * pow))
            pow=$((pow * 10))
        done
        echo "! $X"
    else
        echo "! -1"
    fi
    exit 0
fi

# Case: 2+ non-zero positions
j1=${nonzero[0]}
j2=${nonzero[1]}
echo "? $j1 $j2"
read q12
if [ "$q12" = "-1" ]; then
    exit 0
fi

# d[L]^2 = products[j1] * products[j2] / q12
p1=${products[$j1]}
p2=${products[$j2]}
dL_sq=$(( (p1 * p2) / q12 ))

# Integer square root
dL=$(python3 -c "import math; print(round(math.isqrt($dL_sq)))")

# Build digits
declare -a digits
for ((i=0; i<N; i++)); do digits[$i]=0; done
digits[$L]=$dL

for ((j=0; j<L; j++)); do
    if [ "${products[$j]}" -gt 0 ]; then
        digits[$j]=$(( products[j] / dL ))
    fi
done

# Compute X
X=0
pow=1
for ((i=0; i<N; i++)); do
    X=$((X + digits[i] * pow))
    pow=$((pow * 10))
done

echo "! $X"
0