2013
11-11

# Copier Reduction

What do you do if you need to copy a 560x400mm image onto a standard sheet of US letter-size paper (which is about 216x280mm), while keeping the image as large as possible? You can rotate the image 90 degrees (so that it is in “landscape” mode), then reduce it to 50% of its original size so that it is 200x280mm. Then it will fit on the paper without overlapping any edges. Your job is to solve this problem in general.

The input consists of one or more test cases, each of which is a single line containing four positive integers A, B, C, and D, separated by a space, representing an AxBmm image and a CxDmm piece of paper. All inputs will be less than one thousand. Following the test cases is a line containing four zeros that signals the end of the input.

For each test case, if the image fits on the sheet of paper without changing its size (but rotating it if necessary), then the output is 100%. If the image must be reduced in order to fit, the output is the largest integer percentage of its original size that will fit (rotating it if necessary). Output the percentage exactly as shown in the examples below. You can assume that no image will need to be reduced to less than 1% of its original size, so the answer will always be an integer percentage between 1% and 100%, inclusive.

560 400 218 280
10 25 88 10
8 13 5 1
9 13 10 6
199 333 40 2
75 90 218 280
999 99 1 10
0 0 0 0


50%
100%
12%
66%
1%
100%
1%


//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
public static void main(String[] args){
int a,b,c,d;
int z,nz;
while (true){
a=scanner.nextInt();
b=scanner.nextInt();
c=scanner.nextInt();
d=scanner.nextInt();
if (a+b+c+d==0){
break;
}
if (a*d>b*c){
z=getN(a,c);
}
else{
z=getN(b,d);
}
if (a*c>b*d){
nz=getN(a,d);
}
else{
nz=getN(b,c);
}
if (z< nz){
if (nz>100){
nz=100;
}
System.out.println(nz+"%");
}
else{
if (z>100){
z=100;
}
System.out.println(z+"%");
}
}
}

public static int getN(int a,int c){
return 100*c/a;
}
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。