题目描述题目要求解决水壶问题。给定两个容量分别为CaC_aCa​和CbC_bCb​的水壶Ca≤CbC_a \le C_bCa​≤Cb​以及目标水量NNNN≤CbN \le C_bN≤Cb​。允许操作fill A将AAA壶装满fill B将BBB壶装满empty A倒空AAA壶empty B倒空BBB壶pour A B将AAA壶中的水倒入BBB壶直到AAA空或BBB满pour B A将BBB壶中的水倒入AAA壶直到BBB空或AAA满success表示目标达成需要输出一系列操作步骤使得最终BBB壶中有恰好NNN加仑水。输入保证有解。输入格式输入包含多行每行三个正整数CaC_aCa​、CbC_bCb​、NNN以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个测试用例输出一系列操作每行一个最后一行是success。样例输入3 5 4 5 7 3输出fill B pour B A empty A pour B A success fill B pour B A empty A pour B A success题目分析本题的核心是使用BFS\texttt{BFS}BFS或经典数学方法求解。由于CaC_aCa​和CbC_bCb​互质可以通过不断将AAA壶的水倒入BBB壶来得到所有余数。算法循环执行以下步骤直到BBB壶中有NNN加仑若BBB已满清空BBB。若AAA为空装满AAA。将AAA倒入BBB。输出相应操作。正确性由于CaC_aCa​和CbC_bCb​互质通过重复将AAA倒入BBB可以生成所有模CbC_bCb​的余数。复杂度分析每个操作O(1)O(1)O(1)最多O(Cb)O(C_b)O(Cb​)步。代码实现// Jugs// UVa ID: 571// Verdict: Accepted// Submission Date: 2016-09-02// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intCa,Cb,N;while(cinCaCbN){intA0,B0;while(true){if(BCb){coutempty B\n;B0;}if(A0){coutfill A\n;ACa;}if(AN){coutsuccess\n;break;}coutpour A B\n;BA;if(BCb){AB-Cb;BCb;}elseA0;if(AN||BN){coutsuccess\n;break;}}}return0;}