AtCoder ABC 174 Python

Summary

Only A and B were AC. It seems that C and D will be solved soon, but it is difficult to solve.

problem

https://atcoder.jp/contests/abc174/tasks

A. Air Conditioner

Answer

X = int(input())

if X >= 30:
    print('Yes')
else:
    print('No')

Just write this.

B. Distance

Answer

N, D = map(int, input().split())
count = 0
for _ in range(N):
    x, y = map(int, input().split())
    distance = (x ** 2 + y ** 2)**0.5

    if distance <= D:
        count += 1

print(count)

This is also just written according to the problem statement, but it seems better to compare the squares of the distances than to judge by the distance by the route.

C. Repsept

Answer (at the time of the contest)

K = int(input())
   
answer = -1
target = 0
for i in range(K):
    target += 7 * 10**i
    if target % K == 0:
        answer = i + 1
        print(answer)
        break

print(answer)

Of course, if you implement it according to the problem statement, it will not pass. `` `999983``` in input example 3 is the maximum value of the problem, but if you try to solve this, you have to calculate 10 to the 999983 power, which is obviously impossible.

Answer (at a later date)

K = int(input())
count = 1
mod = 7
answer = -1

for _ in range(K):
    if mod % K == 0:
        answer = count
        break
    count += 1
    mod = (mod * 10 + 7) % K

print(answer)

Consider reducing the power of 10.

The problem is that you don't need to keep `7,777,777 ....` because you only need to know the first number that is divisible by the number ``` 7,777,777 .... . If you keep it, it will be solved.

In other words, instead of target + = 7 * 10 ** i, you should repeat `` `mod = (mod * 10 + 7)% K``` K times.

At this point, all you have to do is write.

D. Alter Altar

Answer (at the time of the contest)

N = int(input())
stones = input()
count_R = stones.count('R')

if N == count_R:
    answer = 0
elif N - count_R > count_R:
    answer = count_R
else:
    if 'R' in list(stones)[:N//2]:
        answer = count_R - 1
    else:
        answer = count_R

print(answer)

This cannot be solved. I thought too hard and the conditional branch was messed up. According to this policy, there are not enough conditional branches.

Answer (at a later date)

N = int(input())
stones = input()

total_count_R = stones.count('R')
left_count_R = stones[:total_count_R].count('R')

answer = total_count_R - left_count_R

print(answer)

Later, I found that it melts simply when I think about it with a clean head.

wr All you have to do is to eliminate the lineup, so in the end, allrYou can see that you should operate so that are gathered on the left side.

The number of operations in which all `R```s are gathered on the left side can be found by experimenting with the following. --From total_count_R```, which is the number of all `` R`` --Subtract ``left_count_R, which is the number of `` `R contained from left to `` `total_count_R```

Once you know this, the code can be written fairly simply.

E. Logs

Answer (at the time of the contest)

import heapq

N, K = map(int, input().split())
K_copy = K
A = list(map(int, input().split()))
A = list(map(lambda x: x*-1, A))
heapq.heapify(A)

while K:
    max1 = heapq.heappop(A)
    max2 = heapq.heappop(A)

    for i in range(2, K_copy+1):
        temp = max1 / i
        if temp > max2:
            heapq.heappush(A, temp)
            heapq.heappush(A, max2)
            K -= 1
            break

print(A)

This will not pass. The policy is to "continue to cut the longest log in half", but with this, for example, if you cut the same log twice, you should cut it in three equal parts, but halfway cut It will be the one.

You can also improve it a little and "find the longest log and cut it again with the best cutting method", but this seems to be difficult to implement, and maybe `` `TLE``` I gave up because it would be.

Answer (at a later date)

N, K = map(int, input().split())
A = list(map(int, input().split()))

def check(l):
    count = 0
    for L in A:
        count += L // l
        if L % l != 0:
            count += 1
        count -= 1
    return count <= K
        
bottom, top = 0, max(A)

while top - bottom > 1:
    mid = (top + bottom) // 2
    if check(mid):
        top = mid
    else:
        bottom = mid

print(top)

Think in reverse, "cut the log K times to minimize it." "Can you do it within K times to make the log a certain length (minimum)?"

In a 2-minute search, go to find "the right place to minimize the length of the log", At that time, `def check ()` is used to judge "whether it can be done within K times".

** For the E problem, I referred to Katsuppa's YouTube. ** ** https://youtu.be/0jwtdtinPiE