A2SV G5 — Contest 3 Editorial
Разница между en4 и en5, 6 символ(ов) изменены
[Here](https://codeforces.net/gym/492793037) is the mashup link (the problems are from Codeforces' problem set).↵
#### [A. The Olympic Legend](https://codeforces.net/gym/492797/problem/A)↵

<spoiler summary = "Hint">↵
<p>Count how many of b, c, d are greater than a.</p>↵
</spoiler>↵

<spoiler summary = "Solution">↵
<p>If b > a, we count 1. If c > a we add 1, and the same for d.</p>↵
</spoiler>↵

<spoiler summary="Code">↵
```python3↵

t = int(input())↵
for _ in range(t):↵

    a, b, c, d = map(int, input().split())↵
    infront = (b > a) + (c > a) + (d > a)↵
    print(infront)↵

```↵
</spoiler>↵

#### [B. Yes-Yes?](https://codeforces.net/gym/492797/problem/B)↵

<spoiler summary = "Hint">↵
<p>Think of the order of characters in 'Yes'.</p>↵
</spoiler>↵

<spoiler summary = "Solution">↵
<p>Order of characters:↵
'e' should follow 'Y',↵
's' should follow 'e',↵
and 'Y' should follow 's'.↵
For every character other than the first one, we check if it is found in 'Yes' and check if the current character can follow the previous one. Handle the first character with an if condition.↵

</p>↵
</spoiler>↵

<spoiler summary="Code">↵
```python3↵

t = int(input())↵
next_char = {↵
            'Y': 'e',↵
            'e': 's',↵
            's':'Y'↵
            }↵

for _ in range(t):↵
    s = input()↵

    if s[0] not in next_char:↵
        print('NO')↵
        continue↵

    yes = True↵
    for index in range(1, len(s)):↵
        prev = s[index - 1]↵
        cur = s[index]↵

        if cur not in next_char or next_char[prev] != cur:↵
            yes = False↵
            break↵

    print('YES' if yes else 'NO')↵
    ↵
```↵
</spoiler>↵


#### [C. Notepad#](https://codeforces.net/gym/492797/problem/C)↵

<spoiler summary= "Hint">↵
 if any appropriate substring exists, an appropriate substring of length 2 also exists.↵
</spoiler>↵


<spoiler summary = "Solution">↵
Why does the problem ask us only to check if we can do less than n↵
 operations instead of just asking the minimum amount? That must be making the problem easier, so let's focus our attention on that.↵

What if it was ≤n↵
 instead of <n↵
? Well, then the problem would be trivial. You can type the word letter by letter and be done in n↵
 operations. So we only have to save one operation. In order to save at least one operation, we have to use the copy operation and copy more than one character in that.↵

Let's think further. Imagine we found a substring that works. Let it have length k↵
. Notice how you can remove its last character, obtaining a substring of length k−1↵
, and it will still occur in the same set of positions (possibly, even more occurrences will be found). Remove characters until the substring has length 2↵
. Thus, if any appropriate substring exists, an appropriate substring of length 2↵
 also exists.↵

Finally, we can check if there exists a substring of length 2↵
 that appears at least twice in the string so that the occurrences are at least 2↵
 apart. That can be done with a set or a dictionary. Some implementations might require careful handling of the substrings of kind "aa", "bb" and similar.↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
from collections import Counter↵
t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    s = input()↵
    set_ = set()↵
    flag = False↵
    for i in range(2, n - 1):↵
        set_.add(s[i - 2:i])↵
        if s[i:i+2] in set_:↵
            flag = True↵
            break↵
    print("YES" if flag else "NO")↵
```↵
</spoiler>↵

#### [D. Matching Numbers](https://codeforces.net/gym/492797/problem/D)↵

<spoiler summary = "Hint">↵
Consider The cases where n is even and odd↵
</spoiler>↵


<spoiler summary = "Solution">↵
Let's assume that 1 to 2n is paired and each sum of pair is k,k+1,⋯,k+n−1↵
. Sum from 1↵
 to 2n↵
 should equal to the sum of k↵
 to k+n−1↵
. So we obtain n(2n+1)=(2k+n−1)n/2↵
, which leads to 4n+2=2k+n−1↵
. Since 4n+2↵
 is even, 2k+n−1↵
 should be even. So if n↵
 is even, we cannot find such pairing.↵

If n↵
 is odd, there are various ways to make such pairing. ↵
Let's see one of them, If all the sums of the pairs are consecutive, it is possible to find the middle element by dividing the total sum of the pairs by n. From that, we can determine all the sums of the pairs, such as k, k+1, k+2, ..., k+n-1. We can then separate the sums into odd and even categories. For example, let the first sum (k) be even; we can start with 1 and k-1. By incrementing both numbers by 1, we can find the next even number. So, the first odd pair sum is k + 1. We can use the numbers (ceil(n/2) + 1) and (k + 1 &mdash; ceil(n/2) + 1) to obtain k + 1. By continuing to add 1 to both numbers, we can generate the next odd number.↵
</spoiler>↵

<spoiler summary="Code">↵
```python3↵

from math import ceil↵
t = int(input())↵
for _ in range(t):↵
    n = int(input())↵
    if n % 2 == 0:↵
        print("NO")↵
    else:↵
        print("YES")↵
        total = 2 * n↵
        total_sum = total* (total + 1) // 2↵
        middle_element = total_sum // n↵
        starting_number_one = middle_element - n // 2 - 1↵
        starting_number_two = middle_element - n // 2 + 1 - (ceil(n / 2) + 1)↵
        i = 1↵
        for _ in range(ceil(n / 2)):↵
            print(i, starting_number_one)↵
            i += 1↵
            starting_number_one += 1↵
        for _ in range(n // 2):↵
            print(i, starting_number_two)↵
            i += 1↵
            starting_number_two += 1↵

```↵
</spoiler>↵

#### [E. Acacius and String](https://codeforces.net/gym/492797/problem/E)↵


<spoiler summary = "Hint 1">↵
Consider when there is $0, 1,$ and more than $1$ occurrence of "$abacaba$" in string $s$.↵
</spoiler>↵

<spoiler summary = "Hint 2">↵

Once we have exactly one occurrence of "$abacaba$"  in $s$, we can replace all remaining '$?$' with a character that does not exist in "$abacaba$".↵
</spoiler>↵


<spoiler summary = "Solution">↵
<p>At first, we will count the occurrences of "$abacaba$" within the given string $s$. If the count is exactly one, it means there is a unique occurrence of "$abacaba$" in $s$. We can then replace all the '$?$' characters with a small letter character that doesn't exist in "$abacaba$" so that our final string still contains a unique occurrence of "$abacaba$$. ↵
</p>↵
<p>↵
If the count is zero for every $i$ such that $1 <= i <= n − 6$, we can choose a substring $s[i:i+7]$ and attempt to convert it into the string "$abacaba$". If that is possible, we will then replace the remaining '$?$' characters with a character that doesn't exist in "$abacaba$" and check the final string to ensure there is only one occurrence of "$abacaba$".↵
</p>↵
<p>↵
If the count is more than one, it implies there are multiple occurrences of "$abacaba$" in $s$. In this case, replacing question marks to achieve a unique occurrence is impossible.↵
</p>↵
</spoiler>↵


<spoiler summary="Code">↵
```python3↵
def count_sub_str(s,v):↵
    ans = 0↵
    for i in range(len(s)-6):↵
        if s[i:i+7] == v: ans += 1↵
    return ans↵
 ↵
def solve():↵
    n = int(input())↵
    s = input()↵
    sub_str = "abacaba"↵

    if count_sub_str(s,sub_str) == 1:↵
        s = s.replace('?','x')↵
        print("YES")↵
        print(s)↵
        return↵
   ↵
    for i in range(n-6):↵
        cur = list(s)↵

        for x in range(i,i+7):↵
            if cur[x] == '?':↵
                cur[x] = sub_str[x - i]↵

        cur = "".join(cur)↵
        if count_sub_str(cur,sub_str) == 1:↵
            cur = cur.replace('?','x')↵
            print("YES")↵
            print(cur)↵
            return↵
       ↵
    print("NO")↵
 ↵
T = int(input())↵
for _ in range(T):↵
    solve()↵

```↵
</spoiler>↵




История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский A2SV_Group5 2023-12-20 11:46:55 6 Tiny change: 'com/gym/492797) is the ' -> 'com/gym/493037) is the '
en4 Английский A2SV_Group5 2023-12-19 17:32:58 0 (published)
en3 Английский A2SV_Group5 2023-12-16 10:04:30 1 Tiny change: '=(2k+n−1)n2\n, which' -> '=(2k+n−1)n/2\n, which'
en2 Английский A2SV_Group5 2023-12-15 23:50:23 209
en1 Английский A2SV_Group5 2023-12-15 18:44:19 7622 Initial revision (saved to drafts)