結果

問題 No.3501 Digit Products 2
コンテスト
ユーザー Naru820
提出日時 2026-03-28 04:47:24
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,367 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,883 ms
コンパイル使用メモリ 167,572 KB
実行使用メモリ 30,320 KB
平均クエリ数 1.00
最終ジャッジ日時 2026-04-17 19:48:58
合計ジャッジ時間 19,710 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 72
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//gemini 
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // 入出力の高速化はインタラクティブ問題では外すか、適宜flushする
    int N;
    if (!(cin >> N)) return 0;

    vector<int> P(N - 1);
    // N-1回の質問: 10^{N-1} の位と、10^i の位の積を聞く
    for (int i = 0; i < N - 1; ++i) {
        cout << "? " << N - 1 << " " << i << endl;
        cin >> P[i];
        if (P[i] == -1) return 0;
    }

    vector<int> C; // d_{N-1} の候補
    for (int x = 1; x <= 9; ++x) {
        bool ok = true;
        for (int i = 0; i < N - 1; ++i) {
            if (P[i] % x != 0) {
                ok = false;
                break;
            }
            if (P[i] / x > 9) {
                ok = false;
                break;
            }
        }
        if (ok) {
            C.push_back(x);
        }
    }

    // 候補が1つの場合は即座に特定可能
    if (C.size() == 1) {
        int x = C[0];
        string ans = to_string(x);
        for (int i = N - 2; i >= 0; --i) {
            ans += to_string(P[i] / x);
        }
        cout << "! " << ans << endl;
        return 0;
    }

    // 候補が複数ある場合、非ゼロの P[i] の数を数える
    vector<int> nonzero_idx;
    for (int i = 0; i < N - 1; ++i) {
        if (P[i] > 0) {
            nonzero_idx.push_back(i);
        }
    }

    // 非ゼロの要素が1つ以下なら、他のどの質問をしても0しか返ってこないため特定不可
    if (nonzero_idx.size() <= 1) {
        cout << "! -1" << endl;
        return 0;
    }

    // 非ゼロの要素が2つ以上あるなら、最後の1回の質問で一意に特定可能
    int u = nonzero_idx[0];
    int v = nonzero_idx[1];
    cout << "? " << u << " " << v << endl;
    
    int A;
    cin >> A;
    if (A == -1) return 0;

    int final_x = -1;
    for (int x : C) {
        // 条件に合致する x を見つける
        if ((P[u] / x) * (P[v] / x) == A) {
            final_x = x;
            break;
        }
    }

    if (final_x == -1) {
        cout << "! -1" << endl;
        return 0;
    }

    // X を復元して出力
    string ans = to_string(final_x);
    for (int i = N - 2; i >= 0; --i) {
        ans += to_string(P[i] / final_x);
    }
    cout << "! " << ans << endl;

    return 0;
}
0