Break through in a minute and a half. Just write. It took a lot of time because the code test wasn't executed easily.
A, B = map(int, input().split())
print(A * B)
Break through in 3 minutes. It's a problem that even 64-bit integers overflow, but it's easy because you don't have to think about anything in Python. Don't forget to sort to start with 0 OK!
N = int(input())
A = list(map(int, input().split()))
limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
result *= a
if result > limit:
print(-1)
exit()
print(result)
Break through in 3 minutes. The moment I saw A ≤ 10 15 </ sup>, I realized that it was double, so I escaped to decimal. (10 15 </ sup> is 10 > 3 </ sup> ≒ 2 10 </ sup> So, roughly ≒ 2 50 </ sup>, so it is close to the 52bit immutable part of double, and you can see that it is an act to overflow it. .)
from decimal import Decimal
A, B = map(Decimal, input().split())
print(int(A * B))
It broke through in 22 and a half minutes, WA1. I thought I would stick the Eratosthenes sieve for the time being, but I couldn't stick it because N ≤ 10 12 </ sup>, so I started by changing to the processing up to sqrt (N). I enumerated p e </ sup> in, and when I divided it in the order of pounding and processed the remaining values, I failed and got WA, but maybe this code is also a lie. (Remains properly) Does it seem like you have to check if it's a prime number?)
from math import sqrt
N = int(input())
rn = int(sqrt(N))
sieve = [0] * (rn + 1)
sieve[0] = -1
sieve[1] = -1
t = [0] * (rn + 1)
for i in range(2, rn + 1):
if sieve[i] != 0:
continue
sieve[i] = i
j = i
while j < rn + 1:
t[j] = 1
j *= i
for j in range(i * i, rn + 1, i):
if sieve[j] == 0:
sieve[j] = i
result = 0
last = -1
for i in range(2, rn + 1):
if t[i] == 0:
continue
if N % i == 0:
result += 1
N //= i
last = i
if N != 1 and N > rn:
result += 1
print(result)
Addendum: I could write more quickly using the prime factorization function I wrote earlier. Failure.
def prime_factorize(n):
result = []
if n % 2 == 0:
t = 0
while n % 2 == 0:
n //= 2
t += 1
result.append((2, t))
for i in range(3, int(n ** 0.5) + 1, 2):
if n % i != 0:
continue
t = 0
while n % i == 0:
n //= i
t += 1
result.append((i, t))
if n == 1:
break
if n != 1:
result.append((n, 1))
return result
N = int(input())
result = 0
for p, e in prime_factorize(N):
i = 1
while e >= i:
result += 1
e -= i
i += 1
print(result)
I couldn't break through. I was thinking for over an hour, but the more I think about it, the more difficult it is.
PS: I thought there was a possible median between the median of A i </ sub> and B i </ sub> during the contest, but I'm sure they are all. I couldn't get it. However, it may have been necessary to be prepared to pop it out with a rotten reading. With yukicoder, I throw it hoihoi because there is no pena (laugh). If you start with> i </ sub> starting with A i </ sub> and increase any of them by 1, the median will not increase or increase by 1 (or even 0.5 could be 0.5). I can understand that it is true ...
N = int(input())
A = [None] * N
B = [None] * N
for i in range(N):
a, b = map(int, input().split())
A[i] = a
B[i] = b
A.sort()
B.sort()
if N % 2 == 0:
b = (B[N // 2] + B[(N - 1) // 2]) / 2
a = (A[N // 2] + A[(N - 1) // 2]) / 2
print(int((b - a) * 2 + 1))
else:
print(B[N // 2] - A[N // 2] + 1)
Recommended Posts