-
Notifications
You must be signed in to change notification settings - Fork 11
/
kattis_thinkingofanumber.py
57 lines (44 loc) · 1.36 KB
/
kattis_thinkingofanumber.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
'''
Kattis - thinkingofanumber
We observe that regarding the minimum and maximum, we only need to take the maximum lowerbound and the
minimum upperbound. As for the divisiblity, our final answer only needs to be divisble by the LCM
of all the numbers provided. We note that the final search space is small so we can brute force check
divisbility for all numbers between mini and maxi. If we needed to go faster, we could use the
use x0 + n*l to generate the required numbers.
Time: O(n), Space: O(1)
'''
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
while (1):
n = int(input())
if (n == 0):
break
l = 1
maxi = -1
mini = 1
for _ in range(n):
op1, op2, x = input().split()
x = int(x)
if (op1 == "less"):
if (maxi == -1):
maxi = x-1
maxi = min(maxi, x-1)
elif (op1 == "greater"):
mini = max(mini, x+1)
else:
l = lcm(l, x)
if (maxi == -1):
print("infinite")
continue
if (maxi < mini):
print("none")
continue
has_sol = 0
for i in range(mini, maxi+1):
if (i % l == 0):
has_sol = 1
print(i, end=" ")
if (not has_sol):
print("none", end="")
print()