倒酒

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 pour.in 输出文件 pour.out

【问题描述】

Winy是一家酒吧的老板,他的酒吧提供两种体积的啤酒,a mlb ml,分别使用容积为a mlb ml的酒杯来装载。

    酒吧的生意并不好。Winy发现酒鬼们都非常穷。有时,他们会因为负担不起aml或者bml啤酒的消费,而不得不离去。因此,Winy决定出售第三种体积的啤酒(较小体积的啤酒)

  Winy只有两种杯子,容积分别为a mlb ml,而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。

    为了简化倒酒的步骤,Winy规定:

    (1ab

    (2)酒桶容积无限大,酒桶中酒的体积也是无限大(但远小于桶的容积)

    (3)只包含三种可能的倒酒操作:

     ①将酒桶中的酒倒入容积为b ml的酒杯中;

     ②将容积为a ml的酒杯中的酒倒入酒桶;

     ③将容积为b ml的酒杯中的酒倒入容积为a ml的酒杯中。

4)每次倒酒必须把杯子倒满或把被倾倒的杯子倒空。

Winy希望通过若干次倾倒得到容积为a ml酒杯中剩下的酒的体积尽可能小,他请求你帮助他设计倾倒的方案

【输入】

两个整数ab0<ba109

【输出】

第一行一个整数c,表示可以得到的酒的最小体积。

第二行两个整数PaPb(中间用一个空格分隔),分别表示从体积为a ml的酒杯中倒出酒的次数和将酒倒入体积为b ml的酒杯中的次数。

若有多种可能的PaPb满足要求,那么请输出Pa最小的一个。若在Pa最小的情况下,有多个Pb满足要求,请输出Pb最小的一个。

【样例】

pour.in

5 3

pour.out

1

1 2

倾倒的方案为:

1、桶->B杯; 2B->A杯;

3、桶->B杯; 4B->A杯;

5A->; 6B->A杯;