AtCoder Beginner Contest 169 Participation Report

AtCoder Beginner Contest 169 Participation Report

ABC169A - Multiplication 1

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)

ABC169B - Multiplication 2

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)

ABC169C - Multiplication 3

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))

ABC169D - Div Game

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)

ABC169E - Count Median

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

AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Regular Contest 104 Participation Report
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 177
AtCoder Beginner Contest 172
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 181 Note
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review