[PYTHON] Codeforces Round # 651 (Div. 2) Bacha Review (8/20)
This time's results
Impressions of this time
I spent a huge amount of time without seeing B as a gag. I am very disappointed. I couldn't see it because I tried to find the maximum value by ** misreading the problem statement **. The pattern that should be easy but strange is usually ** missed in the question sentence **, so let's make a calm judgment.
Problem A
Consider the one with the greatest $ gcd (a, b) (= X) $ among the $ a, b $ that satisfies $ 1 \ leqq a <b \ leqq n $. At this time, both $ a and b $ are multiples of $ X (\ geqq 1) $, and both $ a = X and b = 2X $ are the largest among $ n $ or less. Therefore, $ X = [\ frac {n} {2}] $ is the answer.
A.py
for _ in range(int(input())):
n=int(input())
print(n//2)
Problem B
** I overlooked the problem statement ** and was trying to find the greatest gcd. Actually, you should output so that gcd larger than 1 is satisfied.
It's easy to think that ** gcd should be 2 **. In other words, odd numbers should be paired and even numbers should be paired and added together. At this time, there are at most two ** numbers that cannot be made into ** pairs, odd and even, so you can always make more than $ n-1 $ pairs. Therefore, you can output this $ n-1 $ pair.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
xy=[[] for i in range(2)]
for i in range(2*n):
xy[a[i]%2].append(i+1)
ans=[]
for i in range(2):
for j in range(len(xy[i])//2):
ans.append([xy[i][2*j],xy[i][2*j+1]])
for i in range(n-1):
print(" ".join(map(str,ans[i])))
C Problem
I wasn't able to think correctly because of B's impatience. In such cases, be sure to ** take a break **. In the following, $ Ashishgup $ will be $ A $ and $ FastestFinger $ will be $ F $.
There are two operations for $ n $ in the problem: ① Divide $ n $ by an odd divisor of $ n $ excluding 1, or ② Subtract 1 from $ n $.
The person who can finally set $ n $ to 1 wins, so we aim to set it to 1 first. First, consider the case where ** $ n $ is odd **. At this time, you can divide it by $ n $ to make it 1, so you win $ A $. However, if ** $ n = 1 $ **, the loss of $ A $ is confirmed, so $ F $ wins.
Next, consider the case where ** $ n $ is even **. At this time, if you operate ②, you will lose $ A $, so consider operating ①. However, if ** $ n = 2 $ **, you can subtract 1 to make $ n $ 1 so $ A $ can win.
Here, let $ fac (n) $ be ** how many odd numbers are included in $ n $ when factored into prime factors **. When ** $ fac (n) = 0 $ ** cannot operate ①, $ A $ has no choice but to operate ②, and $ F $ wins. Here, if ** $ fac (n)> 0 $ and $ n $ is a multiple of 4, then $ n $ can be changed to $ fac (n) = 0 $ and $ n> 2 $ by the operation of ②. So $ A $ wins.
The last thing left is ** $ fac (n)> 0 $ and even $ n $ ** that is not a multiple of 4. Here, when ** $ fac (n) = 1 $ **, in the case of operation ②, it becomes an odd number and loses, and in the case of operation ①, $ n = 2 $, so $ F $ wins. To do. On the other hand, when ** $ fac (n)> 1 $ ** can be divided by an odd number to make $ fac (n) = 1 $, $ A $ wins.
I felt that it was necessary to calmly solve the problem because the samples should be sorted in order ** and the samples are kind. Also, it is easy to think that such a ** asymmetrical game problem ** is aware that the first player has a considerable advantage.
C.py
from math import sqrt
def fac(n):
if n==1:return 0
for i in range(2,int(sqrt(n))+1):
if n%i==0:
return fac(i)+fac(n//i)
if n%2==1:
return 1
else:
return 0
for _ in range(int(input())):
ans=["Ashishgup","FastestFinger"]
n=int(input())
#print(fac(n)+(n%2==0)+(n%4==0))
if n==1:
print(ans[1])
elif n==2:
print(ans[0])
elif n%2==1:
print(ans[0])
elif fac(n)==0:
print(ans[1])
elif n%4==0:
print(ans[0])
else:
if fac(n)>1:
print(ans[0])
else:
print(ans[1])
D Problem
Try to minimize the maximum of each of the odd and even indexes for the selected subsequence. Also, the size of such subsequences is fixed at $ k (\ geqq 2) $.
** At first, I thought about how to greedily choose from the smaller one **. In other words, the smaller ones are selected in order. However, this method tries to make both the odd index element and the even index element smaller, so I felt that there was a way to make it smaller ($ \ because $ ** if only one index element became smaller). Because it's good **).
Now consider reducing only the odd indexes (as well as the even indexes only). Also, since it is difficult to select just $ k $ elements, I considered a binary search because it seems that there is still room for constraints and finding the minimum value (this consideration borders the ** minimum value). You can be confident that it has a monotonicity ** that meets or changes with the condition and ** counts the number of times **.).
Therefore, consider whether you can select ** $ k $ (or more) elements ** while satisfying that only odd indexes are less than or equal to a certain value of $ X $. Under this, elements can be ** greedily selected **. In other words, for odd-numbered index elements, select the first appearing element below $ X $ as a subsequence, and for even-numbered index elements, select the next element after the odd-numbered index element. If you can select $ k $ (or more) elements in this way, return True, and if you can not select, check the time of even index.
You can also implement binary search without bugs by looking at this article. At the beginning, you only need to pay attention to the range of $ l and r $ set by the initial value **.
D.py
#You can choose one conveniently
n,k=map(int,input().split())
a=list(map(int,input().split()))
def f(x):
global n,k,a
#Can it be less than x(This is the odd number)
check=0
now=1
for i in range(n):
if now:
if a[i]<=x:
now=1-now
check+=1
else:
now=1-now
check+=1
if check>=k:
#print(check)
return True
#Even number
check=0
now=0
for i in range(n):
if now:
if a[i]<=x:
now=1-now
check+=1
else:
now=1-now
check+=1
if check>=k:
#print(check)
return True
else:
#print(check)
return False
l,r=0,10**9+1
#Find the minimum value
while l+1<r:
m=l+(r-l)//2
#print(f(m))
if f(m):
r=m
else:
l=m
print(r)
E Problem
Consider the minimum number of operations to match $ S $ to $ T $ by repeatedly selecting a substring of a binary string and shifting the characters one by one clockwise.
Here, ** 0 and 1 cannot be matched unless they are equal **, so -1 is output. Therefore, in the following, we only need to consider strings with the same number of 0s and 1s. (Conversely, strings with the same number of 0s and 1s can always be matched, but the proof is omitted here.)
First of all, think about ** greedily deciding from the end **. For such problems, you can reduce the number of operations by ** greedy algorithm that changes as many characters as possible **. Also, you don't have to think about what already matches, so only think about different positions.
However, I couldn't think of a solution, so I thought about ** looking at the sample and experimenting ** (I can't solve it without a good sample, so I want to not rely too much on the sample **. is.). At this time, I paid attention to the following patterns.
8
10101010
01010101
In this pattern, ** all positions are different, but it is $ S \ rightarrow T $ ** in one operation. Generalizing this, if ** 0 and 1 are staggered and even-numbered subsequences **, you can perform an operation to match all the selected parts.
At this time, I tried to simulate while generating subsequences starting with 0 and 1, but this policy was unsuccessful because it was too cumbersome to implement. Here is a ** easier way to simulate **. In other words, you only need to save ** how many staggered subsequences start with 0,1 when you look at a certain character. Also, I want each subsequence to be as long as possible, so if it can be connected **, connect it to the remaining subsequences **.
Therefore, $ v \ _1: Number of subsequences starting at $ 0, $ v \ _2: $ 0 Number of subsequences starting at 0 and ending at 0 (unfinished), $ w \ _1: Number of subsequences starting at $ 1, $ w \ _2: $ 1 Place the number of subsequences that start and end with 1 (unfinished), and variables. Then, the $ i $ th is 0 or 1, and the cases are divided as follows.
(1) When the $ i $ th is 0 [1] When $ w \ _2 $ is greater than 0 → Add 0 to the unfinished subsequence, $ w \ _2 $-= 1. → At this time, you can see that ** the number of subsequences does not increase **. [2] When $ w \ _2 $ is 0 → When $ v \ _1> v \ _2 $, you can increase the number of unfinished subsequences, which is $ v \ _2 $ + = 1. → At this time, you can see that ** the number of subsequences does not increase **. → When $ v \ _1 = v \ _2 $ ** There is a need to add a new subsequence **, which is $ v \ _1 $ + = 1 and $ v \ _2 $ + = 1.
(2) When the $ i $ th is 1. [1] When $ v \ _2 $ is greater than 0 → Add 0 to the unfinished subsequence, which is $ v \ _2 $-= 1. → At this time, you can see that ** the number of subsequences does not increase **. [2] When $ v \ _2 $ is 0 → When $ w \ _1> w \ _2 $, you can increase the number of unfinished subsequences, which is $ w \ _2 $ + = 1. → At this time, you can see that ** the number of subsequences does not increase **. → When $ w \ _1 = w \ _2 $ ** There is a need to add a new subsequence **, and $ w \ _1 $ + = 1 and $ w \ _2 $ + = 1.
If the number of 0s and 1s is not equal and according to this greedy algorithm, ** finally $ v \ _2, w \ _2 $ will be 0 ** (proof is omitted). Therefore, the answer is $ v \ _1 + w \ _1 $ after performing the greedy algorithm.
E.py
#Make the implementation lighter!
n=int(input())
s=input()
t=input()
if s.count("1")!=t.count("1"):
print(-1)
exit()
#Of the string+Computational complexity
x=[s[i] for i in range(n) if s[i]!=t[i]]
#v starts at 0
#w is 1 start
#1 is total
#2 is the surplus
v1,v2,w1,w2=0,0,0,0
for i in x:
if i=="0":
if w2==0:
if v1==v2:
v1+=1
v2+=1
else:
w2-=1
else:
if v2==0:
if w1==w2:
w1+=1
w2+=1
else:
v2-=1
print(v1+w1)
After the F problem
I will skip this time
Recommended Posts