審査員は、ある整数 $x$ を区間 $[1, n]$ から選びました。あなたの課題は、この $x$ を当てることです。完全に手探りで当てる必要がないように、質問を行うことができます。各質問において、整数 $y$ を区間 $[0, c]$ から指定することができ、その回答として $x + y$ の約数の個数が得られます。
課題を少し難しくするために、プログラムの1回の実行につき $t$ 個のテストケースを解く必要があります。これらすべてのテストケースで質問できる合計回数は $q$ 回までに制限されています。
インタラクション
この問題はインタラクティブです。提供されたライブラリを使用して審査員と通信するプログラムを作成する必要があります。ライブラリを使用するには、プログラムの先頭で以下を記述してください。
- C++:
#include "dzilib.h" - Python:
from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
ライブラリは以下の関数を提供します。
GetT()– テストケースの数 $t$ を返します。GetN()– 隠された値 $x$ の上限 $n$ を返します。GetQ()– すべての $t$ 個のテストケースを通じて質問できる合計回数の上限 $q$ を返します。GetC()– 指定できる $y$ の上限 $c$ を返します。Ask(y)– 隠された値 $x$ に $y$ を加えた値の正の約数の個数を返します。$0 \le y \le c$ を満たす必要があります。Answer(z)– 隠された値 $x$ が $z$ であるとライブラリに伝えます。戻り値はありません（C++ではvoid型）。
Pythonでは、ライブラリ関数のすべてのパラメータおよび戻り値は整数型です。C++では、関数が受け取る型および戻り値の型は、提供されたサンプルライブラリと同じです（詳細は「実装の詳細」セクションを参照）。
プログラムの実行中（終了時を除く）、常に1つのテストケースがアクティブです。最初のテストケースはプログラム開始直後にアクティブになります。テストケースがアクティブな間は、Ask 関数を使用して質問を行うことができます。隠された値 $x$ が分かったと判断したら、Answer 関数を使用して回答を送信し、ライブラリがそれを検証します。もし回答が不正であれば、ライブラリは「不正解」という判定でプログラムを終了させます。もし回答が正しければ、その関数は終了します。まだ解いていないテストケースがある場合は、直ちに次のテストケースがアクティブになります。最後のテストケースに回答した後は、プログラムを終了させる必要があります。もし終了せずに Ask や Answer を呼び出そうとすると、「不正解」という判定を受けます。
GetT、GetN、GetQ、GetC 関数はプログラムのどの時点でも呼び出すことができ、返される値は変化しません。これらの関数は質問回数の制限には含まれませんが、CPU時間を消費します。値 $q$ は Ask 関数の呼び出し回数のみを制限します。許可された合計質問回数を超えた時点で、ライブラリはプログラムを終了させ、「不正解」という判定を出します。
標準入力からデータを読み込んだり、標準出力に何かを出力したりしてはいけません。評価用ライブラリの内部動作に意図的に干渉しようとする試みは禁止されています。
ライブラリ
すべてのテストにおける隠された値 $x$ とその順序はあらかじめ決定されています。つまり、あなたのプログラムと通信するライブラリは悪意のあるものではなく、あなたのプログラムの動作に合わせて挙動を変化させることはありません。
問題文に記載されている制限は、あなたのプログラムが消費する時間とメモリのみに関するものです。ライブラリの実行時間や消費メモリは、テストやあなたのプログラムの正確な挙動に依存する場合があります。そのため、SIO2における時間とメモリの制限は、問題文に記載されているものよりもわずかに大きく設定されています。
入出力例
入力 1
2 1000000 10000 1000000000000000 1000 1
出力 1
GetT() GetN() GetQ() GetC() Ask(1) Ask(24) Answer(1000) GetT() Answer(1)
注記
サンプルテストでは $t = 2, n = 10^6, q = 10^4, c = 10^{15}$ であり、隠された値は順に $1000$ と $1$ です。Ask(1) は $8$ を返し、$x + 1$ は $1, 7, 11, 13, 77, 91, 143, 1001$ の8個の約数を持ちます。Ask(24) は $11$ を返し、$x + 24$ は $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$ の11個の約数を持ちます。Ask 質問は2回行われ、これは $10\,000$ 回の制限内に収まっています。
制約
グループ内のすべてのテストにおいて、$t, n, q, c$ は以下の表の通りです。
| グループ番号 | $t$ | $n$ | $q$ | $c$ |
|---|---|---|---|---|
| 1 | 50 | $10^5$ | 50 000 | $10^{12}$ |
| 2 | 50 | $10^6$ | 5 000 | $10^{12}$ |
| 3 | 10 | $10^9$ | 50 000 | $10^{12}$ |
| 4 | 10 | $10^{14}$ | 5 000 | $10^{17}$ |
| 5 | 10 | $10^{14}$ | 2 000 | $10^{17}$ |
| 6 | 10 | $10^{14}$ | 1 300 | $10^{17}$ |
| 7 | 10 | $10^{14}$ | 950 | $10^{17}$ |
| 8 | 10 | $10^{14}$ | 820 | $10^{17}$ |
| 9 | 10 | $10^{14}$ | 750 | $10^{17}$ |
| 10 | 10 | $10^{14}$ | 720 | $10^{17}$ |
サンプルテストはどのグループにも属しません。解くことは可能ですが、解かなくても満点を獲得できる可能性があることに留意してください。
実装の詳細
C++およびPythonのサンプル誤答プログラムとサンプルライブラリは、SIO2の「ファイル」セクションにあるアーカイブに含まれています。これらはすべての関数が受け取る型と返す型を示しています。サンプルライブラリは、評価に使用されるものとは挙動が異なる場合があり、問題の前提条件を満たさない可能性があります。これらはプログラムとの対話方法を示すためのものです。
C++の dzi.cpp は以下のコマンドでコンパイルできます。
g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20
dzilib.h と dzilib.cpp がプログラムと同じフォルダにあることを確認してください。
Pythonの dzi.py は以下のコマンドで実行できます。
python dzi.py
dzilib.py がプログラムと同じフォルダにあることを確認してください。
実行開始時、ライブラリは標準入力から順に $t, n, q, c$ の値を読み込み、続いて隠された値 $x$ を読み込みます。サンプルテストに対応する入力ファイルは、両方のアーカイブ内に dzi0.in という名前で存在します。