Uva 10603 Fill 倒水问题
题目描述
有三个容量分别为a,b,c升的容器(a,b,c都是正整数,且都不超过200),刚开始的时候第一个和第二个杯子都是空的,只有第三个杯子装满了c升水。允许从一个容器把水倒入另一个容器中,直到一个容器空了或者是另一个容器满了,允许无限次的进行这样的倒水操作。
你的任务是编写一个程序来计算出最少需要倒多少升水才能让其中某一个杯子中的水有d升(d是不超过200的正整数)?如果无法做到恰好是d升,就让某一个杯子里的水是d‘升,其中d'<d并且尽量接近d。如果能够找到这样的d',你还是需要计算出其中某一个杯子达到d'升时,最少需要倒多少升水。
输入输出格式
输入格式:
输入的第一行是一个整数T,表示测试数据组数。
接下来T行,每行4个用空格隔开的整数分别表示a,b,c,d。
输出格式:
对于每组测试数据,输出一行,包含两个整数,第一个整数表示最少的倒水总量,第二个整数表示目标倒水量(d或者d')。
输入输出样例
输入样例#1:
2
2 3 4 2
96 97 199 62
输出样例#1:
2 2
9859 62
限制
每组测试样例时空限制3s/262144KiB(256MiB)