This time's results

Impressions of this time

I made a mistake that I couldn't solve the C problem. The subject could not be read accurately. ** If you have a problem, check the movement with a sample **.

It seems that many people have investigated and solved the F problem. I think it's an interesting problem, but since I knew how to solve it, I'll try to solve it when I forget it. ** There are quite a few problems that make it easy to find one in the section **, but it's easy to forget, so I want to make sure that I can solve it next time.

Problem A

You just have to check if it is over 30 degrees.

`A.py`


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

B problem

Just find the distance. Also, I'm worried that the route will be a decimal number this time, so I squared it (it seems that it is okay to calculate the route as it is in this problem).

`B.py`


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

C problem

A multiple of ** $ K $ can be rephrased as 0 ** with the remainder divided by $ K $. Also, if the $ i $ th of $ 7,77,777,… $ is $ a_i $, then $ a_ {i + 1} = 10 \ times a_i + 7 $. Therefore, if the remainders of $ a_j and a_l $ are the same, the remainders of $ a_ {j + 1} and a_ {l + 1} $ will also be the same. Therefore, there is something that suffers from the remainder divided by ** $ K $ up to $ a_ {K + 1} $ **, so if you search for $ a_1 $ ~ $ a_k $, the remainder divided by $ K $ will be You can search for 0's. On the contrary, if 0 does not come out up to that point, there is nothing that the remainder after dividing by $ K $ becomes 0.

For this problem, you can solve the problem by paying attention to the remainder of ** $ K $ if you notice that the multiple of ** $ K $ is the remainder of dividing by $ K $ is 0 **. Also, since it is included in the basics of ** simulating for the time being when solving a problem **, I realized again the importance of thoroughly implementing the basics.

`C.py`


k=int(input())
now=7%k
if now==0:
    print(1)
    exit()
for i in range(1,k):
    now=10*now+7
    now%=k
    if now==0:
        print(i+1)
        break
else:
    print(-1)

D problem

It is easy to see that the final sequence is "red-red ... red-red / white-white ... white-white". First, in order to ** greedily change the given row of stones **, we will change it from left to red.

At this time, it is not necessary to change Akaishi, so consider ** only for Shiroishi **. At this time, I think about changing the white stone to red stone, but if you replace the stone with the red stone on the right side of the stone rather than repainting it, you can change the color of the two stones at the same time, which is efficient. is. In addition, you can see that ** replace with the rightmost red stone ** is appropriate to replace with red stone so that the number of replacements is reduced (← For example, ** Extreme case ** (next to). I think it is easy to understand considering that it is inefficient (when replacing it with Akaishi). If you can create a situation where there is no red stone on the right side while repeating this, the number of operations at that time will be the minimum number of operations.

`D.py`


from collections import deque
n=int(input())
c=input()
r=deque()
lr=0
for i in range(n):
    if c[i]=="R":
        lr+=1
        r.append(i)
ans=0
for i in range(n):
    if lr==0:
        break
    if c[i]=="W":
        if i<r[-1]:
            ans+=1
            r.pop()
            lr-=1
        else:
            break

print(ans)

E problem

You can think of a binary search by combining the number of times a log is cut (the number of times), the minimum (the range of numbers is large), and ** the longer the log, the fewer times it is cut ** (monotonicity).

Here, ** in a binary search, it is necessary to consider a condition that always holds for the minimum (or maximum) or more **, but here, "at least necessary to make the longest length (round up) less than $ x $". The condition is that the number of times a log is cut is $ K $ or less, and the total of ceil (a [i] / x) -1 calculated for each log is $ K $ or less. If it is good.

Also note that for l, r, ** $ l $ is always set to a value that does not always hold **, ** $ r $ is set to a value that does not always hold **.

If you pay attention to these, you can reach the correct answer by implementing according to this article.

`E.py`


n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
    global a,n,k
    if x==0:
        return 10**10
    ret=0
    for i in range(n):
        ret+=(-((-a[i])//x)-1)
    return ret

l,r=0,10**10
while l+1<r:
    x=l+(r-l)//2
    if f(x)<=k:
        r=x
    else:
        l=x

print(r)

F problem

I will not solve this time.

[PYTHON] AtCoder Beginner Contest 174 Review