1479. [UVa 1073] 葛伦堡博物馆

【题目描述】

$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 \leq L \leq 1000)$，表示要求的角度序列长度。

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

【输出格式】

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

【样例输入】

4
6
0

【样例输出】

Case 1: 1
Case 2: 6

【提示】

设数据组数为 $T$。
对于 $30\%$ 的数据，$1 \leq T \leq 100，1 \leq L \leq 10$。
对于 $100\%$ 的数据，$1 \leq T \leq 1000,1 \leq L \leq 1000$。

【来源】

UVa 1073 Glenbow Museum

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