#P1432. 倒水问题

倒水问题

题目背景

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

题目描述

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

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

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

问题由3个参数:CaC_aCbC_bNN,分别表示水壶AABB的容量,目标水量NN。解决问题的目标是,给出一系列倒水的步骤,使水壶BB中的水量恰好是NN

输入格式

第一行为数据组数TT

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

TT不超过3030组,0<CaCb0<C_a≤CbNCb1000N≤C_b≤1000,且CaC_aCbC_b互质。

输出格式

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

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

  • 1操作:fillAfill A 意为给AA灌满水
  • 2操作:fillBfill B
  • 3操作:emptyAempty A 意为将AA中水倒空
  • 4操作:emptyBempty B
  • 5操作:pourBApour B A 意为将BB中水倒到AA中(直到AA满或者BB中水没有剩余)
  • 6操作:pourABpour A B
2
3 5 4 
5 7 3 
6 2 5 3 5 2 5 
6 1 6 1 6 4 6 
1
26 29 11
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,此时请联系管理员修改数据。

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