2017年华中科技大学ACM招新赛

From: 2016-12-18 12:30:00 To: 2016-12-18 17:30:00 Now: 2017-09-24 21:44:05 Status: Public

G - 电影院

Time Limit: 1s Memory Limit: 128MB

Submissions: 22 Solved: 6
Description

 

LLY去看电影啦!

 

LLY只买了一张票!

 

LLY一个人入场啦!

 

LLY疯狂吃狗粮

 

       已知电影院的座位通常分为四个区域。现在,单身狗保护会研究决定,设计一种电影院的布局,以保证每排中间区域至少会有一位像LLY这样的单身狗。

 

       单身狗保护协会请你帮助规划电影院的座位布局。座位布局需要满足下述两个条件:

 

       1.座位分为A, B, C, D四个区域,且每个区域的座位数不能为零。

 

       2.中间区域(B&C)的座位数必须为奇数,以保证每排至少有两个像LLY这样的单身狗(微笑)。

 

       你需要知道一共有多少种不同的座位规划方式。两种布局被认定为不同,当且仅当它们A, B, C, D的座位数不全对应相等。

 

 

 

Input

 

       第一行为样例组数T(T<=10000)

 

       接下来每行有一个整数n,代表一排的座位数。(4<=n<=1000000)

 

Output

 

       对每个n首先输出“Case #i: ”(不包含引号,冒号后有一个空格),其中i对应它为第几组数据。输出它对应的规划方式数k

 

 

Sample Input
2
4
5
Sample Output
Case #1: 1
Case #2: 2
Hint

 

       对第一种情况,仅有1 1 1 1”这一种可能。

 

       对第二种情况,有2 1 1 1”“1 1 1 2”两种可能。

 

输出结果可能超出int范围,请使用longlong长整型。

 

Source
songwenhao