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 image.png

Answer

X = int(input())

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

Just write this.

B. Distance image.png

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 image.png

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 image.png

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 image.png

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

Recommended Posts

AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
atCoder 173 Python
AtCoder ABC176
AtCoder ABC177
AtCoder ABC 177 Python (A ~ E)
Solve AtCoder ABC166 with python
AtCoder ABC 178 Python (A ~ E)
Atcoder ABC164 A-C in Python
AtCoder ABC 176 Python (A ~ E)
Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
AtCoder ABC 182 Python (A ~ D)
Solve AtCoder ABC 186 with Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
Beginner ABC154 (Python)
Beginner ABC156 (Python)
Solve Atcoder ABC169 A-D in Python
Beginner ABC155 (Python)
Solved AtCoder ABC 114 C-755 with Python3
Template AtCoder ABC 179 Python (A ~ E)
Beginner ABC157 (Python)
Python beginner Atcoder memo @ KEYENCE 2020, ABC problem
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
Daily AtCoder # 36 in Python
Daily AtCoder # 2 in Python
Daily AtCoder # 32 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 7 in Python
Daily AtCoder # 24 in Python
Daily AtCoder # 37 in Python
Solve AtCoder 167 with python
Daily AtCoder # 8 in Python
Daily AtCoder # 42 in Python
Daily AtCoder # 17 in Python
Daily AtCoder # 54 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
Daily AtCoder # 30 in Python
Daily AtCoder # 40 in Python
Daily AtCoder # 10 in Python
Daily AtCoder # 5 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 39 in Python
Automate AtCoder submission (Python)
Atcoder ABC115 Past Exercises
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python