[HackerRank]福爾摩斯和超級電腦「野獸」(Sherlock and The Beast)

題目描述

夏洛克·福爾摩斯懷疑他的死對頭─詹姆斯·莫里亞蒂教授又再進行邪惡計劃。華生覺得莫里亞蒂和英國秘密情報局的超級電腦「野獸」最近發生的問題有關。

在短暫的調查後，福爾摩斯找到了莫里亞蒂的筆記，上頭寫著有關於超級電腦「野獸」感染病毒的事情。然而，他也發現了其中隱藏的重要線索，那就是一個數字N。福爾摩斯知道移除病毒的關鍵代碼，就是找出另一組長度為N並且符合以下規則的數字，這些數字的規則如下：

符合的數字可能會有很多組，數值最大的那個便是正確的關鍵代碼。

莫里亞蒂的病毒將會在很快的時間內開始運作。您的任務就是在超級電腦「野獸」被毀掉之前，幫助福爾摩斯找到這個關鍵代碼！

原題網址

輸入格式

第一行輸入測試資料的數量T，範圍在1到20之間(包含1和20)。

接下來的T行為每組測試資料的數字N。N的範圍在1到100000之間(包含1和100000)。

輸出格式

輸出符合的關鍵代碼，應該要有N位數。如果找不到符合的關鍵代碼，輸出「-1」。

範例輸入

範例輸出

額外解釋

數字N為1時，符合條件的關鍵代碼並不存在。

數字N為3時，555是唯一符合的數字，「5」的數量可以被3整除。

數字為5時，只有33333是唯一符合的數字，「3」的數量可以被5整除。

數字為11時，55555533333是符合條件的關鍵代碼，「5」有6個，可以被3整除，「3」有5個，可以被5整除。

解題概念

由於這邊要找出最大的數，因此可以先從擁有最多個「5」的數字開始嘗試組合。「5」的數量為3的整數倍數，因此可以先將N除以3取整數部份，再乘以3便是「5」可能的最大數量，接著再判斷「3」的數量(N減掉這個「5」的數量後)是否可以整除5。如果可以，表示已經找到了關鍵代碼；如果不行，要將「5」的數量減3，並繼續檢查「3」的數量是否可以整除5。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        TestCase:
        while (testCase-- > 0) {
            final int n = sc.nextInt();

            int a = n / 3 * 3;
            while (true) {
                final int b = n - a;
                if (b % 5 == 0) {
                    final StringBuilder sb = new StringBuilder();
                    for (int x = 0; x < a; ++x) {
                        sb.append("5");
                    }
                    for (int x = 0; x < b; ++x) {
                        sb.append("3");
                    }
                    System.out.println(sb.toString());
                    continue TestCase;
                }
                a -= 3;
                if (a == -3) {
                    break;
                } else if (a < 0) {
                    a = 0;
                }
            }
            System.out.println(-1);
        }
    }
}