UVa 571 Jugs （想法题）

UVa 571 Jugs （想法题）2014-07-25

571 - Jugs

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=512

思路：

由于是special judge，所以构造出一个可行解就可以。

论断：如果A是空的就加水，不空就向B倒，B满了之后就empty掉，这样在B中一定可以形成0~B的任意一个解。

证明：按这样去倒水的话，我们可以用（k*A）%B表示B中的水量，由于A与B互质，所以lcm（A,B）=AB，那么A积累B次才能回到起点，所以最小周期是B。并且，在一个周期内，我们可以用反证法证明所有的值均是不同的（只要证明后一个值与前一个不用即可），因此这样我们就一定可以得到一个满足要求的操作序列。

完整代码：

/*0.029s*/#include <cstdio>int main（）{int na, nb, N, ca, cb;while （~scanf（"%d %d %d", &ca, &cb, &N））{na = 0, nb = 0;while （nb ！= N）{if （na == 0）{puts（"fill A"）;na = ca;}if （nb == cb）{puts（"empty B"）;nb = 0;}nb += na;puts（"pour A B"）;if （nb > cb） na = nb - cb, nb = cb;else na = 0;}puts（"success"）;}return 0;}

作者：csdn博客 synapse7