作者babufong (嗶嗶)
看板puzzle
標題[中譯] ProjectEuler 364 Comfortable distance
時間Sun Dec 25 00:08:26 2011
364. Comfortable distance
http://projecteuler.net/problem=364
有 N 個座位排成一排，N 個人依序入座並把座位坐滿，但是入座條件如下：
1. 當有某座位的左右兩個相鄰的座位都沒人時，他就坐這裡。
2. 當已經沒有上述條件的座位時，就退而求其次，挑有一邊沒有坐人的座位坐下。
3. 當已經沒有上述條件的座位時，就挑剩下的座位坐。
使 T(N) 表示為有 N 個人要用上述條件去坐滿 N 個座位時的方法數
下列圖示表示出 T(4) = 8
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │●│ │→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│●│ │ │ │→│●│ │ │●│→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │●│ │ │→│ │●│ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │●│ │→│●│ │●│ │→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│●│ │ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│●│ │ │●│→│●│ │●│●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │ │ │●│→│ │●│ │●│→│●│●│ │●│→│●│●│●│●│
└─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘ └─┴─┴─┴─┘
我們可以驗證出 T(10) = 61632 而 T(1000) mod 100000007 = 47255094。
請算出 T(1000000) mod 100000007。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.5.144
2F：→ utomaya:目前只有24人解出來 看樣子不是容易的題目吶? 12/25 01:13
3F：推 utomaya:解掉了! 第37名，排列組合的問題!!! 12/25 12:09
4F：→ utomaya:OEIS完全幫不上忙 僅供參考而已 12/25 12:11
5F：推 LPH66:解掉了+1 我是第43名XD 果然只是個看起來嚇人的排列組合題 12/25 21:05
6F：→ LPH66:我是直接寫出這個數列的顯式出來了XDDDDDD 12/25 21:05
7F：→ Favonia:lol 12/28 15:15
8F：推 LPH66:閒聊一下, 第365題竟然正好在台灣時間跨年時開放XD 12/31 01:48
9F：→ babufong:我覺得這很陰險 意圖使人難以搶答（誤） 12/31 02:06
10F：推 LPH66:很好...它炸了...想說來搶搶看的說 /_\ 01/01 00:10
11F：→ utomaya:今天應該是Easy題，才那麼多人搶，搶到當機 01/01 01:02
12F：→ utomaya:若沒猜錯的話 出題的難易度有固定pattern,HMEMEMHMEMEMH.. 01/01 01:05
13F：→ utomaya:猜錯了? 這次竟然是M(Medium) 01/01 01:23
14F：→ utomaya:果然沒猜錯 真的是Easy題! 01/01 01:29
15F：推 LPH66:做出來了 XD 第10名 XDDDDD 01/01 01:55
16F：→ LPH66:還好同樣類型的題目以前碰過 回想一下就想起來當初怎麼做的 01/01 01:56