Skip to content

1821

A_Matching

Explanation

Logic:

For a given integer template, the number of integers that match the template depends on the number of question marks and their positions.

For the first position, if it's a question mark, you can use any digit from 1 to 9; for other positions, if it's a question mark, you can use any digit from 0 to 9.

Approach:

Iterate through the given string, checking each character. If the first character is '0', set the result to 0. If the character is a question mark, multiply the result by 9 if it's the first position, otherwise multiply by 10.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def solve():
    s = input().strip()

    if s[0] == "0":
        print(0)
        return

    res = 1
    for i, char in enumerate(s):
        if char == "?":
            res *= 9 if i == 0 else 10

    print(res)


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

B_Sort_the_Subarray

Explanation

Find two integers l and r (1≤𝑙≤𝑟≤𝑛), such that sorting the subarray a[l..r] of the given array a would result in the given array a. If there are multiple answers, choose the one with the longest subarray. If there are still multiple answers, any of them is acceptable.

 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())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    l, r = 0, n - 1

    while a[l] == b[l]:
        l += 1

    while a[r] == b[r]:
        r -= 1

    while r < n - 1 and b[r] <= b[r + 1]:
        r += 1

    while l > 0 and b[l - 1] <= b[l]:
        l -= 1

    print(l + 1, r + 1)


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

C_Tear_It_Apart

Explanation

  1. Iterate through all lowercase Latin letters (26 iterations).
  2. For each letter, split the input string s into substrings, using the current letter as the delimiter.
  3. For each substring created in step 2, calculate the minimum number of operations required to make all the letters in the substring the same. This is done by finding the length of the substring and calculating the smallest power of 2 that is greater than or equal to that length. The number of operations required is the exponent of that power of 2.
  4. Keep track of the maximum number of operations required among all the substrings for the current letter.
  5. After iterating through all the letters, find the minimum number of operations among all the maximums calculated in step 4. This minimum will be the answer to the problem.
 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
def solve():
    s = input()
    min_operations = float("inf")

    for i in range(26):
        current_char = chr(97 + i)
        substrings = s.split(current_char)

        max_operations_for_char = 0
        for substring in substrings:
            length = len(substring)
            operations = 0

            # smallest power of 2 that is greater than or equal to the len of substr
            while length > 0:
                length //= 2
                operations += 1

            max_operations_for_char = max(max_operations_for_char, operations)

        min_operations = min(min_operations, max_operations_for_char)

    print(min_operations)


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