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


題目描述

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

原題網址

https://www.hackerrank.com/challenges/manasa-and-stones

輸入格式

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

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

輸出格式

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

範例輸入

2
3
1
2
4
10
100

範例輸出

2 3 4
30 120 210 300

額外解釋

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

0,1,2
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

所以答案是「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。

參考答案

關於作者

Magic Len

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

相關文章