回分類題庫
g042: D.沙之國
關鍵字: NPSC 2008 國中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 157 Times / 156 Users | Submit : 202 Times / 159 Users | Accepted rate : 98%
題目加入時間 : 2011-12-21 14:55

Content: 简体中文

從前有個叫做「阿拉巴斯坦」的沙漠王國,住著一群和沙漠對抗、樂天知命的人。在沙漠生存,水源是非常稀有和珍貴的,即使是一滴也不能浪費。為了讓人民能夠節約和好好地衡量自己的取水量,在這個國家所有的水井旁邊都放了1公升、3 公升、9 公升、27 公升的四種公用水桶,可以讓人民自行取用。然而在水井打水有個奇特的規定:一定要把公用水桶裝滿才能帶走。

例如,住在猷巴村愛喝水的魯夫大叔家裡有個 25 公升的大木桶,每天他都會把這25 公升的大木桶裝滿並且喝個精光。為了恰好裝滿25 公升的大水桶而不浪費,每天早上,他先用3 公升的水桶打7 趟水、再用1 公升的水桶打4 趟水,來來回回跑個11 趟,就可以恰好裝滿他家的大水桶而不浪費。

聰明的你應該已經發現,其實他也可以用 9 公升的水桶打2 趟水,再用3公升的水桶打1 趟水、最後再用1 公升的水桶打1 趟水,這樣他就只需要跑4趟到井邊裝水。

為了讓魯夫大叔能夠節省打水的時間,給定任何大水桶的容量P (公升),你能不能幫魯夫大叔找出裝滿他家的大水桶所需要的最少的裝水次數呢?

Input:

輸入檔中會有多筆資料,第一行是一個正整數N,代表一共有多少組資料,接下來是N 組測試資料:

P<換行>

P 表示魯夫大叔家裡大水桶的容量(公升), 1 <= P <= 500

Output:

對每組測試資料,請輸出魯夫大叔最少需要打幾趟水。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
1
29
100

Sample Output :

1
3
6

Hint :

Author :

NPSC 2008 國中組初賽 (管理員:sagit)

  Solve it!   Status Forum