Skip to content

1810

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)

A_Beautiful_Sequence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def solve():
    n = int(input())
    ar = list(map(int, input().split()))
    for i in range(n):
        if ar[i] <= i + 1:
            print("YES")
            return
    print("NO")


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

B_Candies

Explanation

The solution to this problem focuses on manipulating the number of candies by applying either the first or second spell. The idea is to check if it is possible to reach the target number of candies (n) within 40 steps.

For each step, the algorithm determines whether it is better to use the first or the second spell based on whether the result of the spell will be closer to the target number.

The algorithm continues applying spells and updating the number of candies until it reaches the target number or reaches the 40-step limit.

If the target is reached, the sequence of spells is printed, otherwise, it prints -1.

 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():
    n = int(input())

    if n % 2 == 0:
        print(-1)
        return

    res = []
    while n != 1:
        if (n + 1) // 2 % 2 == 1:
            n += 1
            res.append(1)
        else:
            n -= 1
            res.append(2)
        n //= 2

    res.reverse()
    print(len(res))
    print(" ".join(map(str, res)))


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

C_Make_It_Permutation

 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
29
30
31
32
33
34
def solve():
    n, c, d = map(int, input().split())
    ar = list(map(int, input().split()))

    l = 0
    r = 0

    res = c * n + d
    min_cost = 0

    ar.sort()
    if ar[0] != 1:
        res = min(res, c * n + d)

    for i in range(n):
        r = ar[i]
        to_remove = n - i - 1

        if l == r:
            min_cost += c
        elif r == l + 1:
            l = r
            min_cost += 0
        else:
            min_cost += d * (max(0, r - l - 1))
            l = r

        res = min(res, min_cost + c * to_remove)

    print(res)


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

D_Climbing_the_Tree

Explanation

  1. Initialize the minimum and maximum range with the given limits.
  2. Iterate through each query and perform the operations.
  3. For type 1 operation:
    1. Calculate the current minimum and maximum values using the given integers 'a', 'b', and 'n'.
    2. Update the overall minimum and maximum range by taking the intersection of the current range with the overall range.
    3. Append the result (0 or 1) based on whether the updated range is valid or not.
  4. For type 2 operation:
    1. Calculate the minimum value of 'n' that satisfies the condition based on the current range and given integers 'a' and 'b'.
    2. Append the result (-1 or minimum 'n').
 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
29
30
31
32
33
34
def solve():
    min_range, max_range = 1, 10**18
    results = []

    for _ in range(int(input())):
        operation = list(map(int, input().split()))

        if operation[0] == 1:
            a, b, n = operation[1], operation[2], operation[3]
            curr_min = 1 if n == 1 else (a - b) * (n - 2) + a + 1
            curr_max = (a - b) * (n - 1) + a

            if curr_min <= max_range and curr_max >= min_range:
                results.append(1)
                min_range = max(min_range, curr_min)
                max_range = min(max_range, curr_max)
            else:
                results.append(0)

        else:
            a, b = operation[1], operation[2]
            min_n = max(1, (min_range - a - 1) // (a - b) + 2)
            max_n = max(1, (max_range - a - 1) // (a - b) + 2)

            if max_n > min_n:
                results.append(-1)
            else:
                results.append(min_n)

    print(*results)


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