题目描述
题目要求解决水壶问题。给定两个容量分别为CaC_aCa和CbC_bCb的水壶（Ca≤CbC_a \le C_bCa≤Cb），以及目标水量NNN（N≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intCa,Cb,N;while(cin>>Ca>>Cb>>N){intA=0,B=0;while(true){if(B==Cb){cout<<"empty B\n";B=0;}if(A==0){cout<<"fill A\n";A=Ca;}if(A==N){cout<<"success\n";break;}cout<<"pour A B\n";B+=A;if(B>Cb){A=B-Cb;B=Cb;}elseA=0;if(A==N||B==N){cout<<"success\n";break;}}}return0;}