问题 3515 --座位安排

3515: 座位安排

题目描述

  考场里的座位恰好有n行m列,并且恰好有n*m位考生在这个考场里面考试,也就是说,所有的座位上都有考生。hzy根据学校记载,有k位考生可能作弊,因此hzy不能让他们之中的任何两个人做在相邻的座位上!所谓相邻的座位,即在同一行相邻列或者在同一列的相邻行的座位。hzy准备这样安排座位,首先随机选择一种方案,如果这种方案是合法的,就用这种方案,否则重新选择。你的任务是计算,他得到一个合法方案时,需要的期望选择次数。

输入

输入文件为一行,仅包含三个整数n,m和k。

输出

如果不存在合法的方案,则输出文件seating.out中应该包含Impossible!,否则输出一个分数p/q,表示期望选择次数(即平均次数),这里p和q应该是互质的。

样例输入输出

输入#1 复制
1 4 3
输出#1 复制
Impossible!
输入#2 复制
2 3 2
输出#2 复制
15/8

提示

1≤n≤80,1≤m≤80,1≤n*m≤80 0≤k≤20,并且k≤n*m

序号 标题 作者 发表时间 费用 订购数 操作