题目名称 1524. [UVa 12117] ACM谜题
输入输出 acmpuzzle.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2014-02-15
开放分组 全部用户
提交状态
分类标签
动态规划 状态压缩 UVa
通过:2, 提交:5, 通过率:40%
Gravatarranto 100 0.007 s C++
Gravatarcstdio 100 0.361 s C++
Gravatarranto 0 0.011 s C++
Gravatarranto 0 0.011 s C++
Gravatarranto 0 0.160 s C++
关于 ACM谜题 的讨论
输出格式错了。
唉..
Gravatarranto
2014-02-15 20:30 1楼
儿童机协会
Association of Children Machines,ACM

笑尿
Gravatardigital-T
2014-02-15 21:17 2楼

1524. [UVa 12117] ACM谜题

★★☆   输入文件:acmpuzzle.in   输出文件:acmpuzzle.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

儿童机协会(Association of Children Machines,ACM)正计划给小朋友们设计一类新的拼图游戏。这些拼图都是3*N的网格,并且使用如下的图形进行拼接。这些图形都可以出现任意次。由于ACM推出的这种拼图供不应求,因此许多别的公司发布了外观相同的仿制品,例如“穿越拼图”,“拼图联盟”。

为了阻止假冒产品,ACM已经采取了措施,他们希望借此帮助商家避免自己的商店中出现仿品。因为所有的拼图都是3*N的网格,并且对于较大的N,一个3*N的拼图可能有无数种放法。ACM的工厂制作的所有拼图都只会有几种特定的放法数量。这个数量是独一无二的,并且只是所有N对应放法数的一小部分。因此假冒产品的放法数很可能不同。你将在最初的部分帮助他们:给出N的值,你将要找出用给定图形填满3*N拼图的方案总数。这些图形不能旋转,但每个图形都可以用任意多次。当然,有的图形仅仅是另外图形旋转得到的,但它们同样不能被旋转。例如,倒着的T型(棕色块)不能被旋转成正着的T型(粉色块)。

【输入格式】

输入文件包含多组数据。

每组数据有1行,包含一个正整数N(0<N<2001)。N表示网格的宽度。网格的高度总是3.

输入结束标志为N=0.不必处理这组数据。

【输出格式】

对每组数据,输出一行。这一行是一个固定的串,后面跟上方案数模10^12的值。具体格式见样例。

【样例输入】


5

100

0


【样例输出】


Case 1: 26

Case 2: 584039302899


【样例解释】

N=5的情况

【来源】

Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman

UVa12117 ACM Puzzles