yukicoder contest 271 Participation record

yukicoder contest 271 Participation record

A 1264 010

010 can be operated once with 010 → 101, 0100 can be operated twice with 0100 → 1010 → 1101, and 01000 can be operated 3 times with 01000 → 10100 → 11010 → 11101.

N = int(input())

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

B 1265 Balloon Survival

Since N ≤ 1000, * O * ( N </ i> 2 </ sup> log N </ i>) can be managed at the last minute, so put out the distances of all combinations and start from the smallest. You can simulate the disappearance side by side. Record the balloons that have already disappeared and skip them when they collide. The number of balloons that collide with the first balloon is the answer.

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