67 lines
1.4 KiB
Python
67 lines
1.4 KiB
Python
import operator
|
|
from math import *
|
|
from pprint import pprint
|
|
|
|
n, m, q = map(int, input().split())
|
|
|
|
|
|
def f(s):
|
|
if s == 0:
|
|
return 0
|
|
if s == float('inf'):
|
|
return m * n - 1
|
|
return m - 1 + sum(m - y // s - 1 for y in range(1, n + 1))
|
|
|
|
|
|
def g(s1, s2):
|
|
print(f"g({s1},{s2})")
|
|
lst = []
|
|
if s2 == float('inf'):
|
|
for x in range(0, m):
|
|
for y in range(int(ceil(x * s1)), n):
|
|
if (x, y) != (0,0):
|
|
lst.append((x, y))
|
|
else:
|
|
for x in range(0, m):
|
|
for y in range(int(ceil(x * s1)), int(floor(x * s2) + 1)):
|
|
if (x, y) != (0,0):
|
|
lst.append((x, y))
|
|
|
|
|
|
return lst
|
|
|
|
|
|
def search(i, bound):
|
|
lowerS = 0
|
|
lowerC = 0
|
|
upperS = float('inf')
|
|
upperC = m * n - 1
|
|
|
|
while (upperC - lowerC > bound):
|
|
tempS = (lowerS + upperS) / 2
|
|
tempC = f(tempS)
|
|
|
|
if (tempC > i):
|
|
upperC = tempC
|
|
upperS = tempS
|
|
else:
|
|
lowerC = tempC
|
|
lowerS = tempS
|
|
|
|
return g(lowerS, upperS), lowerC
|
|
|
|
|
|
def get(i):
|
|
print('case i=', i)
|
|
pts, lowc = search(i, 1000)
|
|
pts = sorted(((y / x if x != 0 else float('inf')), x, y) for x, y in pts)
|
|
print(i, lowc)
|
|
pprint(pts)
|
|
_, x, y = pts[i - lowc]
|
|
return y + 1, x + 1
|
|
|
|
|
|
for _ in range(q):
|
|
i = int(input()) - 1
|
|
print(*get(i))
|