SRM 594 DIV 2

一般编程题，稍加思考可以推出：

(1) 从任意一个位置开始，如果能坐上所有位置，则从其他位置开始同样可以

(2) 1的否命题也成立

指定从 ((0, 0)) 开始，编程模拟坐的过程即可判断Possible还是Impossible。

【优化】

(m)、(n) 互质的情况才可以坐上所有座位

从 ((0, 0)) 开始，到达 ((mn-1, mn-1)) 时一共坐上了 (mn) 个座位，下一个座位又回到了 ((0, 0))

若 (m)、(n) 互质则不存在整数 (p)、(q) 使得 (pm=qn<mn)，所以：

从 ((0, 0)) 到 ((mn-1, mn-1)) 中不存在 ((0, 0))

若 ((0, 0)) 到 ((mn-1, mn-1)) 中存在两个位置相同则可以推出存在另外一个 ((0, 0)) ，矛盾，所以：

从 ((0, 0)) 到 ((mn-1, mn-1)) 中不存在任何两个位置相同

综上，命题得证，以下只给出模拟法的代码

 1 class FoxAndClassroom:
 2     def ableTo(self, n, m):
 3         row = beginRow = 0
 4         col = beginCol = 0
 5         counter = n * m - 1
 6         while True:
 7             row = (row + 1) % n
 8             col = (col + 1) % m
 9             if row == beginRow and col == beginCol:
10                 break
11             counter -= 1
12         if counter == 0:
13             return 'Possible'
14         else:
15             return 'Impossible'
16 
17 # test
18 o = FoxAndClassroom()
19 
20 # test case
21 assert(o.ableTo(2, 3) == 'Possible')
22 assert(o.ableTo(2, 2) == 'Impossible')
23 print('ok')

View Code