To check if an amount $$$n$$$ can be formed using coins of denominations $$$2$$$ and $$$k$$$ (with $$$k \ne 2$$$), we can simplify the problem using a key observation: two $$$k$$$-coins can be replaced by $$$k$$$ coins of $$$2$$$, since $$$2k = k \cdot 2$$$.

This means any solution using two or more $$$k$$$-coins can be transformed into one with at most one $$$k$$$-coin. So, we only need to check two cases:

Use only $$$2$$$-coins: possible if $$$n$$$ is even.

Use one $$$k$$$-coin and the rest $$$2$$$-coins: possible if $$$n \ge k$$$ and $$$n - k$$$ is even.

If either condition holds, the answer is "YES"; otherwise, it's "NO". This allows each test case to be solved in constant time.

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    if n % 2 == 0 or (n >= k and (n - k) % 2 == 0):
        print("YES")
    else:
        print("NO")

In this problem, we are given a sequence of cells arranged in a line (from $$$1$$$ to $$$n$$$) with portals between some of them. The portals are one-way and described using an array $$$a$$$, where each element $$$a_i$$$ tells us that from cell $$$i$$$, we can move forward to cell $$$i + a_i$$$. We begin at cell $$$1$$$ and are asked to determine whether we can reach cell $$$t$$$ using only the available portals.

This structure can be interpreted as a directed graph, where each node (cell) has exactly one outgoing edge (as described by the portals). Since we only move forward and there is no branching (each node goes to exactly one next node), we can simulate this as a simple linear traversal—essentially a simplified depth-first search (DFS) or a loop—starting from cell $$$1$$$ and following the portals until we either reach cell $$$t$$$ or go past it.

We continue moving from the current cell to the next one given by the portal, i.e., from $$$i$$$ to $$$i + a_i$$$, and check at each step whether we've landed at cell $$$t$$$. If we do, we output "YES". If we go beyond it or reach a point from which we can no longer progress toward $$$t$$$, we conclude it's unreachable and output "NO."

This logic runs in linear time and is highly efficient due to the constraint that each cell leads to only one next cell.

n, t = map(int, input().split())
a = list(map(int, input().split()))

pos = 1
while pos < t:
    pos += a[pos - 1]

if pos == t:
    print("YES")
else:
    print("NO")

We are given a grid where each cell contains a non-negative integer representing the depth of water. A lake is defined as a group of connected cells (connected up, down, left, or right) that all have positive depth (greater than zero). Our goal is to find the lake with the largest total volume, where volume is the sum of depths of all cells in that lake.

To solve this, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS). The idea is to explore the grid cell by cell. Whenever we find a cell with depth greater than zero that we haven’t visited before, we start a DFS/BFS from that cell to find all connected cells belonging to the same lake. During this traversal, we accumulate the total depth (volume) of the lake.

After completing the search for a lake, we compare its volume with the maximum volume found so far and update if needed. We repeat this process until all cells have been checked.

This approach ensures that each cell is visited at most once, resulting in an overall time complexity of $$$O(nm)$$$ where $$$n$$$ and $$$m$$$ are the grid dimensions. This is efficient enough given the problem constraints.

Implementing the search iteratively (using a stack for DFS or a queue for BFS) instead of recursively often gives better performance in practice, avoiding the overhead and limitations of recursion and reducing the risk of stack overflow on large inputs.

import sys
input = sys.stdin.readline

t = int(input())
directions = [(1,0), (-1,0), (0,1), (0,-1)]

for _ in range(t):
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    
    max_volume = 0
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] > 0 and not visited[i][j]:
                stack = [(i,j)]
                volume = 0
                visited[i][j] = True
                
                while stack:
                    x, y = stack.pop()
                    volume += grid[x][y]
                    
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < m:
                            if grid[nx][ny] > 0 and not visited[nx][ny]:
                                visited[nx][ny] = True
                                stack.append((nx, ny))
                
                if volume > max_volume:
                    max_volume = volume
    
    print(max_volume)

The problem models a 3D plate composed of $$$k$$$ layers, each layer being a 2D grid of size $$$n \times m$$$. Some cells are empty '.', where water can fill, and some contain obstacles '#' that block water flow. Water starts pouring from a specific cell in the top layer and flows to adjacent cells in all 6 directions — up, down, left, right, forward, and backward — but only through empty cells.

To determine how many units of water the plate can hold before overflowing, the key is to find how many empty cells are reachable from the starting tap position. Each reachable empty cell can hold exactly one unit of water. Therefore, the answer is the count of all connected empty cells accessible from the tap.

The solution treats the plate as a 3D grid and performs a Depth-First Search (DFS) starting from the tap’s cell in the top layer. DFS explores all neighboring cells in the six possible directions — vertically between layers, horizontally between rows, and laterally between columns — as long as those cells are within bounds, empty, and not yet visited. This exploration simulates the spread of water filling every reachable empty cell.

The code first reads the 3D grid input carefully, handling blank lines between layers, and converts the coordinates of the tap to zero-based indexing. Then, it initializes a 3D visited array to keep track of cells already counted. The DFS uses an explicit stack to avoid recursion limits and traverses all accessible cells, counting each as water volume.

Finally, the total count of reachable cells represents how many minutes until the plate is completely filled (since one unit of water falls each minute). If the water falls beyond this count, it would overflow, so the answer is this count.

This approach efficiently solves the problem in time complexity $$$O(kmn)$$$ since each cell is visited at most once, which is practical given the problem constraints.

def read_3d_grid():
    d, r, c = map(int, input().split())
    grid = []
    layers_read = 0

    while layers_read < d:
        line = input().strip()
        if line == "":
            continue
        layer = [list(line)]
        for _ in range(r - 1):
            layer.append(list(input().strip()))
        grid.append(layer)
        layers_read += 1

    while True:
        start_line = input().strip()
        if start_line:
            break

    start_x, start_y = map(int, start_line.split())
    start_x -= 1
    start_y -= 1

    return d, r, c, grid, start_x, start_y


def in_bounds(z, x, y, d, r, c):
    return 0 <= z < d and 0 <= x < r and 0 <= y < c


def dfs(z, x, y, grid, visited, d, r, c):
    stack = [(z, x, y)]
    visited[z][x][y] = True
    minutes = 0

    directions = [
        (1, 0, 0), (-1, 0, 0),
        (0, 1, 0), (0, -1, 0),
        (0, 0, 1), (0, 0, -1)
    ]

    while stack:
        cz, cx, cy = stack.pop()
        minutes += 1

        for dz, dx, dy in directions:
            nz, nx, ny = cz + dz, cx + dx, cy + dy
            if in_bounds(nz, nx, ny, d, r, c):
                if not visited[nz][nx][ny] and grid[nz][nx][ny] == '.':
                    visited[nz][nx][ny] = True
                    stack.append((nz, nx, ny))

    return minutes


d, r, c, grid, start_x, start_y = read_3d_grid()
visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(d)]

start_layer = 0

if grid[start_layer][start_x][start_y] == '.':
    minutes_until_overflow = dfs(start_layer, start_x, start_y, grid, visited, d, r, c)
else:
    minutes_until_overflow = 0

print(minutes_until_overflow)