葛伦堡博物馆

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file glenbow.in Output file glenbow.out

【题目描述】

Calgary市著名的葛伦堡博物馆是加拿大西部最大的博物馆,它的主题包括艺术,文化史和矿物学。博物馆计划给像你这样机智的程序员开设一个新展区。不幸的是,由于缺乏空间,博物馆将不得不建造一个全新的场馆,并且搬迁进去。

新场馆的大小,外形与传统的建筑不同。但二者都是直角多边形。直角多边形是指内角为90°或270°的多边形。如果90°的内角被表示为R(Right的缩写),270°的内角被表示为O(Obtuse的缩写),那么一个仅由R和O组成的序列能大致描述一个直角多边形。例如,矩形(图1)是最简单的直角多边形,它可以被描述为RRRR(内角以逆时针方向列出,可以从任意一个角开始)。类似地,一个十字形(图2)可以被描述为RRORRORRORRO,RORRORRORROR,或ORRORRORRORR。这种R/O序列被称作角度序列。

当然,一个角度序列并不能完全确定直角多边形的形状——它并不能表示边的长度。并且一些角度序列不能表示某个合法的直角多边形(例如RRROR)。

使事情更麻烦的是,并非所有的直角多边形都能作为新场馆的形状。博物馆里有许多价值连城的物品,因此必须采取安保措施。出于成本考虑,一个场馆中只能配备一名警卫。因此场馆的形状必须满足这样的条件:场馆内存在一个点,使得站在这一点处的警卫可以看到整个场馆。类似地,只有一个角度序列对应至少一个合法的直角多边形时,这个角度序列才是合法的。注意到图2中的十字形场馆中,一名站在正中央的警卫可以看到整个场馆,因此图2中的多边形是合法的。因此角度序列RRORRORRORRO是合法的,虽然它能描述另外一些不合法的直角多边形。

请帮助新场馆的设计者计算有多少个合法的角度序列,其长度为给定的正整数L。

【输入格式】

输入文件包含多组数据。

每一组数据有一行,包含一个正整数L(1<=L<=1000),表示要求的角度序列长度。

输入文件以一个“0”结束。

【输出格式】

对于每组数据,输出一行,包含数据编号(从1开始)和相应的合法序列个数。具体格式见样例。

【样例输入】

4
6
0

【样例输出】

Case 1: 1
Case 2: 6

【提示】

设数据组数为T。
对于30%的数据,1<=T<=100,1<=L<=10。
对于100%的数据,1<=T<=1000,1<=L<=1000。

【来源】

UVa1073 Glenbow Museum

刘汝佳,《算法竞赛入门经典训练指南》表2.2