1814

A_Coins

Explanation

1. First, check if n is even. If it is, you can always represent n using coins of denomination 2 (2*x = n, and y = 0).
2. If n is odd, then the only way to represent n is by using an odd number of k coins and an even number of 2 coins (since the sum of an odd number of odd integers and an even number of even integers is odd). In this case, check if n >= k and k is odd. If so, it's possible to represent n using these coins.

If n is even, then you can always represent n using only coins of denomination 2. If n is odd, it checks if n is greater than or equal to k and if k is odd. If this condition is satisfied, you can represent n using the given coins. Otherwise, it's not possible to represent n using the coins.

def solve():
    n, k = map(int, input().split())

    if n % 2 == 0:
        print("YES")
    elif n >= k and k % 2 == 1:
        print("YES")
    else:
        print("NO")


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

B_Long_Legs

Explanation

1. Iterate through possible leg lengths (m) from 1 to a large number (e.g., 10^5).
2. For each leg length m, calculate the number of horizontal jumps (jumps_a) and vertical jumps (jumps_b) the robot needs to reach cells a and b, respectively.
3. The total moves required for each leg length m is the sum of m (number of times the robot increases its leg length), jumps_a, and jumps_b.
4. Keep track of the minimum moves among all leg lengths.

Iterates through possible leg lengths (m) and calculates the number of horizontal jumps (jumps_a) and vertical jumps (jumps_b) required to reach the target cell (a,b) for each leg length. The minimum number of moves for the robot is the sum of the leg length increases and the number of horizontal and vertical jumps. By iterating through leg lengths and keeping track of the minimum moves, the solution finds the optimal leg length and the minimum number of moves required to reach the target cell.

def solve():
    a, b = map(int, input().split())
    ans = float("inf")
    for m in range(1, 10**5):
        jumps_a = (a + m - 1) // m
        jumps_b = (b + m - 1) // m
        ans = min(ans, jumps_a + jumps_b + m - 1)
    print(int(ans))


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

C_Search_in_Parallel

Explanation

You have n boxes with balls of different colors and two robots to retrieve balls for you. You need to assign the boxes to two lists (a and b), one for each robot. When you request a ball of color x, the robots search the boxes in their list one by one. The first robot takes s1 seconds to analyze a box, and the second robot takes s2 seconds. You have to assign the boxes to the lists in such a way that the total search time for all requests is minimized.

1. Sort the boxes in decreasing order of the number of requests for their corresponding color.
2. Iterate through the sorted list of boxes.
3. Assign each box to the robot that will minimize the total search time.
4. Print the lists a and b.

def solve():
    n, s1, s2 = map(int, input().split())
    R = list(map(int, input().split()))
    S = sorted(range(n), key=lambda i: -R[i])

    A, B = [], []
    a, b = 0, 0
    for i in S:
        k = R[i]
        if (a + s1) * k <= (b + s2) * k:
            A.append(i + 1)
            a += s1
        else:
            B.append(i + 1)
            b += s2

    print(len(A), *A)
    print(len(B), *B)


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