锐客网

  1. 首页 > it技术 > >

蓝桥

Glenbow Museum
问题描述 卡城著名的格林堡博物馆是加拿大西部最大的博物馆，展品涵盖了艺术、文化史以及矿物学。如今一个全新的展区正在被布置，它是专门为你这样杰出的程序猿（媛）打造的。不幸的是，由于空间不足，博物馆打算建造一栋新的建筑来重新安置这个展区。
新的建筑的尺寸和容量将不同于原始的建筑，但是所有楼层的设计都是直角多边形。一个直角多边形是内角均为90°或270°的多边形。如果我们记90°角为R（Right）、270°角为O（Obtuse），那么一个只包含R和O的字符串能够粗略的表示一个直角多边形。比如，一个矩形（图形1）就是最简单的直角多边形，它能够用RRRR来描述（内角按逆时针排列，起始角任意）。同样地，一个十字形直角多边形（图形2）能够用RRORRORRORRO、RORRORRORROR或者ORRORRORRORR来描述。这些序列被称为角序列。

蓝桥
文章图片




当然，一个角序列不一定能完全对应一个形状的多边形，因为它没有说明边长。并且一个角序列不一定能描述一个合法的直角多边形（比如RRROR）。
为了把事情搞得更麻烦，博物馆并不接受所有的楼层设计。一个博物馆保存了许多价值连城的物品，它们必须要被看守着。出于对成本的考虑，一个楼层最多只能有一个保安。所以只有满足以下要求的楼层设计能被接受：存在一个地点使得一个保安能监视到整个楼层。因此一个角序列能被接受，当且仅当它描述了一个能够被接受的多边形。注意图形2的十字形直角多边形能够被站在中心的保安完全监视，所以它是被接受的，因此角序列RRORRORRORRO是被接受的，即使它也能够描述其他不能被一个保安监视的多边形。
请帮助新建筑的设计师确定有多少给定长度的能够被接受的角序列。 输入格式 输入文件包含多组测试数据。每组数据一行，包含一个正整数 L (1 <= L <= 1000)，表示给定的角序列长度。
输入文件以仅包含0的一行结束。 输出格式 对于每一组数据，输出一行，包含测试数据编号（从1开始），之后为给定长度的被接受的角序列的个数。具体格式参考样例输出。 样例输入 4
6
0 样例输出 Case 1: 1
Case 2: 6 数据规模和约定 按题目描述所示。

解法： 基本图形：
n(角序列长度)=8R=6O=2
蓝桥
文章图片
蓝桥
文章图片

由上可得出：R=O+4
所以n=R+O=2O+4——> R=(n+4)/2O=(n-4)/2

n不能为奇数，不能存在连O和首尾为O的情况。问题转化为在（n+4）/2个R之间插入O，每个R旁边只能插一个O，因为O不能相连。要是往O之间插R，每个位置可以插数量不定的R，问题复杂化。

考虑两种插法：
（1）在每个R后面插的R个位置中选任意O个位置插O，即求组合C（（n+4）/2，（n-4）/2 ）=C（（n+4）/2，4 ）
（2）第一个位置为O，则最后一个位置必须为R（即最后一个R后面位置不能插），则求组合C（（n+4）/2 - 1，（n-4）/2 -1）=C（（n+2）/2 ，4 ）
所以就求C（（n+4）/2，4 ）+ C（（n+2）/2 ，4 ）//4是（n+4）/2-（n-4）/2=4 所以代码如下：

#include long long int we(int n) { long long int sum=1; for(int i=n-4+1; i<=n; i++) { sum*=i; } return sum/24; } int main() { int n; int cnt=0; while(scanf("%d",&n)!=-1) { ++cnt; if(n==0) break; if(n<4||n&1) { printf("Case %d: 0\n",cnt); } else{ int t; t=(n+4)/2; int t1; t1=(n+2)/2; printf("Case %d: %lld\n",cnt,we(t)+we(t1)); } } }









【蓝桥】

    推荐阅读


    上一篇：pta学习笔记|Pta:实验四（查找指定字符）

    下一篇：Flink DataStream流表与维表Join(Async I/O)