結果
| 問題 |
No.3018 目隠し宝探し
|
| ユーザー |
 eom2357
|
| 提出日時 | 2025-07-02 00:55:51 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,024 bytes |
| コンパイル時間 | 1,196 ms |
| コンパイル使用メモリ | 90,888 KB |
| 実行使用メモリ | 26,320 KB |
| 平均クエリ数 | 2.68 |
| 最終ジャッジ日時 | 2025-07-02 00:55:56 |
| 合計ジャッジ時間 | 4,073 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 15 WA * 6 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:242:37: warning: ‘final_i’ may be used uninitialized [-Wmaybe-uninitialized]
242 | std::cout << "! " << final_i << " " << final_j << std::endl;
| ^~~
main.cpp:31:9: note: ‘final_i’ was declared here
31 | int final_i, final_j;
| ^~~~~~~
main.cpp:242:44: warning: ‘final_j’ may be used uninitialized [-Wmaybe-uninitialized]
242 | std::cout << "! " << final_i << " " << final_j << std::endl;
| ^~~~~~~
main.cpp:31:18: note: ‘final_j’ was declared here
31 | int final_i, final_j;
| ^~~~~~~
ソースコード
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm> // for std::min and std::max
// 標準出力をフラッシュするヘルパー関数
void flush_stdout() {
std::cout << std::flush;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int H, W;
std::cin >> H >> W;
long long d1, d2;
// 1回目の質問: マス (1, 1)
std::cout << "? 1 1" << std::endl;
flush_stdout();
std::cin >> d1;
if (d1 == -1) {
return 0; // エラー終了
}
// H=1 の場合、行は確定 (i=1)
// W=1 の場合、列は確定 (j=1)
int final_i, final_j;
if (H == 1 && W == 1) {
final_i = 1;
final_j = 1;
} else if (H == 1) { // H=1の場合、iは確定
final_i = 1;
// j を特定するために、マス (1, W) を質問
std::cout << "? 1 " << W << std::endl;
flush_stdout();
std::cin >> d2;
if (d2 == -1) {
return 0; // エラー終了
}
// d1 = (1-1)^2 + (j-1)^2 = (j-1)^2
// d2 = (1-1)^2 + (j-W)^2 = (j-W)^2
// (j-1)^2 = d1
// (j-W)^2 = d2
// (j-1)^2 - (j-W)^2 = d1 - d2
// (j^2 - 2j + 1) - (j^2 - 2Wj + W^2) = d1 - d2
// -2j + 1 + 2Wj - W^2 = d1 - d2
// 2j(W-1) = d1 - d2 - 1 + W^2
// j = (d1 - d2 - 1 + W*W) / (2 * (W-1)) + 1
// よりシンプルな導出:
// (j-1)^2 = d1
// j-1 = sqrt(d1) (j-1 >= 0)
// j = 1 + sqrt(d1)
// または
// j-1 = -sqrt(d1) (j-1 < 0)
// j = 1 - sqrt(d1)
// 適応的ジャッジのため、sqrt(d1)はj-1か-(j-1)のどちらかになる
// (j-1)^2 = d1
// (j-W)^2 = d2
// この2つからjを求める
// j^2 - 2j + 1 = d1
// j^2 - 2Wj + W^2 = d2
// 上の式から下の式を引くと
// (-2j + 2Wj) + (1 - W^2) = d1 - d2
// 2j(W-1) = d1 - d2 - 1 + W^2
// j = (d1 - d2 - 1 + W*W) / (2.0 * (W-1)) + 1
// この計算は浮動小数点になるため、整数で扱う場合は注意が必要
// d1 - (j-1)^2 = 0
// d2 - (j-W)^2 = 0
// d1 + 2Wj - W^2 = d2 + 2j - 1 (j^2項が消える)
// 2j(W-1) = d2 - d1 - 1 + W^2
// j = (d2 - d1 - 1 + W*W) / (2 * (W-1)) + 1
// W=1ではないので、W-1 > 0
// d1は(j-1)^2
// d2は(j-W)^2
// jを特定するために、もう一つ点を質問する必要はない
// d1からjの候補を絞り、d2からその候補を検証
// sqrt(d1) を s1とする。 j = 1 + s1 もしくは j = 1 - s1
// sqrt(d2) を s2とする。 j = W + s2 もしくは j = W - s2
// (j-1)^2 = d1 より j-1 = k (k=sqrt(d1) or -sqrt(d1))
// (j-W)^2 = d2 より j-W = m (m=sqrt(d2) or -sqrt(d2))
// j = 1 + k
// j = W + m
// 1 + k = W + m => k - m = W - 1
// kとmはそれぞれsqrt(d1)とsqrt(d2)の正負どちらか
// 4通りの組み合わせを試して、一致するjを探す
for (long long k_val : {static_cast<long long>(std::sqrt(d1)), -static_cast<long long>(std::sqrt(d1))}) {
if ((k_val * k_val) != d1) continue; // k_valが整数にキャストされた結果なので元のd1と一致するか確認
long long current_j = 1 + k_val;
if (current_j >= 1 && current_j <= W) {
if (((current_j - W) * (current_j - W)) == d2) {
final_j = static_cast<int>(current_j);
break;
}
}
}
} else if (W == 1) { // W=1の場合、jは確定
final_j = 1;
// i を特定するために、マス (H, 1) を質問
std::cout << "? " << H << " 1" << std::endl;
flush_stdout();
std::cin >> d2;
if (d2 == -1) {
return 0; // エラー終了
}
// d1 = (i-1)^2 + (1-1)^2 = (i-1)^2
// d2 = (i-H)^2 + (1-1)^2 = (i-H)^2
// 上と同様にiを特定
for (long long k_val : {static_cast<long long>(std::sqrt(d1)), -static_cast<long long>(std::sqrt(d1))}) {
if ((k_val * k_val) != d1) continue;
long long current_i = 1 + k_val;
if (current_i >= 1 && current_i <= H) {
if (((current_i - H) * (current_i - H)) == d2) {
final_i = static_cast<int>(current_i);
break;
}
}
}
} else { // H > 1 かつ W > 1 の場合
// マス (1, W) を質問して d2 を得る
// これにより、(i-1)^2 と (j-W)^2 の情報が得られる
std::cout << "? 1 " << W << std::endl;
flush_stdout();
std::cin >> d2;
if (d2 == -1) {
return 0; // エラー終了
}
// d1 = (i-1)^2 + (j-1)^2
// d2 = (i-1)^2 + (j-W)^2
// d1 - d2 = (j-1)^2 - (j-W)^2
// d1 - d2 = (j^2 - 2j + 1) - (j^2 - 2Wj + W^2)
// d1 - d2 = -2j + 1 + 2Wj - W^2
// d1 - d2 = 2j(W-1) + 1 - W^2
// 2j(W-1) = d1 - d2 - 1 + W^2
// j = (d1 - d2 - 1 + W*W) / (2.0 * (W-1)) + 1
// 浮動小数点誤差を避けるため、整数で計算
// (j-1)^2 は d1 - (i-1)^2
// (j-W)^2 は d2 - (i-1)^2
// よって、d1 - (i-1)^2 と d2 - (i-1)^2 の差が一定
// この差を利用してjを決定します。
// sqrt(d1)とsqrt(d2)を考慮して、jを特定
// (i-1)^2 = A
// (j-1)^2 = B
// (j-W)^2 = C
// A + B = d1
// A + C = d2
// C - B = d2 - d1
// (j-W)^2 - (j-1)^2 = d2 - d1
// j^2 - 2Wj + W^2 - (j^2 - 2j + 1) = d2 - d1
// -2Wj + W^2 + 2j - 1 = d2 - d1
// 2j(1-W) + W^2 - 1 = d2 - d1
// 2j(1-W) = d2 - d1 - W^2 + 1
// j = (d2 - d1 - W*W + 1) / (2.0 * (1-W))
// これでjが求まります。
// 適応的ジャッジのため、複数の候補がある場合でも、
// 1つの質問でi座標の候補が2つ、もう1つの質問でj座標の候補が2つ
// 合計4つの交点候補がある可能性がある。
// しかし、実際には2つの質問で一意に定まることが多い。
// 確実な方法: 2点からの距離で円の方程式を立て、交点を求める
// 宝物の座標を (r, c) とする
// (r-1)^2 + (c-1)^2 = d1
// (r-1)^2 + (c-W)^2 = d2
// 上記2式から (r-1)^2 を消去
// d1 - (c-1)^2 = d2 - (c-W)^2
// d1 - (c^2 - 2c + 1) = d2 - (c^2 - 2Wc + W^2)
// d1 - c^2 + 2c - 1 = d2 - c^2 + 2Wc - W^2
// 2c - 2Wc = d2 - d1 - W^2 + 1
// 2c(1 - W) = d2 - d1 - W^2 + 1
// c = (d2 - d1 - W*W + 1) / (2.0 * (1 - W))
// if (1 - W == 0) (i.e. W == 1) then this formula is invalid
// W != 1 の場合、上記の式で c が一意に定まる。
// H != 1 の場合、r を求めるために同様に (1,1) と (H,1) で質問が必要？
// いいえ、2回で特定する必要がある。
// d1: (r-1)^2 + (c-1)^2
// d2: (r-1)^2 + (c-W)^2
// ここで r と c を直接計算する
// 実際には2つの質問で (i-1)^2 と (j-1)^2 を特定する。
// d1 = (i-1)^2 + (j-1)^2
// d2 = (i-1)^2 + (j-W)^2
// x = i-1
// y = j-1
// z = j-W
// x^2 + y^2 = d1
// x^2 + z^2 = d2
// y = j-1
// z = j-W = (j-1) - (W-1) = y - (W-1)
// x^2 + y^2 = d1
// x^2 + (y - (W-1))^2 = d2
// (y - (W-1))^2 = d2 - x^2
// y^2 - 2y(W-1) + (W-1)^2 = d2 - x^2
// d1 - x^2 - 2y(W-1) + (W-1)^2 = d2 - x^2
// d1 - 2y(W-1) + (W-1)^2 = d2
// 2y(W-1) = d1 + (W-1)^2 - d2
// y = (d1 + (W-1)*(W-1) - d2) / (2.0 * (W-1))
// もし W-1 が 0 なら (W=1の場合)、この式は使えない。
// 上で W=1 の場合はすでに処理済み。
long long y_val_times_2_W_minus_1 = d1 + (long long)(W-1)*(W-1) - d2;
long long divisor_for_y = 2 * (W-1);
// yが整数であることを確認し、除算
// y = j-1
final_j = 1 + static_cast<int>(y_val_times_2_W_minus_1 / divisor_for_y);
// x^2 = d1 - y^2
// x^2 = d1 - (final_j - 1)^2
long long x_squared = d1 - (long long)(final_j - 1)*(final_j - 1);
final_i = 1 + static_cast<int>(std::sqrt(x_squared));
// x = i-1 なので、i = 1 + x
// xは正の値を取るようにすることで、1 <= i <= H の範囲で妥当な値になるはず。
// 適応的ジャッジのため、sqrt(x_squared)は適切な値になる
}
// 解答を出力
std::cout << "! " << final_i << " " << final_j << std::endl;
flush_stdout();
return 0;
}