/ OPS / 题库 /

座位安排

座位安排

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

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

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

#样例1#
##样例输入1##
input1
1 4 3
input2
2 3 2

##样例输出1##
input1
Impossible!
input2
15/8

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

信息

ID
3303
难度
9
分类
category1category2 点击显示
标签
递交数
2
已通过
1
通过率
50%
上传者