題目描述
瑪拉薩正在跟朋友們遠足。她找到一連串有著編號的石頭遞增排序著,並且注意到兩個相鄰的石頭的號碼的差異只會是a或是b。傳說中有個寶藏就在這串石頭的尾端,如果瑪拉薩可以猜得到尾端這顆石頭的編號,那麼她將可以得到這個寶藏。給定第一顆石頭的數字為0,尋找尾端的石頭所有可能的編號。
原題網址
輸入格式
第一行包含一個整數T,表示測試資料的數量,範圍在1到10之間(包含1和10)。
接下來的3T行,每三行為一組測試資料。第一行為n的數值,表示石頭的數量。第二行為a的數值,第三行為b的數值。範圍都在1到103之間(包含1和103)。
輸出格式
分行輸出每組測試資料計算所有可能的尾端石頭編號的結果,用空格分隔不同的編號。
範例輸入
2
3
1
2
4
10
100
3
1
2
4
10
100
範例輸出
2 3 4
30 120 210 300
30 120 210 300
額外解釋
第一組測試資料中,石頭可能的編號為:
0,1,2
0,1,3
0,2,3
0,2,4
0,1,3
0,2,3
0,2,4
所以答案是「2 3 4」。
第二組測試資料中,石頭可能的編號為:
0, 10, 20, 30
0, 10, 20, 120
0, 10, 110, 120
0, 10, 110, 210
0, 100, 110, 120
0, 100, 110, 210
0, 100, 200, 210
0, 100, 200, 300
0, 10, 20, 120
0, 10, 110, 120
0, 10, 110, 210
0, 100, 110, 120
0, 100, 110, 210
0, 100, 200, 210
0, 100, 200, 300
所以答案是「30 120 210 300」。
解題概念
排序a、b的大小,若a小於b,則編號若每次遞增a的話,最後的石頭的編號之大小為所有可能的最小值;同樣地,編號若每次遞增b的話,最後的石頭的編號之大小為所有可能的最大值。
在編號遞增的時候,若不是每次遞增a,而是在其中一次遞增了b的話,那麼最後的結果就會是最小值再加上b-a。舉例來說,若有五顆石頭,要所以要從0開使遞增四次:
a + b + a + a = a + a + a + b = (a + a + a + a) + (b - a)
若是其中有兩次遞增b的話,算法變成:
a + b + b + a = a + a + b + b = (a + a + a + a) + (b - a) + (b - a)
所以,在最小值和最大值的編號範圍中,尾端石頭所有可能的編號為「最小值+k*(b - a)」,其中的k為大於等於0且小於n的整數,表示遞增時有幾次是遞增了b。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);
int testCase = sc.nextInt();
while (testCase-- > 0) {
final int n_dec = sc.nextInt() - 1;
final int a = sc.nextInt();
final int b = sc.nextInt();
if (a == b) {
System.out.print(b * (n_dec));
} else {
final int min;
final int max;
final int d;
if (a > b) {
max = a * n_dec;
min = b * n_dec;
d = a - b;
} else {
max = b * n_dec;
min = a * n_dec;
d = b - a;
}
for (int i = min; i < max; i += d) {
System.out.print(i + " ");
}
System.out.print(max);
}
System.out.println();
}
}
}