问题 4383 --干脆面工厂

4383: 干脆面工厂

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

小浣熊受到梦中的巨大干脆面的启发,决定生产一种更大的干脆面(不只是为了好玩)。但尺寸更大的干脆面对现有的干脆面产线来说是一种挑战,确切地说,这个问题是这样的:

工厂中现在有n条并列的流水线,每条流水线都可以简化为一条长度为m的传送带,例如下图表现了5条并列的、长度为6的流水线:

------

------

------

------

------

当干脆面被放上传送带时,它们由左向右传送;同时为了防止生产事故,同一时间我们只允许一条传送带上安放一块干脆面;由于现有的干脆面产品都很小(让我们用字符'#'表示),它们可以被毫无障碍地排成一列(也许不太整齐)送上传送带:

--#---

-#----

--#---

-#----

---#--

但当小浣熊的超级巨大干脆面被送上传送带时,情况就没有这么乐观了;我们可以将超级干脆面看成一块3×3的巨大正方形,这首先使得第一条和最后一条传送带不再能使用了,我们只能在5条生产线上放置2块超级干脆面,并且它们必须错开放置,避免上下相撞;最后,我们仍然不希望一条传送带上同时放置两块或更多的超级干脆面,这会使得工作人员手忙脚乱,但是允许一条传送带在运载超级干脆面的同时帮助其它传送带抬升另一块超级干脆面的边缘

###---

######

######

---###

------

给出传送带的数量n和长度m,以及超级干脆面的数目k,求是否存在合理的摆放方案,使得n条传送带在同一时刻可以传送k块超级干脆面;如果存在这样的方案,请输出方案的数目;如果不存在,请输出-1

输入

输入仅一行,包含3个正整数n, m, k,中间用空格隔开

输出

输出一个整数,表示摆放超级干脆面的方案情况;

样例输入

5 6 2

样例输出

6

提示


对于100%的数据,保证3 <= n, m <= 10,  1 <= k <= 5;



 



当输入n = 5, m =6,
k = 2时,共有6种方案如下:



① 两块超级干脆面的中心分别位于(2, 2) (3, 5)



###---



######



######



---###



------



 



② 两块超级干脆面的中心分别位于(2, 2) (4, 5)



###---



###---



######



---###



---###



 



③ 两块超级干脆面的中心分别位于(2, 5) (3, 2)



---###



######



######



###---



------



 



④ 两块超级干脆面的中心分别位于(2, 5) (4, 2)



---###



---###



######



###---



###---



 



⑤ 两块超级干脆面的中心分别位于(3, 2) (4, 5)



------



###---



######



######



---###



 



⑥ 两块超级干脆面的中心分别位于(3, 5) (4, 2)



------



---###



######



######



###---

来源

[提交][状态]