Educational Codeforces Round 90 Bacha Review (8/19)
This time's results
Impressions of this time
I thought it would be impossible even if I knew the direction of the idea, so I gave up. I'm not sure if I give up and drop it, so in this case I would like to take a deep breath and then proceed with consideration **. Even when I'm in a hurry, I want to calm down and understand ** what is difficult and what I want to improve **.
Problem A
If you want to make the first donut cheaper than the second donut, it's best to buy only one first donut and one set of second donuts. At this time, if $ a <c $, it can be cheaper, so 1 is the answer. Also, when it is $ a \ geqq c $, it cannot be cheaper by any purchase, so -1 is the answer.
If you want to make the second donut cheaper than the first donut, it's best to buy only $ b $ for the first donut and only one set for the second donut. At this time, if $ c <a \ times b $, it can be cheaper, so $ b $ is the answer. Also, $ c \ geqq a \ times b $ time cannot be cheaper by any purchase, so -1 is the answer.
A.py
for _ in range(int(input())):
a,b,c=map(int,input().split())
ans=[]
if a<c:
ans.append(1)
else:
ans.append(-1)
if a*b>c:
ans.append(b)
else:
ans.append(-1)
print(" ".join(map(str,ans)))
Problem B
I think it's a common problem setting. Select and delete adjacent ones with 0 and 1, and the player loses when it is not operable. ** If both 0 and 1 are included in the string, there are 0s and 1s adjacent to each other **, so the final remaining string (which may be an empty string) is either 0 or 1. Only remains. Therefore, the number of times you can select adjacent 0s and 1s is the smallest of the included 0s and 1s. Therefore, if this number is odd, it will be the first victory, and if it is even, it will be the second victory.
B.py
for _ in range(int(input())):
s=input()
print(["NET","DA"][min(s.count("1"),s.count("0"))%2])
C problem
It was difficult to read because the problem statement was pseudo code. Did the Writer person skip it?
When looking at the character string, the variable cur changes as -1 for "-" and +1 for "+". The initial value of cur when scanning a character string is init, and it increases in order from 0.
For such problems, ** experiment and grasp the behavior ** to improve the outlook. Therefore, if you experiment with the first sample -+-, it will be as follows.
When the above experiment is verbalized, when considering the cumulative sum in order from the left, it scans until ** where the minimum value update occurs ** (set to 0 at the beginning), and returns to the beginning if it is updated. Repeating the above, if you check all the places where the update occurs, ** scan all the elements at the end ** to finish the scan.
In other words, the answer is to find the sum of the updated indexes (1-indexed) while saving the minimum value while looking at the cumulative sum in order from the front, and add the length of the character string as the final scan.
C.py
from itertools import accumulate
for _ in range(int(input())):
s=input()
l=len(s)
t=[1 if s[i]=="+" else -1 for i in range(l)]
t=list(accumulate(t))
now=0
ans=0
for i in range(l):
if t[i]<now:
ans+=(i+1)
now=t[i]
if i==l-1:
ans+=(i+1)
print(ans)
D problem
I was about to reach the correct answer, but I lost my concentration. After all, I think that this ** maintaining mentality when I'm about to lose my concentration ** is the biggest challenge for me.
Consider the case where the sum of the numbers corresponding to even indexes when a certain continuous subsequence is selected and inverted is the maximum. First, for easy understanding, if the length of the selected continuous subsequence is odd, the sum does not change before and after inverting the selected continuous subsequence, so consider ** even **.
Therefore, for the elements contained in the selected even-length continuous subsequence, the odd-indexed elements are selected instead of the even-numbered index. Also, at this time, I tried to think of a continuous subsequence that maximizes the difference in change when changing from even to odd, but ** it is difficult to do with the greedy method, so DP is calculated like the maximum partial sum. I think it's a natural idea to think using ** (I wasn't able to organize my thoughts during the contest ...).
Here, when one continuous subsequence is selected (** consider with assumptions ), even indexes can be selected before and after the continuous subsequence, and odd indexes can be selected in the continuous subsequence. Yes ( three types of states !! **), DP can be defined as follows.
$ dp [i] [j]: = $ (maximum sum in each state $ j $ when $ i $ indexes are selected)
However, when $ j = 0 $, the continuous subsequence has not been selected yet, when $ j = 1 $, the continuous subsequence has not been selected yet, and when $ j = 2 $, the continuous subsequence has not been selected yet. It is said. (Continuous subsequences are likely to have two patterns: ** manage the end of the continuous subsequence and take the accumulation at the end ** and ** manage whether the continuous subsequence is selected, so keep it down. I want to.)
Also note that you want to find the sum of the elements of the selected index, so it should be the $ i $ th, not the ** $ i $ th **.
Furthermore, even-numbered continuous subsequences have ** patterns starting with even-numbered indexes and patterns ** starting with odd-numbered indexes, with the former corresponding to $ i $ being $ a_ {2i-1} $. $ a_ {2i} $, the latter corresponding to $ i $ is $ a_ {2i} $ and $ a_ {2i + 1} $.
From the above, considering the transition of DP that can be obtained by performing DP for each of the two patterns, it is as follows. Also, in the following, we are considering a pattern that starts with an odd index.
(1) When $ j = 0 $
There is no choice but to select the elements with even index, and it will be as follows.
(2) When $ j = 1 $
There is no choice but to select an element with an odd index, and there can be two transition sources, $ dp [i-1] [0] and dp [i-1] [1] $, so it is as follows.
(3) When $ j = 2 $
There is no choice but to select an even index element, and there can be two transition sources, $ dp [i-1] [1] and dp [i-1] [2] $, so it is as follows.
Also, if you implement it while paying attention to $ i = 0 $ ~ $ [\ frac {n-1} {2}] $, it will be as follows.
D.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
dp0=[[0,0,0] for i in range((n-1)//2+1)]
for i in range((n-1)//2+1):
if i==0:
dp0[i][0]=a[2*i]
continue
dp0[i][0]=dp0[i-1][0]+a[2*i]
dp0[i][1]=max(dp0[i-1][0],dp0[i-1][1])+a[2*i-1]
dp0[i][2]=max(dp0[i-1][1],dp0[i-1][2])+a[2*i]
dp1=[[0,0,0] for i in range((n-1)//2+1)]
for i in range((n-1)//2+1):
if i==0:
dp1[i][0]=a[2*i]
if 2*i+1<n:dp1[i][1]=a[2*i+1]
continue
dp1[i][0]=dp1[i-1][0]+a[2*i]
if 2*i+1<n:dp1[i][1]=max(dp1[i-1][0],dp1[i-1][1])+a[2*i+1]
if 2*i<n:dp1[i][2]=max(dp1[i-1][1],dp1[i-1][2])+a[2*i]
#print(dp0)
#print(dp1)
print(max(dp0[(n-1)//2]+dp1[(n-1)//2]))
E problem
For example, when $ x = 108, k = 3 $, it becomes $ 108,109,110,111 $, but when there is no carry, $ f (x + 1) = f (x) + 1 $ holds. Therefore, we will classify cases with ** no carry and with **, and look for cases with given $ n $. If there are multiple $ x $ candidates, the smallest one should be output. (Here, obviously ** I gave up the implementation because it was troublesome to carry it up **, but I was able to solve it after the contest, I regret it ...)
(1) When there is no carry
Looking at the last digit, it is $ i, i + 1,…, i + k $. At this time, when $ i, i + 1,…, i + k $ and $ i + l, i + l + 1,…, i + l + k $ are compared with $ l> 0 $, the latter is above. The sum of each digit is $ (k + 1) \ times l $ less than the former. Therefore, ** the least significant digit should be as large as possible **, and $ 9-k, 9-k + 1,…, 9-k + k $ is optimal (✳︎). At this time, the sum of the least significant digits is $ \ frac {(18-k) (k + 1)} {2} $, so the digits above it are $ n- \ frac {(18-k). Consider constructing with (k + 1)} {2} $. Here, ** because there is no carry, the upper digits are all the same **, and if the sum of the digits is $ X $, then $ n- \ frac {(18-k) (k + 1)} {2} = X \ times (k + 1) $ must hold. When this is true, it becomes $ X = \ frac {n- \ frac {(18-k) (k + 1)} {2}} {k + 1} $. Also, in order to make the upper digit as small as possible, if 9 is placed in order from the lower digit, the surplus number should be placed in the most significant digit. Furthermore, about (✳︎), $ n \ leqq \ frac {(18-k) (k + 1)} {2} $ is not optimal, so ** $ x = 0 $ ~ $ 9-k $ at this time. You can try all the streets of **.
(2) When there is a carry
At this time, it is necessary to check both information on (1) ** how many 9s are consecutive excluding the lowest digit ** and (2) ** what number the lowest digit 9 appears in **. .. Regarding (1), we investigated up to $ 19 $ this time due to the constraint that $ n $ is about 150. For ②, you can try the number (0-indexed) where the least significant digit is 9 from $ 0 $ to $ k-1 $. Therefore, let us consider the former as $ num9 $ and the latter as $ j $. Also, since it is complicated to write in letters, the current situation is shown in a diagram. (If you don't understand the case of (1), you may want to draw a diagram.)
As shown in the above figure, +1 in carry is $ 1 \ times (kj) $, consecutive 9 excluding the least significant digit is $ num9 \ times 9 \ times (j + 1) $, and least significant digit is $ \ frac {(18-j) (j + 1)} {2} + \ frac {(kj) (kj-1)} {2} $, subtracted from $ n $ and left (1 ) And the same consideration. The basics are the same, but only note that the last digit in the upper digit cannot be 9 and is 8 to prevent carry.
Implementing the above, it becomes as follows. When I solved it, I felt that the implementation was heavy, but I felt that it was a problem that ** I could improve the prospect of implementation by using not only verbalization but also diagrams **.
E.py
for _ in range(int(input())):
n,k=map(int,input().split())
ans=[]
#Do not carry up
if n<=(18-k)*(k+1)//2:
for i in range(10):
check=n
for j in range(k+1):
if i+j>9:
break
else:
check-=(i+j)
else:
if check==0:
ans.append(i)
else:
check=n-(18-k)*(k+1)//2
if check%(k+1)==0:
check//=(k+1)
i,j=check%9,check//9
if i==0:
ans.append(int("9"*j+f"{9-k}"))
else:
ans.append(int(f"{i}"+"9"*j+f"{9-k}"))
#There is a carry
for num9 in range(20):
for j in range(k):
check=n-(18-j)*(j+1)//2-(k-j)*(k-j-1)//2
check-=(num9*9*(j+1))
check-=(1*(k-j))
#print(check)
if check>=0:
if check%(k+1)==0:
check//=(k+1)
h,i=check%9,check//9
#You don't have to divide by 9
if i==0:
if h==0:
ans.append(int("9"*num9+f"{9-j}"))
else:
ans.append(int(f"{h}"+"9"*num9+f"{9-j}"))
else:
check-=8
h,i=check%9,check//9
if h==0:
ans.append(int("9"*i+"8"+"9"*num9+f"{9-j}"))
else:
ans.append(int(f"{h}"+"9"*i+"8"+"9"*num9+f"{9-j}"))
#print(ans)
if len(ans):
print(min(ans))
else:
print(-1)
After the F problem
I will skip this time
Recommended Posts