[Java] UVa 10013 Super long sums

題目連結

題意:
計算兩數之和，每組測資一行相隔
先給定兩數之位數 M (同位)
接著每行依序從最高位給兩數的值

題目有說可以是不同位的數
M 會是高位的位數
較低位者的高位會補 0

例如: 931 + 85
3
9 0
3 8
1 5

其中 M 的大小可能達1000000 (100萬位)

解法:
由於M ≤ 1000000
不能當成2個數字直接相加
就算用 BigInteger 也可能無法計算這麼多位的加法
只能建立陣列，計算每個位數的值

先將位數的值個別相加
再處理進位問題，從個位推到最高位

以931+85為例，以陣列大小比題目的位數多 1 做預留
(任兩個 N 位的數相加不會超過 N+1 位)

第一步，各位數相加後，分別存 9 11 6
從個位數開始，十位超過 10，進一位
百位也是相同做法

最後從陣列頭輸出到陣列尾即可

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int N = Integer.parseInt(sc.nextLine());
	boolean first = true;
	while(N-- > 0) {
	if (!first)
	System.out.println();
	sc.nextLine();
	int M = Integer.parseInt(sc.nextLine());
	int ans[] = new int [M+1];
	for (int i = 1; i <= M; i++) {
	StringTokenizer st = new StringTokenizer(sc.nextLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
	ans[i] = a + b;
	}
	for (int i = M; i >= 1; i--) {
	ans[i-1] += ans[i]/10;
	ans[i] %= 10;
	}
	StringBuilder sb = new StringBuilder();
	if (ans[0] != 0)
	sb.append(ans[0]);
	for (int i = 1; i <= M; i++)
	sb.append(ans[i]);
	System.out.println(sb.toString());
	first = false;
	}
	}
	}

view raw UVa10013.java hosted with ❤ by GitHub