AtCoder Beginner Contest 168 Participation Report

AtCoder Beginner Contest 168 Participation Report

It's the first time I've cut 700, so I don't like it !!

ABC168A - ∴ (Therefore)

Break through in 2 minutes. Just write.

N = int(input())

if N % 10 in [2, 4, 5, 7, 9]:
    print('hon')
elif N % 10 in [0, 1, 6, 8]:
    print('pon')
elif N % 10 in [3]:
    print('bon')

ABC168B - ... (Triple Dots)

Break through in 2 minutes. Just write.

K = int(input())
S = input()

if len(S) <= K:
    print(S)
else:
    print(S[:K] + '...')

ABC168C - : (Colon)

Break through in 9 and a half minutes. There is a fool who forgets to move the hour hand even in minutes. I am not good at math, but I can manage at this level.

from math import pi, sin, cos, sqrt

A, B, H, M = map(int, input().split())

x1 = A * cos(2 * pi * (H + M / 60) / 12)
y1 = A * sin(2 * pi * (H + M / 60) / 12)
x2 = B * cos(2 * pi * M / 60)
y2 = B * sin(2 * pi * M / 60)

print(sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)))

ABC168D - .. (Double Dots)

It broke through in 9 and a half minutes. The problem was that it was easy to do a breadth-first search from the entrance, but it was hard to submit with a strong heart that there was no case of'No'.

from collections import deque

N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]

links = [[] for _ in range(N + 1)]
for a, b in AB:
    links[a].append(b)
    links[b].append(a)

result = [-1] * (N + 1)
q = deque([1])
while q:
    i = q.popleft()
    for j in links[i]:
        if result[j] == -1:
            result[j] = i
            q.append(j)
print('Yes')
print('\n'.join(str(i) for i in result[2:]))

ABC168E - ∙ (Bullet)

I couldn't solve it because it seemed to be solvable. Maybe the case where either A i </ sub> or B i </ sub> is 0 is not complete.

Addendum: (A i </ sub>, B i </ sub>) = (0, 0) was treated incorrectly. (0, 0) is close to all fish It was so bad that I had to add it later.

I understand that b / a and -a / b are not on good terms, but unfortunately Python has no rational numbers, so I substitute the tuple of (a, b). By the way, (1, 2) and (-4, 2) I don't get along well, but I don't know it at all, so divide each of a and b by gcd (a, b) and divide them. This gives (1, 2) and (-2, 1), so ( Only (-b, a), (b, -a) have a bad relationship with a, b). Also, (-b, a), (b, -a) are both (-a, -b). Since we are not on good terms, (a, b) and (-a, -b) are groups. After that, for each (a, b) that exists, the number of cases is 2 ^ (the number of (a, b) + ( -A, -b) number) + 2 ^ ((-b, a) number + (b, -a) number) -1 (there is no last -1 but it is duplicated), so multiply Then, add the number of (0, 0) at the end, and subtract one by the amount that you did not select, and you will get the answer.

The theory is simple, but the implementation is high in calories and annoying ...

from math import gcd

N = int(input())
AB = [map(int, input().split()) for _ in range(N)]

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)

Recommended Posts

AtCoder Beginner Contest 181 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 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 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
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 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 167 Review
AtCoder Library Practice Contest Participation Report (Python)