#chokudai今日の一問
3日目は,
今日の一門はPyramid!300点問題ながら参加者の多くを苦しめた一問。何度か言及してるので、解いてる人も多そうな問題かな。https://t.co/YQYRDqrt7t#chokudai今日の一問
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) August 21, 2019
ABC#112 C. Pyramid
X, Y が 0から100までなので,全探索すればよさそう.
hi が全部0のときが注意,なのか? とか思ったけど,解説読むとそれはないのか.
とりあえず,hi が 0ではない組をどれか選んでおいて,そこを基準にする,という感じ.
#include <algorithm> #include <cmath> #include <cstdio> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <sstream> #include <string> using namespace std; static int N; static vector<int> X; static vector<int> Y; static vector<long long> H; void solve(int x0, int y0, long long h0) { for (int cx = 0; cx <= 100; cx++) { for (int cy = 0; cy <= 100; cy++) { long long ch = h0 + abs(x0 - cx) + abs(y0 - cy); bool flag = true; for (int i = 0; i < N; i++) { long long temp = ch - (abs(X[i] - cx) + abs(Y[i] - cy)); if (temp < 0) { temp = 0; } if (temp != H[i]) { flag = false; break; } } if (flag) { printf("%d %d %lld\n", cx, cy, ch); return; } } } } int main() { cin >> N; X.resize(N); Y.resize(N); H.resize(N); int x0 = 0; int y0 = 0; long long h0 = 0; for (int i = 0; i < N; i++) { int x, y; long long h; cin >> x >> y >> h; X[i] = x; Y[i] = y; H[i] = h; if (h > 0) { x0 = x; y0 = y; h0 = h; } } solve(x0, y0, h0); return 0; }