題目描述
夏洛克·福爾摩斯懷疑他的死對頭─詹姆斯·莫里亞蒂教授又再進行邪惡計劃。華生覺得莫里亞蒂和英國秘密情報局的超級電腦「野獸」最近發生的問題有關。
在短暫的調查後,福爾摩斯找到了莫里亞蒂的筆記,上頭寫著有關於超級電腦「野獸」感染病毒的事情。然而,他也發現了其中隱藏的重要線索,那就是一個數字N。福爾摩斯知道移除病毒的關鍵代碼,就是找出另一組長度為N並且符合以下規則的數字,這些數字的規則如下:
每個位數只能是3或5。
整個數字中,「3」的數量必須要可以整除以5。
整個數字中,「5」的數量必須要可以整除以3。
整個數字中,「3」的數量必須要可以整除以5。
整個數字中,「5」的數量必須要可以整除以3。
符合的數字可能會有很多組,數值最大的那個便是正確的關鍵代碼。
莫里亞蒂的病毒將會在很快的時間內開始運作。您的任務就是在超級電腦「野獸」被毀掉之前,幫助福爾摩斯找到這個關鍵代碼!
原題網址
輸入格式
第一行輸入測試資料的數量T,範圍在1到20之間(包含1和20)。
接下來的T行為每組測試資料的數字N。N的範圍在1到100000之間(包含1和100000)。
輸出格式
輸出符合的關鍵代碼,應該要有N位數。如果找不到符合的關鍵代碼,輸出「-1」。
範例輸入
4
1
3
5
11
1
3
5
11
範例輸出
-1
555
33333
55555533333
555
33333
55555533333
額外解釋
數字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);
}
}
}