倒水问题 |||||

题目描述泊松是法国数学家、物理学家和力学家。他一生致力科学事业成果颇多。有许多著名的公式定理以他的名字命名比如概率论中著名的泊松分布。有一次闲暇时他提出过一个有趣的问题后称为“泊松分酒”。在我国古代也提出过类似问题遗憾的是没有进行彻底探索其中流传较多是“韩信走马分油”问题。有 333 个容器容量分别为 121212 升888 升555 升。其中 121212 升中装满油另外两个空着。要求你只用 333 个容器操作最后使得某个容器中正好有 666 升油。下面的列表是可能的操作状态记录12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每行 333 个数据分别表示 12,8,612, 8, 612,8,6 升容器中的油量第一行表示初始状态第二行表示把 121212 升倒入 888 升容器后的状态第三行是 888 升倒入 555 升...当然同一个题目可能有多种不同的正确操作步骤。输入输入各个容器的容量开始的状态和要求的目标油量输入保证只有三个容器输入保证按照容器的容量大小按照降序给出保证所有数据都不会超过100输出程序通过计算输出一种实现的步骤不需要找到所有可能的方法。如果没有可能实现则输出不可能。输入输出样例样例输入 #1复制12,8,5,12,0,0,6样例输出 #1复制12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5提示如果对答案判定有异议请联系编写此题数据的对应管理员#define _CRT_SECURE_NO_WARNINGS #includecstdio #includeiostream #includevector #includeunordered_map using namespace std; int va, vb, vc, tar, sa, sb, sc; bool flag false; struct node { int a, b, c; }; vectorstruct nodepath; auto ans path; bool check(int a,int b,int c) { for (auto e : path) { if (a e.a b e.b c e.c) return false; } return true; } void dfs(int a, int b, int c) { //cout a b c \n; if (a tar || b tar || c tar) { flag true; ans path; return; } int na 0, nb 0, nc 0; //a-b int ab min(a, vb - b); if (ab 0) { na a - ab; nb b ab; nc c; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } //a-c int ac min(a, vc - c); if (ac 0) { na a - ac; nb b; nc c ac; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } //b-a int ba min(b, va - a); if (ba 0) { na a ba; nb b - ba; nc c; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } //b-c int bc min(b, vc - c); if (bc 0) { na a; nb b - bc; nc c bc; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } //c-a int ca min(c, va - a); if (ca 0) { na a ca; nb b; nc c - ca; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } //c-b int cb min(c, vb - b); if (cb 0) { na a; nb b cb; nc c - cb; if (check(na, nb, nc)) { path.push_back({ na,nb,nc }); dfs(na, nb, nc); path.pop_back(); } } } int main() { scanf(%d,%d,%d,%d,%d,%d,%d, va, vb, vc, sa, sb, sc, tar); path.push_back({ sa,sb,sc }); dfs(sa, sb, sc); if (flag) { for (auto e : ans) cout e.a , e.b , e.c \n; } else cout 不可能\n; return 0; }