[PYTHON] AtCoderBeginnerContest174 Review & Summary (first half)

AtCoder ABC174 This is a summary of the problems of AtCoder Beginner Contest 174, which was held on 2020-08-02 (Sun), in order from problem A, taking into consideration the consideration. The first half deals with problems up to ABC. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

Problem A Air Conditioner

Problem statement You turn on the air conditioner only when and only when the room temperature is above $ 30 $. The current room temperature is $ X $ degrees. Do you want to turn on the air conditioner? Output Output'Yes' if you turn on the air conditioner, and'No' if you don't.

abc174a.py

x = int(input())
if x >= 30:
    print("Yes")
else:
    print("No")

Problem B Distance

Problem statement There are $ N $ points on the $ 2 $ dimensional plane. The coordinates of the $ i $ th point are $ (X_i, Y_i) $. How many of these points have a distance of less than $ D $ from the origin? The distance between the point at the coordinate $ (p, q) $ and the origin is represented by $ \ sqrt {p ^ 2 + q ^ 2} $.

I don't like the error in the calculation of the square root, so I used $ p ^ 2 + q ^ 2 \ leqq D ^ 2 $, which is the square of both sides of $ \ sqrt {p ^ 2 + q ^ 2} \ leqq D $. Judgment was made.

abc174b.py

n, d = map(int, input().split())
d = d * d
count = 0
for i in range(n):
    x, y = map(int, input().split())
    if x * x + y * y <= d:
        count+= 1
print(count)

C problem Repept

Problem statement Takahashi likes multiples of $ K $ and $ 7 $. What is the first multiple of $ K $ to appear in the $ 7,77,777,… $ sequence? If it does not exist, output'-1' instead.

I had a hard time. I quickly realized that there were no multiples of $ 5 $ and $ 2 $, but I personally found it difficult. I've spent a lot of time investigating the properties of the repunit. My personal interpretation is that the sequence $ 7,77,777,… $ has the first term $ a_1 = 7 $. a_{n+1}=10a_n+7 It can be expressed as. This can be solved by considering the sequence in $ mod K $. For example, when $ K = 9 $ The remainder of the $ 7,77,777,… $ sequence divided by $ 9 $ is $ 7,5,3,1,8,6,4,2,0,7,… $, and the $ 9 $ item is a multiple of $ 9 $. It can be seen that it is. Let this sequence be $ b_n $. For example, focusing on the $ 3 $ item, the remainder of dividing $ 777 $ by $ 9 $ can be calculated by $ b_3 \ equiv 10b_2 + 7 (mod 9) $, so if there is a multiple of $ K $, it will be the first time. Since it appears at least once from the term to the $ K $ item (because the remainder divided by $ K $ is $ 0 \ leqq x \ leqq K-1 $), the remainder is $ 0 $ in that range. If it appears, it outputs, and if it does not appear, it outputs'-1'. In the implementation, from $ b_ {n + 1} \ equiv 10b_n + 7 (mod K) $, if $ K $ is a multiple of $ 5 $ or a multiple of $ 2 $, it will be $ b_n \ equiv 7 (mod K) $. Therefore, we divided the cases there, and implemented it so that the loop would be repeated until an answer was given because it always exists in other cases.

abc174c.py

k = int(input())
if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    c = 7
    count = 1
    while True:
        if c % k == 0:
            print(count)
            break
        else:
            c = (10 * c + 7) % k
            count += 1

This is the end of the first half. Recently, the official commentary has been described very carefully, so I hope you can refer to that for the detailed solution. Thank you for reading to the end of the first half.

The second half will explain the DEF problem. Continued in the second half.