264 - Count on Cantor - One Star - CPE - 解題筆記 | Hsing Yu = = We are the dreamers. We make it happen 'cause we can see it.

🌕🌑🌑🌑🌑

# 題目連結

題目連結
Online Judge
uDebug

# 題目說明

Time limit: 3.000 seconds

# 題目

One of the famous proofs of modern mathematics is Georg Cantor’s demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below.

Imgur

In the above diagram, the first term is 1/1 , the second term is 1/2 , the third term is 2/1 , the fourth term is 3/1 , the fifth term is 2/2 , and so on.

# Input and Output

You are to write a program that will read a list of numbers in the range from 1 to 107 and will print for each number the corresponding term in Cantor’s enumeration as given below. No blank line should appear after the last number.

The input list contains a single number per line and will be terminated by end-of-file.

# Sample Input

3
14
7

# Sample Output

TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4

# 解題技巧

sqrt(10^7 * 2) < 4500
利用陣列計算當行最大的 num 會是多少
分子分母可以分開用兩個 int 儲存計算

# Solution

Main.java

	import java.util.*;

	public class Main{
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);

	int max[] = new int[4500]; // sqrt(10^7 * 2) < 4500
	max[1] = 1;
	for(int i = 2; i < 4500; i++){
	max[i] = max[i - 1] + i;
	}

	while(sc.hasNextInt()){
	int num = sc.nextInt();
	int line = 0;

	int up = 0, down = 0;

	for(int i = 1; i < 4500; i++){
	if(num <= max[i]){
	line = i;
	break;
	}
	}

	for(int i = 1; i <= num - max[line - 1]; i++){
	if(line % 2 == 0){
	up = i;
	down = line + 1 - i;
	}else{
	down = i;
	up = line + 1 - i;
	}
	}

	System.out.println("TERM " + num + " IS " + up + "/" + down);
	}
	}
	}

單字

** **
!! !!

片語 & 搭配詞

!! !!

Math