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())

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()