UVa 571 Jugs

题目描述

题目要求解决水壶问题。给定两个容量分别为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加仑：
  1. 若BBB已满，清空BBB。
  2. 若AAA为空，装满AAA。
  3. 将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;}