P1432 倒水问题

    • 185通过
    • 570提交
  • 题目提供者 icy
  • 评测方式 云端评测
  • 标签 搜索 O2优化 Special Judge 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

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

    题目描述

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

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

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

    问题由3个参数: $C_a$ , $C_b$ 和 $N$ ,分别表示水壶 $A$ 和 $B$ 的容量,目标水量 $N$ 。解决问题的目标是,给出一系列倒水的步骤,使水壶 $B$ 中的水量恰好是 $N$ 。

    输入输出格式

    输入格式:

    第一行为数据组数 $T$ 。

    接下来的 $T$ 行,每行三个数字 $C_a$ , $C_b$ 和 $N$ ,意义如题目所示。

    $T$ 不超过 $30$ 组, $0<C_a≤Cb$ , $N≤C_b≤1000$ ,且 $C_a$ 和 $C_b$ 互质。

    输出格式:

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

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

    • 1操作: $fill A$ 意为给 $A$ 灌满水
    • 2操作: $fill B$
    • 3操作: $empty A$ 意为将 $A$ 中水倒空
    • 4操作: $empty B$
    • 5操作: $pour B A$ 意为将 $B$ 中水倒到 $A$ 中(直到 $A$ 满或者 $B$ 中水没有剩余)
    • 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,此时请联系管理员修改数据。

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。