It's the first complete completion, and the ranking is also the top 9%. Why isn't it rated! (Desk bang bang).
Break through in 2 minutes. If the sun has already hit, the current position answers. If the current position is less than L, L answers, and if the current position exceeds R, R answers.
S, L, R = map(int, input().split())
if L <= S <= R:
print(S)
elif S < L:
print(L)
elif S > R:
print(R)
Break through in 6 minutes. Sort R and B, display R in ascending order, then display B in ascending order. Of course, sort in ascending order.
N = int(input())
R = []
B = []
for _ in range(N):
X, C = input().split()
if C == 'R':
R.append(int(X))
elif C == 'B':
B.append(int(X))
R.sort()
B.sort()
if R:
print('\n'.join(str(r) for r in R))
if B:
print('\n'.join(str(b) for b in B))
Break through in 12 minutes. N is 9 at most, so all you have to do is brute force. Itertools.permutations I love you.
from itertools import permutations
a1, a2, a3 = map(int, input().split())
a = [a1, a2, a3]
N = a1 + a2 + a3
result = 0
for p in permutations(range(1, N + 1)):
X = [p[:a1], p[a1:a1 + a2], p[a1 + a2:]]
flag = True
for i in range(3):
for j in range(1, a[i]):
if X[i][j] <= X[i][j - 1]:
flag = False
for i in range(1, 3):
for j in range(a[i]):
if X[i][j] <= X[i - 1][j]:
flag = False
if flag:
result += 1
print(result)
Break through in 23 and a half minutes. If you do naive, take TLE. X with * O * (10 10 </ sup>) to take all A and GCD, take all A's GCD and X's GCD Same as. If X does not become 1, then it becomes * O * (10 5 </ sup>) and it is cleared up. The number of operations when X becomes 1, but the GCD of A is taken in order. Since only the changed parts are candidates, check only the changed parts. It is unknown how much the order will be lowered by this, but intuitively it should be greatly reduced, so if you submit it, it will be safe AC.
from math import gcd
N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = list(map(int, input().split()))
gcd_a = A[0]
a = [(1, A[0])]
for i in range(1, N):
t = gcd(gcd_a, A[i])
if t != gcd_a:
gcd_a = t
a.append((i + 1, gcd_a))
for i in range(Q):
X = S[i]
t = gcd(gcd_a, X)
if t != 1:
print(t)
else:
for j, g in a:
if gcd(X, g) != 1:
continue
print(j)
break
Postscript: It seems that everyone is solving it, so I tried to solve it even with a pig.
from math import gcd
N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = list(map(int, input().split()))
for i in range(N - 1):
A[i + 1] = gcd(A[i + 1], A[i])
for i in range(Q):
X = S[i]
t = gcd(A[-1], X)
if t != 1:
print(t)
else:
ng = -1
ok = N - 1
while ok - ng > 1:
m = (ok + ng) // 2
if gcd(X, A[m]) == 1:
ok = m
else:
ng = m
print(ok + 1)
Recommended Posts