Suddenly I was surprised to be 10 minutes late. I feel lucky that I solved the C and D problems. Well, it's good sometimes because I often get confused if I miss the solved problem.
Break through in two and a half minutes. A chicken that spins a loop while thinking that it can be written with * O * (1).
K = int(input())
A, B = map(int, input().split())
for i in range(A, B + 1):
if i % K == 0:
print('OK')
exit()
print('NG')
Postscript: I also wrote in * O * (1).
K = int(input())
A, B = map(int, input().split())
if (B // K) * K >= A:
print('OK')
else:
print('NG')
Break through in 4 minutes. When I saw X ≤ 10 18 </ sup>, I thought that TLE was possible even though it was a B problem, but even if I gave 10 18 </ sup> in the code test, it wasn't at all. I was fine, so I was wondering what it was, AC.
X = int(input())
t = 100
result = 0
while t >= X:
t += t // 100
result += 1
print(result)
It broke through in 23 and a half minutes. The moment I saw the problem, my head turned white, but I managed to solve it. The moment I AC, I thought that the current ranking was amazing, but everyone solved the D problem first and even so far I didn't (laughs).
Well, I wondered if I should do a brute force attack, but if I generate it including invalid ones, it seems that * O * (10 10 </ sup>) will not work. Pay attention to 1 ≤ M ≤ 10. , M -1 is 0-9, so it can be expressed as a character string, so I decided to generate all the valid sets of character strings. After that, I thought that I would do brute force. TLE, but without AC ..
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
m = M - 1
def f(s):
if len(s) == N:
return [s]
result = []
if s == '':
r = 0
else:
r = int(s[-1])
for i in range(r, m + 1):
result.extend(f(s + str(i)))
return result
result = 0
V = f('')
for s in V:
A = [int(c) + 1 for c in s]
t = 0
for a, b, c, d in abcd:
if A[b - 1] - A[a - 1] == c:
t += d
result = max(result, t)
print(result)
Postscript: It seems that I didn't have to do my best to generate all the sets by myself. Python is great.
from itertools import combinations_with_replacement
N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]
result = 0
for A in combinations_with_replacement(range(1, M + 1), N):
t = 0
for a, b, c, d in abcd:
if A[b - 1] - A[a - 1] == c:
t += d
result = max(result, t)
print(result)
Break through in 20 minutes. I thought that there should be a maximum value at the timing when Ax / B increases, so when I solve the equation of Ax / B = n, x = Bn / A, so x is incremented by 1 by N. I tried turning it until it became. However, since this is the case when A <B, I tried turning it to A for that case. When I put it out with a messy combination, AC came and I was surprised myself. I didn't understand much, but I solved it ...
The moment I solved the D problem, I had a dream of blue performance because I was in the 900s, but I'm sorry that I couldn't solve the E problem and retreated to the 1500th place.
from math import floor
A, B, N = map(int, input().split())
def f(x):
return floor(A * x / B) - A * floor(x / B)
result = 0
for x in range(min(A + 1, N + 1)):
result = max(result, f(x))
if B > A:
for i in range(10 ** 20):
x = (i * B + A - 1) // A
if x > N:
break
result = max(result, f(x))
print(result)
Postscript: I used to go through well (sweat). However, the difficulty levels of D and C problems are completely switched.
A, B, N = map(int, input().split())
x = min(B - 1, N)
print(A * x // B - A * (x // B))
Lost. I knew that I should set the distance to 1, 2, ..., M, but I couldn't figure out how to pack the combinations that satisfy it between M.
Addendum: The condition is that the difference between a and b is different, but since it is circular, it may be the same even if the difference is different (for example, (1, 4) when N = 4). (2, 3) seems to be different by 3 difference and 1 difference, but since 4 is next to 1, both are 1 difference). In conclusion, if the distance is 1, 2, ..., M Good. In this case, it is unique even if it circulates from the condition of M × 2 + 1 ≤ N. Next, how to take the combination, first take the longest 1 and M + 1. Of course, inside it Since the one with the distance M-1 does not enter, take it with M + 2 and 2M + 1 next to it. Next, since it is the distance M-2, it enters between 1 and M + 1, so take it with 2 and M. Next is the distance M-3, so I think it's okay to take it at M + 3 and 2M, so divide it into two parts and pack them inside like a Matryoshka doll.
N, M = map(int, input().split())
for i in range(1, M + 1):
if i % 2 == 1:
j = (i - 1) // 2
print(1 + j, M + 1 - j)
else:
j = (i - 2) // 2
print(M + 2 + j, 2 * M + 1 - j)
Recommended Posts