526互联

Codeforces Global Round 17 A. Anti Light's Cell Guessing

发布时间 2023-09-16 05:08:13作者: zsxuan

给一个 \(n \times m\) 的网格，里面藏了一个炸弹 \((x_0, y_0)\) 。你可以选择 \(k\) 个坐标 \((x_1, y_1), (x_2, y_2), \cdots, (x_k, y_k)\) 。第 \(i\) 次选择计算机会回复你一个数 \(d_i = |x_0 - x_i| + |y_0 - y_i|\) 。至少需要选出多少个坐标才能确定 \((x_0, y_0)\) 的位置？

观察：\(d_i\) 意味着 \((x_i, y_i)\) 半径为 \(d_i\) 的边上有炸弹。

  • 当 \(n = 1, m = 1\) ，选择 \(0\) 次可以确定炸弹位置。
  • 当 \(min(n,m) = 1, max(n, m) > 1\)
    • 若选任意位置，圆和坐标轴至多有 \(2\) 个交点，即至多选 \(2\) 次确定。
    • 若选择端点，圆和坐标轴只有 \(1\) 个交点，可以确定炸弹位置。故答案为 \(1\) 。
  • 当 \(min(n,m) > 1\)
    • 若选任意两个点，他们的圆最多至多存在两个交点，即至多选 \(3\) 次确定。
    • 当选择的两个点在同一条网格边上，他们的圆只有一个交点，至多选 \(2\) 次确定。故答案为 \(2\) 。
view 
#include <bits/stdc++.h>
void solve() {
	int n, m; std::cin >> n >> m;
	if (std::max(n, m) == 1) std::cout << 0 << '\n';
	else if (std::min(n, m) == 1 && std::max(n, m) > 1) std::cout << 1 << '\n';
	else std::cout << 2 << '\n';
}
signed main() {
    int _ = 1; std::cin >> _;
    while (_--) solve();
	return 0;
}