c239. 旅行者_九國遊歷記<4> 小綠去焱國
Tags : 旅行者
Accepted rate : 44人/50人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-09-24 09:49

Content

小綠來到焱國,發現他們盛產蔬菜,於是想去他們的市集看看。

到了市集,他發現正在舉行蔬菜節,而聽說有比賽,他想了解看看。

"規則是......"他尋找著。

他找到比賽海報,上面有了規則,比賽規則是參賽者3天內需前往當年選出的n位蔬菜公主的家,要完成他們所指定的任務,最快完成所有任務的人獲勝。他們一開始會到集合地點開始競賽,主辦單位給他們地圖,地圖上標示所有地方之間移動所需的時間。參賽者需自行選擇一位公主家當起點,並從起點出發,解完每一公主家的任務後返回起點。計算的時間為從起點出發,解完所有任務,返回起點所花的時間。

小綠對比賽躍躍欲試,他對他自己解任務很有自信,所以他很好奇他需要多久時間移動,才能花最少時間移動。但他又突然好奇最少和最多的移動時間相差之倍數,於是開始比賽時,一拿到地圖就開始計算.....

Input

本題為EOF檔,每筆測資第一行有數字n代表有n(1<n<=15)位公主,接下來n-1行代表每行有依序有n-1,n-2......1個數,代表第i個公主家到第j個公主家所需的時間,所有數字<=1000

40%的測資,n<=6

100%的測資,n<=15

Output

輸出小綠最多移動時間是最少的幾倍。(化簡為最簡分數)

Sample Input #1
4
1 2 3
6 2
3
Sample Output #1
13/8
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (30%): 1.0s , <1K
公開 測資點#2 (40%): 1.0s , <1M
Hint :

 

 

範例圖解

 1234
1 123
2  62
3   3
4    
Tags:
旅行者
出處:
106學年度板橋高中校內資訊學科能力競賽 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」