[HackerRank]瑪拉薩和石頭(Manasa and Stones)

題目描述

瑪拉薩正在跟朋友們遠足。她找到一連串有著編號的石頭遞增排序著，並且注意到兩個相鄰的石頭的號碼的差異只會是a或是b。傳說中有個寶藏就在這串石頭的尾端，如果瑪拉薩可以猜得到尾端這顆石頭的編號，那麼她將可以得到這個寶藏。給定第一顆石頭的數字為0，尋找尾端的石頭所有可能的編號。

原題網址

輸入格式

第一行包含一個整數T，表示測試資料的數量，範圍在1到10之間(包含1和10)。

接下來的3T行，每三行為一組測試資料。第一行為n的數值，表示石頭的數量。第二行為a的數值，第三行為b的數值。範圍都在1到10³之間(包含1和10³)。

輸出格式

分行輸出每組測試資料計算所有可能的尾端石頭編號的結果，用空格分隔不同的編號。

範例輸入

範例輸出

額外解釋

第一組測試資料中，石頭可能的編號為：

所以答案是「2 3 4」。

第二組測試資料中，石頭可能的編號為：

所以答案是「30 120 210 300」。

解題概念

排序a、b的大小，若a小於b，則編號若每次遞增a的話，最後的石頭的編號之大小為所有可能的最小值；同樣地，編號若每次遞增b的話，最後的石頭的編號之大小為所有可能的最大值。

在編號遞增的時候，若不是每次遞增a，而是在其中一次遞增了b的話，那麼最後的結果就會是最小值再加上b-a。舉例來說，若有五顆石頭，要所以要從0開使遞增四次：

若是其中有兩次遞增b的話，算法變成：

所以，在最小值和最大值的編號範圍中，尾端石頭所有可能的編號為「最小值+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();
        }
    }
}