OI题库

【题目描述】

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