a534: IOI2008 Day2.1.花園問題
Tags :
Accepted rate : 14人/14人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:06

Content

    拉姆西斯(Ramesses)二世剛打勝戰回來,為了慶祝戰爭勝利,他決定建一座皇家花園。花園將由一長排的植物所組成,從他在路克索(Luxor)的皇宮一直延伸到卡納克神殿(Temple of Karnak)。而所種的植物僅由連花(lotus)及紙莎草(papyrus)二種組成,它們分別是上埃及與下埃及的象徵。

    此花園必須種植N顆植物:而且植物數必須平衡,也就是在花園的任何連續區段中蓮花與紙莎草的數量差異不能大於2

    一個花園可以用字母L(lotus)P(papyrus)所組成的字串表示。例如,當N=5時,有14種可能的平衡花園,依英文字母次序排序如下:

LLPLP, LLPPL, LPLLP,LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL

    某一長度的所有可能平衡花園,可依英文字母次序排序,並從1開始編號。例如,當N=5時,編號12的花園是平衡花園PLPPL

    給定N棵植物及一表示平衡花園的字串,請寫一個程式計算出該平衡花園的編號,並取其除以一給定整數M的餘數

注意,M在本題中與解題無關,它只是用來簡化計算。 

Input

程式需從標準輸入讀入下列資料:

·    第一行有一整數N,指花園中的植物的總數。

·    第二行有一整數M 

·    第三行有一N個字元的字串,由字母L(lotus)P(papyrus)組成,代表某一個平衡花園。

Output

程式輸出一個介於0M-1的整數至標準輸出。輸出的整數是輸入的平衡花園的編號,除以M所得到的餘數。

Sample Input
範例輸入1
5
7
PLPPL

範例輸入2	
12
10000
LPLLPLPPLPLL
Sample Output
範例輸出1
5

範例輸出2
39
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :

100%的數據滿足 

1 <= N <= 1,000,000

7 <= M <= 10,000,000
Tags:
出處:
IOI2008Day2第一題 [管理者:
david942j (文旋)
]


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