Easily, we can sum up the difference between the maximum coins out of the three and the other two remaining coins. Then, we can subtract this value from the total coins Polycrap has. If Polycrap's remaining coins after this subtraction are less than $$$0$$$ or not divisible by $$$3$$$, the answer will be $$$NO$$$; otherwise, the answer will always be $$$YES$$$.

for _ in range(int(input())):
    a, b, c, n = map(int, input().split())
    n -= 3 * max(a, b, c) - a - b - c
    print('YES' if n % 3 == 0 and n >= 0 else 'NO')

If $$$ n$$$ is greater than $$$ k$$$ and $$$ n$$$ is divisible by $$$ k$$$, then the minimum maximum number will be 1, and the sum will be $$$ n$$$, which is divisible by $$$ k$$$. However, if $$$ n$$$ is not divisible by $$$ k$$$, the minimum maximum number will be 2. The sum of the array could be any number between $$$ n$$$ and $$$ 2n$$$, and since $$$ k$$$ is less than $$$ n$$$, we can guarantee that there is at least one number divisible by $$$ k$$$.

In the other case, if $$$ n$$$ is less than $$$ k$$$, to make the array sum divisible by $$$ k$$$, we can prove that we can't have a sum that is divisible by $$$ k$$$ if the maximum number in the array is less than $$$ \frac{k}{n}$$$. Therefore, the minimum maximum number will be $$$ \lceil \frac{k}{n} \rceil$$$.

for _ in range(int(input())):
    n,k = map(int,input().split())
    if n >= k:
        print(1 if n % k == 0 else 2)
    else:
        print((k-1)//n + 1)

The maximum value of $$$k$$$ should be determined in the following way: let's find the maximum number of people already sitting on the same bench (i. e. the maximum value in the array $$$a$$$). Let this number be $$$max(a)$$$. Then if all additional $$$m$$$ people seat on this bench, we will get the maximum possible value of $$$k$$$, so the answer is $$$max(a)+m$$$.

To determine the minimum value of $$$k$$$, let's perform $$$m$$$ operations. During each operation we put a new person on the bench currently having the minimum number of people occupying it. The answer is the maximum number of people on the bench after we perform this operation for each of $$$m$$$ newcomers.

import sys
from heapq import heapify, heappop, heappush
input = lambda: sys.stdin.readline().rstrip()


n = int(input())
m = int(input())
a = [int(input()) for line in range(n)]

_max = max(a) + m

heapify(a)
for i in range(m):
    min_bench = heappop(a)
    heappush(a, min_bench + 1)

_min = max(a)
print(_min, _max)
    

Since neither the graph nor the number of queries is too large, for each query you can simply count the number of the "good" colors (the colors that satisfies the condition) by checking if each color is "good". To do that, you can perform Depth First Search (or Breadth First Search) and verify whether you can reach vi from ui traversing only the edges of that color. If you prefer using Union-Find, it will also do the job.

from sys import stdin
from collections import defaultdict


def input(): return stdin.readline().strip()

N, M = map(int, input().split())

graph = [defaultdict(list)  for _ in range(M)]

for _ in range(M):
    u, v, c = map(int, input().split())
    adj = graph[c - 1]
    adj[u].append(v)
    adj[v].append(u)

dest = -1
def dfs(v, adj, visited):
    visited.add(v)
    if v == dest:
        return True
    for u in adj[v]:
        if u not in visited:
            if dfs(u, adj, visited):
                return True
    return False


Q = int(input())
for _ in range(Q):
    cnt = 0
    u, v = map(int, input().split())
    for adj in graph:
        visited = set()
        dest = v
        if dfs(u, adj, visited):
            cnt += 1
    print(cnt)

Firstly, we can find answers for all points that are adjacent to at least one point not from the set. The distance for such points is obviously $$$1$$$ (and this is the smallest possible answer we can get). On the next iteration, we can set answers for all points that are adjacent to points with found answers (because they don't have neighbors not from the set, the distance for them is at least $$$2$$$). It doesn't matter which point we will take, so if the point $$$i$$$ is adjacent to some point $$$j$$$ that have the answer $$$1$$$, we can set the answer for the point $$$i$$$ as the answer for the point $$$j$$$. We can repeat this process until we find answers for all points. In terms of the code, this can be done by breadth first search ($$$BFS$$$). In other words, we set answers for the points that have the distance $$$1$$$ and then push these answers to all adjacent points from the set in order of the increasing distance until we find all the answers.

Time complexity: $$$O(nlogn)$$$ .

import sys
from collections import deque
 
n = int(sys.stdin.readline().strip())
given_points = set()
points = []

for _ in range(n):
    x, y =  map(int, sys.stdin.readline().strip().split())
    points.append((x, y))
    given_points.add((x, y))

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

queue = deque()
visited = {}

for x, y in points:
    for dx, dy in directions:
        nx = x + dx
        ny = y + dy
        if (nx, ny) not in given_points:
            visited[(x, y)] = (nx, ny)
            queue.append((x, y))
            break


while queue:

    for _ in range(len(queue)):

        x, y = queue.popleft()
        for dx, dy in directions:
            nx = x + dx
            ny = y + dy
            if (nx, ny) not in visited and (nx, ny) in given_points:
                visited[(nx, ny)] = visited[(x, y)]
                queue.append((nx, ny))

ans = []
for x, y in points:
    ans.append(visited[(x, y)])
for a, b in ans:
    print(a, b)