logo AlgoBeat OnlineJudge
登录 注册

#200424. 倒水问题

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

输入输出已更改,请不要直接提交原先的代码。


假定两个水壶 ,供水量不限。可以使用三种方法装水:

  • 给一个水壶装水;
  • 把一个水壶倒空;
  • 从一个水壶倒进另一个水壶。

当从一个水壶倒进另一个水壶时,如果第一个水壶倒空,或者第二个水壶装满就不能再倒了。例如,一个水壶 加仑和另一个水壶 加仑,水量是 加仑,则从水壶 倒进水壶 时,让水壶 充满水而水壶 加仑水。

问题有 个参数:,分别表示水壶 的容量,目标水量 。问题的目标是,给出一系列倒水的步骤,使水壶 中的水量恰好是

如果有多种操作方案,请给出操作次数最少的任意一种方案。

输入格式

第一行为数据组数

接下来的 行,每行三个数字 ,意义如题目所示。

不超过 ,且 互质。

输出格式

输出共为 行,第一个数字为要达成的完成次数 (题目保证存在解)。

接下来 个数字,表示各种操作:

  • 1 操作:fill A 意为给 灌满水
  • 2 操作:fill B
  • 3 操作:empty A 意为将 中水倒空
  • 4 操作:empty B
  • 5 操作:pour B A 意为将 中水倒到 中(直到 满或者 中水没有剩余)
  • 6 操作:pour A B

样例

样例输入 1

2
3 5 4 
5 7 3 

样例输出 1

6 2 5 3 5 2 5 
6 1 6 1 6 4 6 

样例输入 2

1
26 29 11

样例输出 2

22 1 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 

数据范围与提示

开启了 spj。

如果你的方案比答案优,会提示 UKE,此时请联系管理员修改数据。

如果你的方案比答案差,分数会相应减损。