Introduction#

The goal is to distribute the hours of n singers in m shows. Each show has a number of hours equal to l (unknown) and can only change singers once. We also want that each singer will have the same time on stage.

Solution#

To solve this problem, I use a greedy strategy that iteratively divides the available singing time among the singers, ensuring that each singer fulfills their required hours.

1
T = int(input())
2

3
for _ in range(T):
4
    n, m = map(int, input().split(' '))
5
    l = n
6
    print(l)
7
    duration_for_singer = m
8
    singers = [duration_for_singer] * n
9
    for i in range(len(singers)):
10
        while singers[i] > 0:
11
            show = []
12
            if (singers[i] - l) >= 0:
13
                show.append((l//2, i+1))
14
                show.append((l - l//2, i+1))
15
                singers[i] -= l
16
            elif singers[i] < l:
17
                show.append((singers[i], i+1))
18
                show.append((l - singers[i], i+2))
19
                singers[i+1] -= l - singers[i]
20
                singers[i] = 0
21
            print(f"{show[0][0]} {show[0][1]} {show[1][0]} {show[1][1]}")

Step-by-Step Explanation#

1. Initialization

• The first input T represents the number of test cases.
• After some experimentation on pen and paper, I noticed that the minimum value of l is equal to the number of singers, so l is set to n.
• I initialize a list singers of length n, where each element is set to m to represent the remaining singing hours for each singer.

2. Time Distribution Logic

• I iterate over each singer using a loop. For each singer i, the following steps are performed:
  • While Loop: Continue allocating time to the current singer as long as they have hours remaining (singers[i] > 0).
  • Time Allocation:
    • If the current singer has l or more hours remaining, divide l hours into two chunks:
      • The first chunk is l//2 hours, and the second chunk is l - l//2 hours. Both chunks are allocated to the same singer.
      • Subtract l from the singer’s remaining hours.
    • If the current singer has less than l hours remaining:
      • Allocate all remaining hours to the current singer.
      • Allocate the rest of l to the next singer in line (i+2).
      • Subtract the hours from the next singer’s total.
  • Output:
    • After each allocation, the result is stored in a list show and printed in the format {hours1} {singer1} {hours2} {singer2}.

3. Output

• The program prints the number l as the first line for each test case.
• For each show, the specific distribution of hours between the singers is printed.

Example Execution#

1
4
2
2 1 2 1
3
3 1 1 2
4
2 2 2 2
5
2 2 2 3
6
2 3 2 3
7
1 3 3 4
8
2 4 2 4

Conclusion#

I don’t consider this challenge difficult, it’s just a greedy algorithm (it takes a lot more to scare a LeetCode boy), but it wasn’t immediately clear that the output didn’t necessarily have to be the same as that shown in the challenge’s PDF , but it was enough to fit the constraints of the problem.

flag: SEKAI{t1nyURL_th1s:_6d696b75766d}