首页 > ACM题库 > 九度OJ > 九度-1336-液晶屏裁剪
2014
02-02

九度-1336-液晶屏裁剪

题目来自九度OJ之我与名企有个约会趣味编程系列赛(1)-

题目描述:
苏州某液晶厂一直生产a * b大小规格的液晶屏幕,由于该厂的加工工艺限制,液晶屏的边长都为整数。最近由于市场需求发生变化,x : y比例的显示器比较流行,该厂为了适应市场需求,需要改造原生产线,并将库存的a * b大小的液晶屏进行裁剪,使之适应市场的需求。该厂同时希望,将a * b大小的液晶屏裁剪之后,不仅符合x : y的比例要求,同时在转换为新比例液晶屏的过程中,保证因切割而丢弃的液晶边角料最少。
你的任务就是根据原液晶屏大小和新的屏幕的比例,判断是否能将库存的液晶屏转换为符合要求的液晶屏大小,并求出新的液晶屏的大小a’ b’;若不能加工成新的,则输出0 0。
注:新的液晶屏边长和旧的液晶屏边长都为整数,并且长和宽不能交换。
输入:
测试数据包括多个,每个测试数据一行。
每行四个整数 a b x y
1) a、b表示原库存液晶屏的长和宽
2) x、y表示新的液晶屏的长宽比例x : y
其中,1 <= a, b, x, y <= 10^9。
输出:
对应每个测试案例,输出一行,每行包含两个整数,由空格隔开:
1)       若答案存在,则输出新的液晶屏的长宽 a’ b’
2)       若不存在,则输出0 0
样例输入:
1920 1600 16 9
800 600 4 3
800 600 3 4
1 1 1 2
样例输出:
1920 1080
800 600
450 600
0 0

简单的计算,没有太大的难度。

#include<stdio.h>
int com_div(int a,int b)//辗转相除法
{
        int r;
        while(b!=0)
        {
                r=a%b;
                a=b;
                b=r;
        }
        return a;
}
int main()
{
        int a,b,x,y,a1,b1,t,i;
        while(scanf("%d%d%d%d",&a,&b,&x,&y)!=EOF)
        {
                t=com_div(x,y);
                x=x/t;
                y=y/t;
                if(a<x||b<y)
                {
                        printf("0 0\n");
                        continue;
                }
                if(x>y)
                {
                        for(a1=a/x*x;a1/x*y>b;a1-=x);
                        b1=a1/x*y;
                }
                else
                {
                        for(b1=b/y*y;b1/y*x>a;b1-=y);
                        a1=b1/y*x;
                }
                printf("%d %d\n",a1,b1);
        }
        return 0;
}

 

 


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  3. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count