[PYTHON] Educational Codeforces Round 92 Bacha Review (7/30)

result

Impressions

** This time, I made a big mistake because the policy was appropriate ** or ** I gave up because I thought it would be difficult **. As a result, I was able to solve 5 questions (although I saw some answers), so I would like to solve them during the actual production.

Also, see @ e869120's this article.

I felt that it was important. I will be careful to implement with these in mind.

Problem A

All of $ x $, $ y $, $ lcm (x, y) $ are in the range of $ l $ or more and $ r $ or less, and ** $ lcm (x, y) $ is the maximum among them ** It becomes. Also, $ lcm (x, y) $ is a multiple of $ x $ and its minimum value is $ 2x $ from the condition that $ x <y $. Therefore, when $ x = l, y = 2l, lcm (x, y) = 2l $, you should check if $ 2l $ is less than $ r $.

A.py

t=int(input())
for _ in range(t):
    l,r=map(int,input().split())
    x,y=l,2*l
    if y<=r:
        print(x,y)
    else:
        print("-1 -1")

Problem B

The order of rock-paper-scissors changes depending on the pos, but ** $ c_1c_2… c_n $ will each play $ n $ times against another hand ($ s_1s_2… s_n $) ** (** Paraphrase of subject and object) **). Therefore, for $ c_i $, you should choose the winning move against $ s_1s_2… s_n $. If there are many, "R" and "P" should be the most, and if there are many, "S" should be used. Also, since it consists of any $ i $, you can output a character string with the length of the number of rock-paper-scissors.

B.py

t=int(input())
for i in range(t):
    S=input()
    l=len(S)
    r=S.count("R")
    s=S.count("S")
    p=S.count("P")
    m=max(r,s,p)
    if m==r:
        print("P"*l)
    elif m==s:
        print("R"*l)
    else:
        print("S"*l)

C Problem

I thought that there shouldn't be any surplus people who misread it, but if you look closely, it says that there may be surplus people. It is a reflection.

In this case, you can combine the programmers with the highest skills in order to exceed ** $ x $. Also, there may be programmer combinations that do not exceed $ x $ even at the end, but you can ignore such combinations.

Also, with this greedy algorithm, ** the smallest number of people can form a group **, so it can be said that the number of groups is the largest.

C.py

t=int(input())
for _ in range(t):
    n,x=map(int,input().split())
    a=sorted(list(map(int,input().split())),reverse=True)
    now=[100000000000,0]
    for i in range(n):
        now=[min(now[0],a[i]),now[1]+1]
        if now[0]*now[1]>=x:
            d.append(now)
            now=[100000000000,0]
    print(len(d))

D Problem

I also misread this and made it difficult to think that ** Berserk can specify two discontinuous people **. Actually, it's not that difficult because there are only two people in a row.

People who are continuous can be defeated, so pay attention to the part where the person who defeats is continuous ** (hereinafter referred to as the continuous part). Also, if you want to defeat the last remaining person in a continuous part with Berserk, one of the non-defeated people ($ L $ and $ R $) who sandwiches that part must have ** more power than that person * * So, we need the information of the person who sandwiches it.

Here, if the length of the continuous part is divided by $ k $ and a remainder appears, it is necessary to reduce the remainder by Berserk, and at this time, the person with the maximum power in the continuous part ($ X $) It is best to select and defeat the people located on both sides of it.

Also, if $ X $ has a higher power than $ L $ and $ R $, you need to ** defeat that $ X $ with Fireball **, and Fireball cannot be used ($ \ leftrightarrow $ length of continuous part). When (is shorter than $ k $) and when the order of the remaining people is different, the subject is not satisfied, so -1 should be output.

At the time of implementation, determine whether $ X $ has higher power than $ L $ and $ R $ → If it is determined, defeat it first with Fireball → Divide the length of the continuous part by $ k $ Defeat the part with Berserk → Repeat the rest with Fireball and Berserk, which is more efficient, and it will be easier.

When I solved it ** I couldn't organize the implementation **, so the code is a bit messy. I also want to be able to pay attention to the cleanliness of the implementation.

D.py

n,m=map(int,input().split())
x,k,y=map(int,input().split())
a=list(map(int,input().split()))
c=list(map(int,input().split()))
b=set(c)
d=[]
now=[]
for i in range(n):
    if a[i] not in b:
        now.append(i)
        if i==n-1:
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
    else:
        if now!=[]:
            #Edge and max index(The edge is-1,n can be)
            d.append([now[0]-1,a.index(max(a[now[0]:now[-1]+1])),now[-1]+1])
            now=[]
#The one whose position is not in order
now=0
lc=len(c)
for i in range(n):
    if a[i]==c[now]:
        now+=1
        if now==lc:
            break
else:
    exit(print(-1))
l=len(d)
ans=0
for i in range(l):
    e=d[i]
    f=e[2]-e[0]-1
    if e[0]==-1:
        m=a[e[2]]
    elif e[2]==n:
        m=a[e[0]]
    else:
        m=max(a[e[0]],a[e[2]])
    if m>a[e[1]]:
        ans+=(f%k*y)
        ans+=min((f//k)*x,(f//k)*k*y)
    else:
        if f<k:exit(print(-1))
        ans+=(f%k*y)
        #I have to defeat them once with k
        ans+=x
        ans+=min((f//k-1)*x,(f//k-1)*k*y)
print(ans)

E Problem

Consider finding $ x + (y-1) d = y + (x-1) d \ (mod \ w) $ under $ 1 \ leqq x, y \ leqq min (d, m) $. Here you can do ** expression transformation ** with $ x + (y-1) d = y + (x-1) d \ leftrightarrow (d-1) (x-y) = 0 $. Therefore, when $ d-1 = 0 \ (mod \ w) $, any $ x, y $ will satisfy this, so if you set $ z = min (d, m) $, then $ \ _ {z } C \ _2 $ It will be as it is.

Here, when ** $ d-1 \ neq 0 \ (mod \ w) $, it seems to be $ x = y \ (mod \ w) $, but this is wrong **. The correct answer is $ x = y \ (mod \ v) $ as $ v = gcd (w, d-1) $ (✳︎).

Therefore, ** $ mod \ v $ is $ 1 $ ~ $ min (d, m) $, and there are several different values **, but ** $ mod \ v $ is hard to think at the beginning of 1. * * So, consider how many ways there are for $ 0 $ ~ $ min (d, m) -1 $.

Also, if you set $ X = [\ frac {min (d, m) -1} {v}], Y = (min (d, m) -1) % v $, then $ 0 $ ~ $ Y \ ( In the case of mod \ v) $, there are $ X + 1 $ ways, so there are $ _ {X + 1} C_2 $ ways to choose $ x and y $ respectively. Also, when $ Y + 1 $ ~ $ v-1 \ (mod \ v) $, there are $ X $ streets, so how to choose $ x and y $ is $ \ _ {X} C \ _2 $ respectively. It will be a street.

Therefore, from the above, how to select the total $ x, y $ is $ \ _ {X + 1} C_2 \ times (Y + 1)-\ _ {X} C \ _2 \ times Y $, and this is output. Just do it.

E.py

t=int(input())
from math import gcd
for _ in range(t):
    m,d,w=map(int,input().split())
    z=min(d,m)
    d-=1
    if d%w==0:
        print(z*(z-1)//2)
        continue
    w//=gcd(d,w)
    z-=1
    x=z//w
    y=z%w+1
    print(x*(x-1)//2*(w-y)+(x+1)*x//2*y)

After the F problem

I can't solve this time.