纯净水

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

        鱼儿子只喜欢喝纯净水,但是鱼头觉得这样对健康不好,他想让鱼儿子改喝矿泉水,鱼儿子不想喝矿泉水。于是鱼头对鱼儿子说:我们来做一个游戏,如果你赢了,就让你喝纯净水。
        这个游戏当然和纯净水有关,鱼头会给鱼儿子两个杯子,容量分别为a毫升和b毫升(1<=a,b<=500),鱼儿子可以进行如下三种操作:
                1. FILL(i):将第i个杯子装满
                2. DROP(i):将第i个杯子倒空
                3. POUR(i,j):将第i个杯子中的水倒进第j个杯子。如果第i个杯子中的水较少(少于第j个杯子的剩余空间),则第i个杯子被倒空;否则第j个杯子被倒满,第i个杯子中剩余的水继续留在杯中。
        鱼头给鱼儿子一个整数X,要求鱼儿子在X个操作内用两个杯子取到c(c>=0)毫升水(这些水必须装在一个杯子里),如果鱼儿子能取回,则鱼儿子赢了。当然,鱼头必须保证在X步内能完成任务,现在鱼头想让他的新队员帮助他编一个程序计算出最小的X(两个杯子最开始是空的,鱼头提供足够的纯净水给鱼儿子玩,并且鱼儿子在玩水的过程中不会把水洒出来)。

Input

有多组输入数据,以文件尾结束,每组数据仅一行:三个整数a,b,c,意义如上。

Output

对于每组输入,输出最小的X,如果该组测试数据无解,输出‘impossible’。

Sample Input

300 500 400
5 3 2
3 5 8
50 48 49

Sample Output

6
2
impossible
impossible

Hint

对于第一组数据,最快的方法为:FILL(2),POUR(2,1),DROP(1),POUR(2,1),FILL(2),POUR(2,1),至少需要6步。对于第二组数据,最快的方法为FILL(1),POUR(1,2) ,至少需要2步。第三组显然要求的水量比杯子的容量大,不能满足。第四组,显然两个偶数容量的杯子不能取到奇数容量的水。

Source

watermelom::zyz

提交代码