題目 2224:
藍橋杯算法提高-Glenbow Museum
時間限制: 2s
內存限制: 192MB 提交: 21 解決: 9
題目描述
卡城著名的格林堡博物館是加拿大西部最大的博物館，展品涵蓋了藝術、文化史以及礦物學。如今一個全新的展區(qū)正在被布置，它是專門為你這樣杰出的程序猿（媛）打造的。不幸的是，由于空間不足，博物館打算建造一棟新的建筑來重新安置這個展區(qū)。
新的建筑的尺寸和容量將不同于原始的建筑，但是所有樓層的設計都是直角多邊形。一個直角多邊形是內角均為90°或270°的多邊形。如果我們記90°角為R（Right）、270°角為O（Obtuse），那么一個只包含R和O的字符串能夠粗略的表示一個直角多邊形。比如，一個矩形（圖形1）就是最簡單的直角多邊形，它能夠用RRRR來描述（內角按逆時針排列，起始角任意）。同樣地，一個十字形直角多邊形（圖形2）能夠用RRORRORRORRO、RORRORRORROR或者ORRORRORRORR來描述。這些序列被稱為角序列。
當然，一個角序列不一定能完全對應一個形狀的多邊形，因為它沒有說明邊長。并且一個角序列不一定能描述一個合法的直角多邊形（比如RRROR）。
為了把事情搞得更麻煩，博物館并不接受所有的樓層設計。一個博物館保存了許多價值連城的物品，它們必須要被看守著。出于對成本的考慮，一個樓層最多只能有一個保安。所以只有滿足以下要求的樓層設計能被接受：存在一個地點使得一個保安能監(jiān)視到整個樓層。因此一個角序列能被接受，當且僅當它描述了一個能夠被接受的多邊形。注意圖形2的十字形直角多邊形能夠被站在中心的保安完全監(jiān)視，所以它是被接受的，因此角序列RRORRORRORRO是被接受的，即使它也能夠描述其他不能被一個保安監(jiān)視的多邊形。
請幫助新建筑的設計師確定有多少給定長度的能夠被接受的角序列。
新的建筑的尺寸和容量將不同于原始的建筑，但是所有樓層的設計都是直角多邊形。一個直角多邊形是內角均為90°或270°的多邊形。如果我們記90°角為R（Right）、270°角為O（Obtuse），那么一個只包含R和O的字符串能夠粗略的表示一個直角多邊形。比如，一個矩形（圖形1）就是最簡單的直角多邊形，它能夠用RRRR來描述（內角按逆時針排列，起始角任意）。同樣地，一個十字形直角多邊形（圖形2）能夠用RRORRORRORRO、RORRORRORROR或者ORRORRORRORR來描述。這些序列被稱為角序列。
當然，一個角序列不一定能完全對應一個形狀的多邊形，因為它沒有說明邊長。并且一個角序列不一定能描述一個合法的直角多邊形（比如RRROR）。
為了把事情搞得更麻煩，博物館并不接受所有的樓層設計。一個博物館保存了許多價值連城的物品，它們必須要被看守著。出于對成本的考慮，一個樓層最多只能有一個保安。所以只有滿足以下要求的樓層設計能被接受：存在一個地點使得一個保安能監(jiān)視到整個樓層。因此一個角序列能被接受，當且僅當它描述了一個能夠被接受的多邊形。注意圖形2的十字形直角多邊形能夠被站在中心的保安完全監(jiān)視，所以它是被接受的，因此角序列RRORRORRORRO是被接受的，即使它也能夠描述其他不能被一個保安監(jiān)視的多邊形。
請幫助新建筑的設計師確定有多少給定長度的能夠被接受的角序列。
輸入格式
輸入文件包含多組測試數據。每組數據一行，包含一個正整數 L (1 <= L <= 1000)，表示給定的角序列長度。
輸入文件以僅包含0的一行結束。
輸入文件以僅包含0的一行結束。
輸出格式
對于每一組數據，輸出一行，包含測試數據編號（從1開始），之后為給定長度的被接受的角序列的個數。具體格式參考樣例輸出。
樣例輸入
4 6 0
樣例輸出
Case 1: 1 Case 2: 6