d916: 4. 高空煙火時間限制
標籤 :
通過比率 : 93% (151 人 / 162 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2010-12-23 09:58

內容
  一家專門為大型活動施放煙火的公司,在這次花博標到一件案子,負責沿著河岸施放高空煙火,在河岸每間隔一定距離會設立一個煙火施放點,假設總共有 N 個施放點。煙火的類型主要有兩類,分別為單色系列及彩色系列。單色系列的煙火施放後僅會出現單一顏色的煙火,而彩色系列的煙火施放後會出現多種顏色的彩色煙火。為了讓煙火施放效果生動,兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來,因此施放煙火的方式有許多種可能的施放組合。例如:N = 3, M = 1 時有 5 種可能施放的方式,即:單單單,彩單單,單單彩,單彩單,彩單彩。
  阿博剛好在這家公司打工,給定施放點的個數 N M 的值,阿博的老板要他幫忙算出有多少種可能的施放煙火方式。你的任務是寫一個程式幫阿博計算出所有可能的施放方式。因為答案可能是非常大的數字,為了讓大家能夠簡化運算,所以我們只要求輸出答案最右邊的四位數 (以十進位表示),也就是答案除以10000 後的餘數 (以十進位表示)。
輸入說明
輸入檔包含兩個正整數 N M ,其中 N 代表施放煙火的施放點總數,M 用來代表兩個施放彩色煙火的施放點之間必須至少有 M 個施放單色煙火的施放點間隔開來。其中 1 <= M < N <= 3000,並以一或多個空白隔開。
輸出說明
假設所有可能施放煙火方式的總數為 P,請輸出 P 除以 10000 後的餘數 (以十進位表示)。
範例輸入
輸入範例 1:
3 l

輸入範例 2:
19 1

輸入範例 3:
25 1
範例輸出
輸出範例 l: 
5

輸出範例 2:
946

輸出範例 3: 
6418
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1K
提示 :
標籤:
出處:
99學年度全國資訊學科能力競賽 [編輯:
pcshic (PCSHIC)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」