[PYTHON] Yukicoder-Wettbewerb 271 Teilnehmerrekord

Yukicoder-Wettbewerb 271 Teilnehmerrekord

A 1264 010

010 kann einmalig mit 010 → 101, 0100 zweimal mit 0100 → 1010 → 1101 und 01000 dreimal mit 01000 → 10100 → 11010 → 11101 betrieben werden.

N = int(input())

print('01' + '0' * N)

B 1265 Balloon Survival

Da N ≤ 1000 ist, kann * O * ( N </ i> 2 </ sup> log N </ i>) in letzter Minute verwaltet werden. Sie können das Verschwinden nebeneinander simulieren. Notieren Sie die bereits verschwundenen Ballons und überspringen Sie sie, wenn sie kollidieren. Die Anzahl der Ballons, die mit dem ersten Ballon kollidieren, ist die Antwort.

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

a = []
for i in range(N - 1):
    for j in range(i + 1, N):
        d = (xy[i][0] - xy[j][0]) * (xy[i][0] - xy[j][0]) + (xy[i][1] - xy[j][1]) * (xy[i][1] - xy[j][1])
        a.append((d, i, j))
a.sort()

result = 0
t = set()
for _, i, j in a:
    if i in t or j in t:
        continue
    if i == 0:
        result += 1
        t.add(j)
    else:
        t.add(i)
        t.add(j)
print(result)

Recommended Posts