[PYTHON] Codeforces Round # 638 (Div. 2) Bacha Review (9/16)

This time's results

Impressions of this time

I couldn't solve the problem because I had something to do while considering the problem. I'm disappointed because it would have been solved if it hadn't been included.

Also, although the C problem could be roughly divided into cases, it did not pass, so I wrote it after reorganizing it, and I was able to AC **. I think we made a good switch. However, I couldn't switch the D problem halfway, so I want to ** handle the problem consistently **.

Problem A

Since $ 2 ^ + 2 ^ 2 +… + 2 ^ {n-1} <2 ^ n $, the sum of the ones containing $ 2 ^ n $ should be minimized. Therefore, the absolute value of the difference to be obtained is $ (2 ^ 1 + 2 ^ 2 +… + 2 ^ {\ frac {n} {2} -1} + 2 ^ n)-(2 ^ {\ frac {n} {2}} + 2 ^ {\ frac {n} {2} + 1} +… + 2 ^ {n-1}) The difference is $.

A.py

for _ in range(int(input())):
    n=int(input())
    a=2**n+sum(2**i for i in range(1,n//2))
    b=sum(2**i for i in range(n//2,n))
    print(a-b)

Problem B

I had a problem with the same theme in recent ABC. When paying attention to consecutive $ k $ pieces, consider ** the difference when sliding one by one **. In this problem, the sums are equal, so the final sequence of $ k $ separated elements is equal **.

Also, the fact that the parts separated by $ k $ are equal is equivalent to the fact that a period of ** length $ k $ appears in the string **. If this cycle cannot include any number that appears in the original sequence, then there is no sequence that meets the subject. Therefore, if (the type of number that appears in the sequence) $> k $, the sequence that satisfies the theme cannot be created and -1 is output.

Based on this, consider a ** convenient sequence ** that satisfies the subject. At this time, it should be noted that the positional relationship of the numbers in the original sequence does not change ** because only the insert operation is performed. Therefore, it can be implemented by setting the cycle to ** an appropriate sequence using any character that appears ** and checking whether it appears in order while looking at the original sequence. However, this time, as a more convenient array, I considered ** a sequence in which each element appears once in each cycle **. In other words, if you repeat $ n $ times with the same cycle as before, you can create a sequence that satisfies the subject without checking.

B.py

from collections import deque
for _ in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    if len(set(a))>k:
        print(-1)
        continue
    ans=[]
    for i in set(a):
        ans.append(str(i))
    for i in range(k-len(set(a))):
        ans.append(str(a[i]))
    realans=[]
    for i in range(n):
        realans+=ans
    print(len(realans))
    print(" ".join(realans))

C Problem

It is a problem to step on the corner case if you do not calm down. However, the sample is kind enough to get you to the correct answer.

At first, I thought that it would be better to divide it as evenly as possible **, but I realized that if there are several types of characters, it is better to concatenate them in the same string **. Also, if the first character has a different character, only one character of that different character is output. These considerations could be obtained experimentally, but it is important to ** generalize the case-by-case axis ** when raising it for implementation. Here, we focus on the ** number of character types ** and ** the first character **, and classify them as follows.

(1) When there is only one type of character Sort the characters as evenly as possible and then output the longest string.

(2) When a different character appears at the beginning Only one of the largest characters that appears first is output.

(The following is the case where the first characters are all the same but there are two or more types of characters)

(3) When there are three or more types of characters After the second character, all the remaining characters can be concatenated into one character string. I think it's best to think of it as having large letters in the dictionary order as far back as possible.

(4) When there are two types of characters If the smaller character in the dictionary order is exactly $ k $, the rest will be sorted as evenly as possible and then the longest character string will be output. If it is not $ k $, you can concatenate all the remaining characters in one string.

Regarding (✳︎) (3) and (4), I think it is more rational to consider ** the case where there are two or more types of characters after the second character **. During the contest, I couldn't think so organized.

C.py

from collections import Counter
for _ in range(int(input())):
    n,k=map(int,input().split())
    s=sorted(input())
    t=list(Counter(s).items())
    if len(t)==1:
        print(s[0]*(-(-n//k)))
        continue
    now=s[0]
    ans=s[k-1]
    if now!=ans:
        print("".join(ans))
    elif len(t)>=3:
        print("".join(s[k-1:]))
    elif t[0][1]==k:
        print(t[0][0]+t[1][0]*(-(-n//k)-1))
    else:
        print("".join(s[k-1:]))

D Problem

(In the following, all = are put in the inequality sign. There are some mathematical differences, but please forgive me.)

At first glance, it's a difficult problem to tackle, but once you get the essence, it's not that difficult. First of all, regarding the slime splitting operation, the slime whose mass should be $ m \ _i + 1 $ that night by splitting is $ (\ frac {m \ _ i} {2} + 1) + (\ frac Since it becomes {m \ _i} {2} + 1) $, it is easy to understand that it is ** an operation that increases the mass by +1 **. In addition, the number of slimes to be selected when dividing is free, and any mass can be expressed without dividing it even once, so it is necessary to proceed with consideration from the standpoint that there is no mass that cannot be expressed. Here, in order to increase the mass as much as possible, it is best to ** select and divide all the existing slime **, but ** you can not just adjust the mass to $ n $ unless you adjust it by the last operation. **I understand this.

Under this, the number of bacteria in the morning of $ i $ is $ a \ _i $, and the total weight of bacteria in the morning of $ i $ is $ b \ _i $, $ i $. Assuming that the number of bacteria to be selected is $ x \ _i $, the following recurrence formula holds.

a\_{i+1}=a\_i+x\_i b\_{i+1}=b\_i+a\_{i+1}

Here, what we want to finally find is the number of days required for $ b \ _i $ to become $ n $, but from ** $ n $, subtract $ a \ _i $ in order to make it 0 **. It seems better to think about it. Here, it can be $ a \ _i \ leqq a \ _ {i + 1} \ leqq 2 a \ _i $, so it is good if $ a \ _i \ leqq n \ leqq 2 a \ _i $ is satisfied on the last day. is. Also, if $ n> 2a \ _i $, I would like to divide it so that $ a \ _ {i + 1} = 2 a \ _i $ as much as possible, but ** one day before the last day ** $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow 2 a \ _i \ leqq a \ _ {i + 2} \ leqq 4 a From \ _i $ $ 2 a \ _i \ leqq na \ _ {i + 1} \ leqq 4 a \ _i \ leftrightarrow 4a \ _i \ leqq n \ leqq 6 a \ _i $ must be satisfied. So if $ 2a \ _i <n <4a \ _i $, you have to choose $ x \ _i $, which is less than ** $ a \ _ {i} $, and just ** to $ n $ on the next final day. Must be.

For example, if $ x \ i = 0 $, then $ a {i + 1} = a \ _i $, so $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ leftrightarrow a \ _i \ leqq a \ _ {i + 2} \ leqq 2 a \ _ i $ from $ a \ _i \ leqq na \ _ {i + 1} \ leqq 2 a \ _i It is time to fill \ leftrightarrow 2a \ _i \ leqq n \ leqq 3 a \ _i $.

What remains is when $ 3a \ _i <n <4a \ _i $, but for example, if $ x \ _i = [\ frac {a \ i} {2}] $, then $ a {i + 1} = a \ _ i + [\ frac {a \ _ i} {2}] $, so $ a \ _ {i + 1} \ leqq a \ _ {i + 2} \ leqq 2 a \ _ {i + 1} \ From leftrightarrow a \ _i + [\ frac {a \ _ i} {2}] \ leqq a \ _ {i + 2} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _ i} {2}] $ $ a \ _i + [\ frac {a \ _i} {2}] \ leqq na \ _ {i + 1} \ leqq 2 a \ _i +2 \ times [\ frac {a \ _i} {2}] \ leftrightarrow 2a \ _i + 2 [\ frac {a \ _i} {2}] \ leqq n \ leqq 3a \ _i + 3 [\ frac {a \ _ i} {2}] $ must be satisfied. Since this includes the time of $ 3a \ _i <n <4a \ _i $, it is also shown when $ 3a \ _i <n <4a \ _i $.

From the above, $ x \ _i = na \ _i $, $ n \ leqq 3a \ _i $ for $ n \ leqq 2a \ _i $, $ x \ _ i = 0 $, $ n <4a \ _i $ If $ x \ _i = [\ frac {a \ _ i} {2}] $, $ n \ geqq 4a \ _i $, then $ x \ _i = a \ _i $ and give in the minimum number of days It is possible to produce bacteria with the total mass obtained.

D.py

for _ in range(int(input())):
    n=int(input())
    ans=[]
    ai=1
    n-=1
    xi=0
    while True:
        if n<=2*ai:
            xi=n-ai
            ai=ai+xi
            n-=ai
            ans.append(xi)
            break
        elif n<=3*ai:
            xi=0
            ai=ai+xi
            n-=ai
            ans.append(xi)
        elif n<4*ai:
            xi=ai//2
            ai=ai+xi
            n-=ai
            ans.append(xi)
        else:
            xi=ai
            ai=ai+xi
            n-=ai
            ans.append(xi)
            #print(2)
        #print(ai,xi,n)
    print(len(ans))
    print(" ".join(map(str,ans)))

After the E problem

I will skip this time