a388. 00580 - Critical Mass
Tags : DP 組合數學
Accepted rate : 299人/346人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-28 20:04

Content

 

在曼哈坦計畫的早期階段,核子武器的危險性鮮有人知,甚至開發了許多的新的工業城市大量地生產鈾和鈽。這些材料的化合物以及成品被儲存在金屬桶、玻璃罐與紙桶裡,擺放在水泥建的儲存室裡。工人並不知道他們正處理的這些物質可能會導致疾病,或者是更恐怖的爆炸。製造這問題的官方則認為,他們完全可以保證擺放在一起的數量在物理上不足以造成任何的危險。然而錯誤還是發生了──有些工人忽視了這些東西的危險性,常常不按照規矩把過多的原料擺放在一起,使得危險一觸即發。

 

幸運的是,這些危機被一些機智的物理學家小心地處理了。他們制定了一套有關於如何儲存原料的方針來避免過量的原料堆積。

其中處理鈾的系統很簡單,每個裝了鈾的桶子被標記上「U」。當我們要疊上一個鈾桶時,就會先在上面疊上一些前綴桶(標記為「L」),如此一來就不會有超過兩個鈾桶在堆上連續相鄰了。藉著這個簡單的系統,就可以避免潛在的因過度集中擺放而造成的危險。(每個裝了鈾的桶子被標記上「U」,並以一些前綴桶(標記為「L」)穿插於釉桶中,堆上不可以連續擺放超過兩桶以上的鈾桶。藉著這個簡單的系統,可以避免任何釉元素到達臨界質量(三個連續疊放的釉桶)的可能性。)
//由於題意可能引起歧義,這裡給出一個更恰當的翻譯。感謝chchwy

第二個限制則是每一堆桶子都不能有超過30個桶子,因為儲藏室的天花板就只有這麼高。

 

但有一個科學家對這個解決方式還是不滿意。他認為,只要有工人工作時不專心或者不按照系統來,還是有可能會造成連鎖反應。因此他丟出了一個問題:假如有一個工人隨機地把一些有放射性的和沒放射性的n個桶子疊成一堆,那麼有多少種可能的組合會導致悲劇發生呢?

 

例如,假如現在只疊3個桶子,只有一個方式有可能會導致悲劇發生:三個裝有鈾的放射性桶子擺在一起。

 

1:UUU

 

然而,如果疊4個桶子,就有3種方式可以導致悲劇了:

 

1:UUUL

 

2:LUUU

 

3:UUUU

 

Input
輸入的每一行包括一個數字。每行包括一個大於 0 的整數 n ,表示桶子的總數量。輸入為 0 的時候表示輸入結束。
Output
對於每筆輸入,計算出在 n 個桶子的情況下有幾種可能會導致悲劇產生。在這些堆成一列的桶子中,只有兩種桶子:U桶以及L桶(意義如上所述)。對於每筆測試資料輸出一個獨立的行,每行只包含解答一個數字。
Sample Input #1
4
5
0
Sample Output #1
3
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
DP 組合數學
出處:
UVA 580 [管理者: liouzhou_101 (王启圣) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40949 joccc014@gma ... (czone) a388
想法&思路
144 2024-06-21 01:06