首页 > 专题系列 > Java解POJ > POJ 3475 Paper-, er, Transcript-Folding Game [解题报告] Java
2013
11-12

POJ 3475 Paper-, er, Transcript-Folding Game [解题报告] Java

Paper-, er, Transcript-Folding Game

问题描述 :

Most recently, frkstyc has engaged himself busily in applying for admission to graduate schools abroad. Among all those tasks he has to complete, one is to prepare the transcripts to mail to the admission offices. Earlier, frkstyc ordered his transcripts from the university’s Educational Admnistration Division (EAD). As per the regulations of the EAD, upon claiming the transcripts in the EAD office, he had to fold the transcripts until they fit into the envelops provided by the EAD, which were later sealed and stamped at the scene. Having unwisely overestimated the actual number of transcripts required, he ordered twice as many transcripts as needed, which left him with a very uninteresting and fatiguing paper-folding game. Finishing the work, he swore to himself that never again would he trouble himself with applications for admission aboard.

To help you better understand frkstyc’s experience folding his transcripts, consider this problem: given the dimensions of an envelop and a transcript, how many times does the transcript have to be folded until its dimensions do not exceed those of the envelop? Remember that frkstyc was preparing the transcripts for the review of faculty members in admission commitees, which required him to fold the transcripts either horizontally or vertically each time, halving its size. Additionally, the transcript must not lie slanted in the envelop.

输入:

The input contains multiple test cases each occupying one line. Each test case consists of four integers a, b, c, d (0 < a, b, c, d ≤ 231 − 1) indicating that the dimension of an envelop is a × b and that of a transcript is c × d. Process until EOF is met.

输出:

For each test case, output the minimum number of times a transcript has to be folded.

样例输入:

1 2 1 4
2 1 1 4

样例输出:

1
1

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
	while(sc.hasNext())
	{
	    long a = sc.nextLong();
	    long b = sc.nextLong();
	    double c = sc.nextDouble();
	    double d = sc.nextDouble();
	    int steps = 0;
	    if(a > b)
	    {
	        long temp = a;
		a = b;
		b = temp;
	    }
	    while(true)
	    {
	        if(c > d)
		{
		    double temp = c;
		    c = d;
		    d = temp;
		}

		if(a >= c && b >=d)
		{
		    break;
		}else if(b < d)
		{
		    d = d/2;
		    steps++;
		}else
		{
		    c = c/2;
		    steps++;
		}
	    }
	    System.out.println(steps);
	}
    }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。