To solve this problem, let's use the following greedy algorithm.

Let's sort the prices of chocolate bars in increasing order, after which we will go from left to right and take chocolates that have a price not less than $$$l$$$, but not more than $$$r$$$ until we run out of money.

The number of chocolate bars that we took will be the answer to the problem.

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

import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

t = int(input())
for _ in range(t):
    n, l, r, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()

    ans = 0
    cur_sum = 0

    for num in a:
        if l <= num <= r and cur_sum + num <= k:
            cur_sum += num
            ans += 1
            
    print(ans)
    

To decode the encoded string, we can observe the following pattern: If the length of the encoded string is odd: The decoded string is formed by first taking and reversing the sequence of characters at odd indices (1st, 3rd, 5th, etc.) from the encoded string, followed by the sequence of characters at even indices (0th, 2nd, 4th, 6th, etc.). The entire sequence is then the final decoded string. If the length of the encoded string is even: The decoded string is formed by first taking and reversing the sequence characters at even indices (0th, 2nd, 4th, 6th, etc.), concatenated with the sequence characters at odd indices (1st, 3rd, 5th, etc.). The entire sequence is then the final decoded string.

n = int(input())
string = input()
if n % 2 == 0:
    part1 = [string[i] for i in range(n) if  i % 2 == 0][::-1]
    part2 = [string[i] for i in range(n) if i % 2]
    print(''.join(part1 + part2))
else:
    part1 = [string[i] for i in range(n) if i % 2][::-1]
    part2 = [string[i] for i in range(n) if i % 2 == 0]
    print(''.join(part1 + part2)) 

First let's consider the cases when the answer exists:

If $$$a=b$$$, then the thermostat is already set up and the answer is $$$0$$$. else if $$$|a−b|≥x$$$, then it is enough to reconfigure the thermostat in $$$1$$$ operation. else if exist such temperature $$$c$$$, that $$$|a−c|≥x$$$ and $$$|b−c|≥x$$$, then you can configure the thermostat in 2 operations. If such $$$c$$$ exists between $$$l$$$ and $$$r$$$, we can chose one of bounds: $$$a→l→b$$$ or $$$a→r→b$$$. we need to make $$$3$$$ operations if times if we cannot reconfigure through one of the boundaries as above, but we can through both: $$$a→l→r→b$$$ or $$$a→r→l→b$$$

If we can't get the temperature b in one of these ways, the answer is $$$−1$$$.

def solve():
    l, r, x = map(int, input().split())
    a, b = map(int, input().split())
    if a == b:
        return 0
    if abs(a - b) >= x:
        return 1
    if r - max(a, b) >= x or min(a, b) - l >= x:
        return 2
    if r - b >= x and a - l >= x or r - a >= x and b - l >= x:
        return 3
    return -1


t = int(input())
for _ in range(t):
    print(solve())

Suppose we are trying to find out the minimum time to get the hands from vertices 1 and k to the same vertex. If both hands end up on some vertex $$$v$$$, then the time required is $$$d(1,v)+d(k,v)$$$, with $$$d(x,y)$$$ being the minimum distance to go from vertex $$$x$$$ to $$$y$$$. Suppose $$$d′(x,y)$$$ is the minimum distance to go from vertex $$$x$$$ to $$$y$$$ in the reversed graph (i.e. all edges' directions are reversed). Then $$$d(1,v)+d(k,v)=d(1,v)+d′(v,k)$$$.

The minimum time if both hands are initially on vertices $$$1$$$ and $$$k$$$ is the minimum value of $$$d(1,v)+d′(v,k)$$$ for all vertices $$$v$$$. This is the same as the minimum distance to go from vertex $$$1$$$ to $k$where in the middle of our path, we can reverse the graph at most once.

Therefore we can set up a graph like the following:

Each vertex is a pair $$$(x,b)$$$, where x is a vertex in the original graph and $$$b$$$ is a boolean determining whether we have already reversed the graph or not. For each edge $$$i$$$ in the original graph, there is an edge from $$$(Ui,0)$$$ to $$$(Vi,0)$$$ and an edge from $$$(Vi,1)$$$ to $$$(Ui,1)$$$, both with weight $$$Wi$$$ . For each vertex $$$x$$$ in the original graph, there is a edge from $$$(x,0)$$$ to $$$(x,1)$$$ with weight $$$0$$$.

After this, we do the Dijkstra algorithm once on the new graph from vertex $$$(1,0)$$$ . Then, the optimal time if both hands start from vertices $$$1$$$ and $$$k$$$ in the original graph is equal to $d((1,0),(k,1))$in the new graph.

Time complexity: $$$O(N+MlogM)$$$

from collections import defaultdict
from heapq import heapify, heappop, heappush
from sys import stdin


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

N, M = map(int, input().split())
adj = defaultdict(list)

for _ in range(M):
   u, v, w = map(int, input().split())
   u -= 1
   v -= 1
   adj[u].append((v, w))
   adj[v + N].append((u + N, w))
for i in range(N):
   adj[i].append((i + N, 0))

dist = [float('inf')]*(2*N)
visited = [False]*(2*N)
dist[0] = 0
pq = [(0, 0)]
while pq:
   d, v = heappop(pq)
   if visited[v]:
       continue
   visited[v] = True
   for ch, w in adj[v]:
       new_d = d + w
       if new_d < dist[ch]:
           dist[ch] = new_d
           heappush(pq, (new_d, ch))

for i in range(N + 1, 2*N):
   if dist[i] == float('inf'):
       print("-1", end=" ")
   else:
       print(dist[i], end=" ")

In this problem we will find the sought quantity for every vertex and find the maximum value. For this for every vertex $$$v$$$ count two values: $$$cnt1[v]$$$ and $$$cnt2[v]$$$ — number of shortest paths from vertex $$$v$$$ to $$$n$$$-th and $$$1$$$-st vertices respectively. For this you should construct graph of shortest paths and use dynamic programming on the constructed graph (because the new graph will be acyclic). To construct the graph of shortest paths you should leave only useful edges in original graph. It can be done, for example, using breadth-first search launched from vertices $$$1$$$ and $$$n$$$ respectively.

After values $$$cnt1[v]$$$ and $$$cnt2[v]$$$ are found consider every useful edge $$$(u, v)$$$ and add to vertices $$$u$$$ and $$$v$$$ value $$$(cnt2[u] * cnt1[v]) / (cnt2[n–1])$$$, which is the contribution of this edge in the sought quantity for the vertices $$$u$$$ and $$$v$$$. Note that value $$$(cnt2[n–1])$$$ is the number of shortest paths between $$$1$$$ and $$$n$$$. All said values can be found in time $$$O(N + M)$$$. The complexity of solution is $$$O(N + M)$$$.

from collections import deque, defaultdict

def solve():
    n, m = map(int, input().split())
    g = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)

    que = deque([1])
    vis = [-1] * (n + 1)
    visr = [-1] * (n + 1)
    ways = [0] * (n + 1)
    waysr = [0] * (n + 1)
    
    vis[1] = 0
    ways[1] = 1
    dis = 1
    
    while que:
        cur_s = len(que)
        for _ in range(cur_s):
            node = que.popleft()
            for child in g[node]:
                if vis[child] == -1:
                    que.append(child)
                    vis[child] = dis
                    ways[child] = ways[node]
                elif dis == vis[child]:
                    ways[child] += ways[node]
        dis += 1

    que.append(n)
    dis = 1
    visr[n] = 0
    waysr[n] = 1
    
    while que:
        cur_s = len(que)
        for _ in range(cur_s):
            node = que.popleft()
            for child in g[node]:
                if visr[child] == -1:
                    que.append(child)
                    visr[child] = dis
                    waysr[child] = waysr[node]
                elif dis == visr[child]:
                    waysr[child] += waysr[node]
        dis += 1
    
    ans = 1.0
    div = vis[n]
    
    for i in range(2, n):
        cur_total = 0
        for child in g[i]:
            if vis[i] + visr[child] + 1 == vis[n]:
                cur_total += ways[i] * waysr[child]
        
        ans = max(ans, (cur_total / ways[n]) * 2)
    
    print(ans)

if __name__ == "__main__":
    solve()