比赛 2025暑期集训第7场 评测结果 AAAAAAAAAA
题目名称 倒水 最终得分 100
用户昵称 xpb 运行时间 0.036 s
代码语言 C++ 内存使用 3.82 MiB
提交时间 2025-08-11 16:26:49
显示代码纯文本
#include <bits/stdc++.h>>
using namespace std;
struct S {
	int a, b, c, s;
};
int A, B, C, x;
int m = INT_MAX;
bool f = false;

bool t(int a, int b, int c) {
	return a == x || b == x || c == x;
}

S p(int a, int b, int c, int f, int t, int s) {
	S r;
	r.s = s + 1;

	if (f == 0) {
		if (t == 1) {
			int d = min(a, B - b);
			r.a = a - d;
			r.b = b + d;
			r.c = c;
		} else {
			int d = min(a, C - c);
			r.a = a - d;
			r.b = b;
			r.c = c + d;
		}
	} else if (f == 1) {
		if (t == 0) {
			int d = min(b, A - a);
			r.a = a + d;
			r.b = b - d;
			r.c = c;
		} else {
			int d = min(b, C - c);
			r.a = a;
			r.b = b - d;
			r.c = c + d;
		}
	} else {
		if (t == 0) {
			int d = min(c, A - a);
			r.a = a + d;
			r.b = b;
			r.c = c - d;
		} else {
			int d = min(c, B - b);
			r.a = a;
			r.b = b + d;
			r.c = c - d;
		}
	}

	return r;
}
void dfs(int a, int b, int c, int s, vector<vector<vector<bool> > >& v) {
	if (s >= m) return;

	if (t(a, b, c)) {
		if (s < m) {
			m = s;
			f = true;
		}
		return;
	}

	if (v[a][b][c]) return;
	v[a][b][c] = true;

	S s1 = p(a, b, c, 0, 1, s);
	dfs(s1.a, s1.b, s1.c, s1.s, v);
	S s2 = p(a, b, c, 0, 2, s);
	dfs(s2.a, s2.b, s2.c, s2.s, v);
	S s3 = p(a, b, c, 1, 0, s);
	dfs(s3.a, s3.b, s3.c, s3.s, v);
	S s4 = p(a, b, c, 1, 2, s);
	dfs(s4.a, s4.b, s4.c, s4.s, v);
	S s5 = p(a, b, c, 2, 0, s);
	dfs(s5.a, s5.b, s5.c, s5.s, v);
	S s6 = p(a, b, c, 2, 1, s);
	dfs(s6.a, s6.b, s6.c, s6.s, v);

	v[a][b][c] = false;
}

int main() {
	freopen("pourwater.in", "r", stdin);
	freopen("pourwater.out", "w", stdout);

	cin >> A >> B >> C >> x;

	if (A == x) {
		cout << 0 << endl;
		return 0;
	}

	vector<vector<vector<bool> > > v(A+1, vector<vector<bool> >(B+1, vector<bool>(C+1, false)));
	dfs(A, 0, 0, 0, v);

	if (f) cout << m << endl;
	else cout << "false" << endl;

	return 0;
}