[Java] UVa 10025 The ? 1 ? 2 ? ... ? n = k problem

題目連結

題意:
給定一個式子

? 1 ? 2 ? ... ? n = k, 其中 ? 可以為 + 或 -
題目給 k 值，要求輸出最小的 n 使得式子成立

舉例:

k = 0， 存在最小的 n = 3 使得 1+2-3 = 0
k =12，存在 n = 7 使得 -1+2+3+4+5+6-7 = 12

解法:
觀察式子，可以知道式子是從 1 ~ n 的運算
例如: 假設 n 為 3，式子的最大發生在運算子都是 + (最小則為 - )
即 +1+2+3 = 6 (最小為 -1-2-3 = -6)

再觀察發現，改變任何運算子後的結果都跟原來的差為偶數
綜觀來看，n = 3時會有以下運算結果

＋１＋２＋３＝６
－１＋２＋３＝４
＋１－２＋３＝２
－１－２＋３＝０
－１＋２－３＝－２
＋１－２－３＝－４
－１－２－３＝－６

因此，我們可以先求得最大值，判斷 k跟它是不是差偶數倍
以上面的例子，假設 k 為 0 ，可以得到(6 - 0) %2 = 0
意思是可以從 +1+2+3的式子透過改變運算元得到 k 的結果，則答案 n 可以為 3

因為題目要求符合答案最小的 n
解題思路為
如果存在 1+2+3+...+n = k，該 n 必為最小
否則 k 就是 將式子結果 扣掉偶數 得到

因此

題目給定 k，透過上圖公式得到最小候選 n (真正的 n 會大於等於該數)
並計算該 n 下的式子結果最大值(即 1+2+...+n)
再判斷該值與 k 值的差是否為偶數(前提是比k大，才能改運算元去得到k)
若否，增加 n 的值並重複判斷

舉例來說
k =12，最後答案 n = 7

先以上圖公式得到n = 4 (4.xxx取整數)
4*5/2 = 10，比 k=12 小

n = 5，5*6/2 = 15，15與k=12的差不為偶數
n = 6，6*7/2 = 21，理由同上
n = 7，7*8/2 = 28，符合結果，答案為 7

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]){
	Scanner sc = new Scanner(System.in);
	int T = Math.abs(Integer.valueOf(sc.nextLine()));
	for (int i = 0; i < T; i++) {
	sc.nextLine();
	int k = Math.abs(Integer.valueOf(sc.nextLine()));
	int n = (-1 + (int)Math.sqrt(1 + 8*k))/2;
	int sum = (n + 1) * n / 2;
	while (sum < k || (sum - k) % 2 != 0) {
	n++;
	sum += n;
	}
	if (i != 0)
	System.out.println();
	if (k == 0)
	System.out.println("3");
	else
	System.out.println(n);
	}
	}
	}

view raw UVa10025.java hosted with ❤ by GitHub