結果
問題 | No.2357 Guess the Function |
ユーザー |
![]() |
提出日時 | 2023-06-24 23:54:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 1,000 ms |
コード長 | 1,322 bytes |
コンパイル時間 | 506 ms |
コンパイル使用メモリ | 64,204 KB |
実行使用メモリ | 25,604 KB |
平均クエリ数 | 2.91 |
最終ジャッジ日時 | 2024-07-02 02:31:13 |
合計ジャッジ時間 | 1,682 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
/*考えたことA = 0のときの解き方x1 = 50だとB > 50で50だらけになる。x1 = 100としてr1が返ると、100 - r1 = q1B となる。100 - r1 ≡ 0 (mod B) -> 99 - r1 ≡ -1 (mod B) ≡ B - 1 (mod B) より、r2 = B - 1。(r1 < 99よりvalidな質問)一般の解き方1回目の答えをr1として100, 99 - r1を聞くと一意に定まるのでは?と思ったが数学的に証明できていない。実験的には1≦A<B≦100の範囲で、(x1,r1,x2,r2)に対応する(A,B)が一意だったので、この制約なら正しい。-> 0≦A<B≦100でしたorz。さらにr1=99になるケースが存在し、x=0になると不正なので、このときに間違える。r1 = 99になるケースはB = 100, (100 + A) % B = 99のケースなので、A=99, B=100で確定。*/#include <iostream>using namespace std;int query(int x) {cout << "? " << x << endl;cout.flush();int r; cin >> r;return r;}void answer(int a, int b) {cout << "! " << a << " " << b << endl;}int main() {int r1 = query(100);if (r1 == 99) {answer(99, 100);return 0;}int r2 = query(99 - r1);for (int a = 0; a <= 100; a++) {for (int b = a + 1; b <= 100; b++) {if ((100 + a) % b == r1 && (99 - r1 + a) % b == r2) {answer(a, b);return 0;}}}return 0;}