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

題目描述

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

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

每個位數只能是3或5。
整個數字中,「3」的數量必須要可以整除以5。
整個數字中,「5」的數量必須要可以整除以3。

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

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

原題網址

https://www.hackerrank.com/challenges/sherlock-and-the-beast

輸入格式

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

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

輸出格式

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

範例輸入

4
1
3
5
11

範例輸出

-1
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。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章