Skip to content

1809

Educational Codeforces Round 145 (Rated for Div. 2)

TODO: B+

A_Garland

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def solve(s):
    if all(c == s[0] for c in s):
        return -1
    elif s.count(s[0]) == 3 or s.count(s[1]) == 3:
        return 6
    else:
        return 4


t = int(input())
for _ in range(t):
    s = input()
    print(solve(s))

B_Points_on_Plane

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import math

t = int(input())
for _ in range(t):
    n = int(input())
    a = math.isqrt(n)
    if a**2 == n:
        a -= 1

    print(a)

C_Sum_on_Subarrays

Explanation

You are given two numbers, 'n' and 'k'. Your task is to create an array of length 'n' with the sum of the elements equal to 'k'. The array can contain any integer numbers, but there is a condition - the sum of any contiguous subarray should be non-positive (less than or equal to 0).

You need to find an array that satisfies the given condition.

Example:

Input:

n = 3, k = 5

Output:

[-1, 2, -6]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def solve(n, k):
    res = [-1000] * n
    if k == 0:
        return " ".join(map(str, res))

    for i in range(n):
        possible = (i + 1) * (i + 2) // 2
        res[i] = 2

        if possible == k:
            break

        if k - possible <= i + 1:
            if k - possible == i + 1:
                res[i + 1] = -1
            else:
                x = 2 * (i + 1) + 1
                x -= 2 * (k - possible)
                res[i + 1] = -x

            break

    return " ".join(map(str, res))


for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    print(solve(n, k))

D_Binary_String_Sorting

Explanation

The idea of this solution is to iterate through the binary string, tracking the counts of zeros and ones. It evaluates the cost of sorting the string by considering various operations, such as swapping consecutive elements or removing elements.

By comparing the costs of these different operations, the solution determines the minimum number of coins required to sort the string in non-decreasing order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solve():
    s = input().strip()
    n = len(s)
    c0 = s.count("0")
    c1 = 0
    res = c0 * (10**12 + 1)

    for i in range(n - 1):
        if s[i] == "1":
            c1 += 1
        else:
            c0 -= 1

        if s[i] == "1" and s[i + 1] == "0":
            res = min(res, (c0 + c1 - 2) * (10**12 + 1) + 10**12)
        else:
            res = min(res, (c0 + c1) * (10**12 + 1))

    res = min(res, s.count("1") * (10**12 + 1))
    print(res)


for _ in range(int(input())):
    solve()