九度-1336-液晶屏裁剪 | Acm之家
Read full article from 九度-1336-液晶屏裁剪 | Acm之家
- 苏州某液晶厂一直生产a * b大小规格的液晶屏幕,由于该厂的加工工艺限制,液晶屏的边长都为整数。最近由于市场需求发生变化,x : y比例的显示器比较流行,该厂为了适应市场需求,需要改造原生产线,并将库存的a * b大小的液晶屏进行裁剪,使之适应市场的需求。该厂同时希望,将a * b大小的液晶屏裁剪之后,不仅符合x : y的比例要求,同时在转换为新比例液晶屏的过程中,保证因切割而丢弃的液晶边角料最少。你的任务就是根据原液晶屏大小和新的屏幕的比例,判断是否能将库存的液晶屏转换为符合要求的液晶屏大小,并求出新的液晶屏的大小a' b';若不能加工成新的,则输出0 0。注:新的液晶屏边长和旧的液晶屏边长都为整数,并且长和宽不能交换。
- 输入:
- 测试数据包括多个,每个测试数据一行。每行四个整数 a b x y1) a、b表示原库存液晶屏的长和宽2) x、y表示新的液晶屏的长宽比例x : y其中,1 <= a, b, x, y <= 10^9。
- 输出:
- 对应每个测试案例,输出一行,每行包含两个整数,由空格隔开:1) 若答案存在,则输出新的液晶屏的长宽 a' b'2) 若不存在,则输出0 0
02 | int com_div( int a, int b) //辗转相除法 |
03 | { |
04 | int r; |
05 | while (b!=0) |
06 | { |
07 | r=a%b; |
08 | a=b; |
09 | b=r; |
10 | } |
11 | return a; |
12 | } |
13 | int main() |
14 | { |
15 | int a,b,x,y,a1,b1,t,i; |
16 | while ( scanf ( "%d%d%d%d" ,&a,&b,&x,&y)!=EOF) |
17 | { |
18 | t=com_div(x,y); |
19 | x=x/t; |
20 | y=y/t; |
21 | if (a<x||b<y) |
22 | { |
23 | printf ( "0 0\n" ); |
24 | continue ; |
25 | } |
26 | if (x>y) |
27 | { |
28 | for (a1=a/x*x;a1/x*y>b;a1-=x); |
29 | b1=a1/x*y; |
30 | } |
31 | else |
32 | { |
33 | for (b1=b/y*y;b1/y*x>a;b1-=y); |
34 | a1=b1/y*x; |
35 | } |
36 | printf ( "%d %d\n" ,a1,b1); |
37 | } |
38 | return 0; |
39 | } |