分子侦测Detecting Molecules - International Olympiad in Informatics.PDFVIP

International Olympiad in Informatics 2016 12-19th August 2016 Kazan, Russia mmoolleeccuulleess day1_1 Country: TWN 分子偵測 Detecting Molecules Petr 正在為一個公司工作 ，這個公司已經建構出一台可以偵測分子的機器。每個分子有一個正整 數的 重。這台機器有一個偵測範圍[l,u] ，其中 l 和 u 皆為正整數。這台機器可以偵測出一組 分子的集合若且唯若這個集合所包含的分子其總 重介於這個機器的偵測範圍之內。 正式地來說 ，考慮n 個分子其正整數 重分別為w , … ,w 。如果有存在一組互不相同的註 0 n−1 標組合I = {i , … ,i } ，使得l ≤ w + …w ≤ u ，我們則稱此偵測是成功的。 1 m i1 im 由於機器的特殊性 ，l 和 u 之間的間距必需保證要大於或等於最重和最輕的分子 重之間距。正 式地來說 ，u − l ≥ w − w ， 其中 w = max (w , … ,w ) and max min max 0 n−1 w = min(w , … ,w ) 。 min 0 n−1 你的任務是寫一個程式去找出任一組分子其總 重在偵測範圍之內，或決定這組分子並不存在。 實作細節 你應該要實作一個函式(方法): int[] solve(int l, int u, int[] w) l 和 u: 偵測範圍的端點, w: 分子的 重(weights of the molecules). 如果滿足條件的分子組合存在 ，則函式回傳任一組滿足條件的分子組合註標陣列 (array of indices)。如果有多組解答 ，則回傳任一組正解。 如果沒有滿足條件的分子組合 ，則函式應回傳空陣列。 對於C程式語言而言 ，其函式特徵有一些不同 ： int solve(int l, int u, int[] w, int n, int[] result) n: 在w 中的元素個數(亦即分子的個數) ，　 其他參數如前所描述。 如果有一組滿足條件的分子組合包含m 個分子 ，函式應寫入註標到陣列result 的前 m 個位置 ，並且回傳m 。 如果沒有滿足條件分子組合 ，則函式不用寫入任何資訊到result陣列 ，並回傳0 。 你的程式可以用任何次序寫入註標到回傳的陣列(或在C中寫到result陣列) 在你使用的程式語言實作時,請使用所提供的對應樣板程式檔案去實作。 範例 範例一 solve(15, 17, [6, 8, 8, 7]) 1 / 2 在此範例中，我們有四個分子 ，其重量分別為　6, 8, 8 和 7。 這台機器可偵測一組分子其 重總 和介於 15 和 17 之間（包含 15 和 17）。請注意17 − 15 ≥ 8 − 6 。分子 1 和分子 的總 重為 w1 + w3 = 8 + 7 = 15 ，所以函式可回傳 [1, 3]。此範例有其他正確解為[1, 2] ( w1 + w2 = 8 + 8 = 16 ) 和 [2, 3] ( w2 + w3 = 8 + 7 = 15 )。 範例二 solve(1 , 15, [5, 5, 6, 6]) 在此範例中，我們有四個分子