1324. 座位安排

时间限制 1000 ms   内存限制 128 MB

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

输入数据

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

输出数据

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

样例输入

复制
input1
1 4 3
input2
2 3 2      \n
 · · \n
      \n
 · · \n

样例输出

复制
input1
Impossible!
input2
15/8      \n
           \n
      \n
    \n

样例说明

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

提交

请先 登录

© 2026 FAQs Contact About