[PYTHON] Educational Codeforces Round 86 Bacha Review (9/17)
This time's results
Impressions of this time
I was impatient as usual this time, but I was able to switch and pass D at the last minute, so it is a good point. After all, when the problem is impatient, the problem is not organized and ** the notes tend to be cluttered **, so ** write as cleanly as possible ** and ** if you really do not understand I would like to make a clean copy **.
Problem A
I think there was a similar problem in ABC before.
The signs of $ x and y $ are the same, and $ x <y $. At this time, it is best to reduce all of them monotonously, and since the operation of ** ② will move at the same time **, reduce $ y $ to $ x $ by the operation of ①. Furthermore, since $ y = x $, you can select the most suitable operation for operations ① and ②, and the minimum value to be obtained is $ (yx) \ times a + min (x \ times b, 2 \ times x \ times a) $. It becomes.
A.py
for _ in range(int(input())):
x,y=map(int,input().split())
a,b=map(int,input().split())
if x>y:
x,y=y,x
print((y-x)*a+min(x*b,2*x*a))
Problem B
Recently, I feel that it has become possible to pass through problems related to the construction of Kodofo at high speed. I'd be happy if you could come out with ABC (I'm very disappointed because it was the case with ABC-F last time ...).
First of all, I thought that ** the cycle could be made quite small **. This is because if you can create a string that is $ 0101… $ or $ 1010… $, the period will be 2. Consideration based on this policy is as follows.
First,
B.py
for _ in range(int(input())):
t=input()
if all(i=="0" for i in t) or all(i=="1" for i in t):
print(t)
else:
print(len(t)*"01")
C problem
When I made the initial policy, I was impatient because I made a mistake in ** $ i, j $ that I wrote **, and I couldn't reach the correct answer. Also, after that, despite the typical problem **, I tried to solve it analytically **.
First of all, it is obvious that the calculation in the query will not be in time, so ** pre-calculate **. At this time, if you write out all possible numbers, it will be $ 10 ^ 9 $ **, so it is obviously not in time.
So, paying attention to $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a $, $ i = x \ mod \ a, j = x \ mod \ b $ If you know the above formula, you can think of the above formula, so I thought about $ ab $ combination of $ i, j $, but ** If you have the image of the Chinese Remainder Theorem, you only need to know the remainder of $ ab $ ** understood. This can be $ x = ab + k (0 \ leqq k <ab) $, then $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a \ leftrightarrow (x \ mod \ a) It can be said from the fact that it becomes k \ mod \ a) \ mod \ b \ neq (k \ mod \ b) \ mod \ a $.
Therefore, as a pre-calculation, $ pre [i]: = $ ($ (i \ mod \ a) \ mod \ b \ neq (i \ mod ) when the remainder divided by $ ab $ is $ 0 $ ~ $ i $ b) Find (the number of \ mod \ a $) (the cumulative sum is used because it will be needed later).
Also, in the query, find the number of $ i \ in [l, r] $ that is $ (i \ mod \ a) \ mod \ b \ neq (i \ mod \ b) \ mod \ a $. Is calculated by subtracting the number in $ i \ in [0, l-1] $ from the number in ** $ i \ in [0, r] $ **. Also, if the number in $ i \ in [0, x] $ is $ f (x) $, it can be calculated by $ f (r) -f (l-1) $.
Consider finding $ f (x) $ using pre-calculation based on this, but the number whose remainder after dividing by ** $ ab $ is $ 0 $ ~ $ ab-1 $ is looped in order from 0. Consider ** and the number of loops, $ f (x) = [\ frac {x} {a \ times b}] \ times pre [ab-1] + pre [x \ mod \ ( It can be calculated as a \ times b)] $.
Therefore, each query is calculated by $ O (1) $, so you can open a program that is enough for $ O (t \ times (a \ times b + q)) $ as a whole.
C.py
from itertools import accumulate
def f(i):
global a,b,pre
x=i//(a*b)
y=i%(a*b)
return x*pre[-1]+pre[y]
for _ in range(int(input())):
a,b,q=map(int,input().split())
pre=[int((i%a)%b!=(i%b)%a) for i in range(a*b)]
pre=list(accumulate(pre))
ans=[]
for i in range(q):
l,r=map(int,input().split())
ans.append(str(f(r)-f(l-1)))
#print(f(r),f(l-1))
print(" ".join(map(str,ans)))
D problem
Personally, it was a more intuitive and easier-to-solve problem than the C problem. It may be quite effective to change the problem to be solved after it gets stuck for about 30 minutes. However, the question sentence was a little difficult to read.
(Hereafter, let's assume that the array given for distribution to the test cases is $ m $. These are ** descending sorted **.)
Each test case is a collection of several arrays of a certain length (← I'm only interested in length, so ** interpret it as a collection of several numbers ** and solve the problem below). In addition, test cases in which the number of test cases is distributed so that the number of test cases is reduced while satisfying the condition that $ i $ is contained in less than $ c \ _i $ in each test case **. Consider the number of. It also fills $ n \ geqq c \ _1 \ geqq c \ _2 \ geqq… \ geqq c \ _k \ geqq 1 $, ensuring that the minimum number of test cases exists.
Here, I decided to greedily decide which test case to include in order from the number with the larger constraint **. It can also be said that ** when a certain number is decided, the constraints after that are always satisfied **.
First, prepare an array $ ans $ that manages the entire test case (each test case contains multiple elements). In addition, let the length of $ ans $ be $ l $ and the index you are looking at in the $ ans $ test case be $ now $. Then add $ [m [0]] $ to $ ans $ as the first test case and initialize $ now $ with 0 and $ l $ with 1.
Based on this, add $ m [1],…, m [n-1] $ to the test case in this order. When you are looking at $ m [i] $, when $ m [i-1]> m [i] $, $ c [m [i] -1]> c [m [i-1]- It can be 1] $. In this case, update ** $ now $ to 0 ** and substitute $ m [i] $ for $ ans [now] $. Also, this judgment is $ len (ans [0]) \ <c [m [i] -1] $ or $ c [m [i-1] -1] \ <c [m [i] -1] $ Can be done by
Next, when $ c [m [i] -1] = c [m [i-1] -1] $, there is a possibility that it can be added after the element seen in ** $ now $ **, so $ now + = 1 $ until an element that becomes $ len (ans [now]) \ <c [m [i] -1] $ is found, and if found, add it to $ ans [now] $. Also, if it is not found, there are not enough test cases, so add $ [m [i]] $ to $ ans $.
By repeating this, you can greedily decide to reduce the number of test cases as much as possible. After that, you can output the final test case according to the instruction of the problem.
It is difficult to explain the above in words, but I feel that the implementation can be done smoothly as long as the legitimacy of the greedy algorithm is understood.
D.py
n,k=map(int,input().split())
m=sorted(list(map(int,input().split())),reverse=True)
c=list(map(int,input().split()))
ans=[[m[0]]]
#ans length
l=1
#Which ans array can be put in(Watch out for updates)(As if vacant)
now=0
for i in range(1,n):
if len(ans[0])<c[m[i]-1]:
now=0
ans[now].append(m[i])
else:
while now!=l:
if len(ans[now])<c[m[i]-1]:
break
now+=1
if now==l:
ans.append([m[i]])
l+=1
else:
ans[now].append(m[i])
print(len(ans))
for i in range(len(ans)):
print(len(ans[i]),end=" ")
print(" ".join(map(str,ans[i])))
After the E problem
I will skip this time
Recommended Posts