Let's Play the Hat? (Codeforces 1619F)
Tags: Greedy, brute force

The Hat is a game of speedy explanation/guessing words (similar to Alias). It's fun. Try it! In this problem, we are talking about a variant of the game when the players are sitting at the table and everyone plays individually (i.e. not teams, but individual gamers play).$$$n$$$ people gathered in a room with $$$m$$$ tables ($$$n \ge 2m$$$). They want to play the Hat $$$k$$$ times. Thus, $$$k$$$ games will be played at each table. Each player will play in $$$k$$$ games.To do this, they are distributed among the tables for each game. During each game, one player plays at exactly one table. A player can play at different tables.Players want to have the most "fair" schedule of games. For this reason, they are looking for a schedule (table distribution for each game) such that:  At any table in each game there are either $$$\lfloor\frac{n}{m}\rfloor$$$ people or $$$\lceil\frac{n}{m}\rceil$$$ people (that is, either $$$n/m$$$ rounded down, or $$$n/m$$$ rounded up). Different numbers of people can play different games at the same table. Let's calculate for each player the value $$$b_i$$$ — the number of times the $$$i$$$-th player played at a table with $$$\lceil\frac{n}{m}\rceil$$$ persons ($$$n/m$$$ rounded up). Any two values of $$$b_i$$$must differ by no more than $$$1$$$. In other words, for any two players $$$i$$$ and $$$j$$$, it must be true $$$|b_i - b_j| \le 1$$$. For example, if $$$n=5$$$, $$$m=2$$$ and $$$k=2$$$, then at the request of the first item either two players or three players should play at each table. Consider the following schedules:  First game: $$$1, 2, 3$$$ are played at the first table, and $$$4, 5$$$ at the second one. The second game: at the first table they play $$$5, 1$$$, and at the second  — $$$2, 3, 4$$$. This schedule is not "fair" since $$$b_2=2$$$ (the second player played twice at a big table) and $$$b_5=0$$$ (the fifth player did not play at a big table). First game: $$$1, 2, 3$$$ are played at the first table, and $$$4, 5$$$ at the second one. The second game: at the first table they play $$$4, 5, 2$$$, and at the second one  — $$$1, 3$$$. This schedule is "fair": $$$b=[1,2,1,1,1]$$$ (any two values of $$$b_i$$$ differ by no more than $$$1$$$). Find any "fair" game schedule for $$$n$$$ people if they play on the $$$m$$$ tables of $$$k$$$ games.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.Each test case consists of one line that contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 2\cdot10^5$$$, $$$1 \le m \le \lfloor\frac{n}{2}\rfloor$$$, $$$1 \le k \le 10^5$$$) — the number of people, tables and games, respectively.It is guaranteed that the sum of $$$nk$$$ ($$$n$$$ multiplied by $$$k$$$) over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case print a required schedule  — a sequence of $$$k$$$ blocks of $$$m$$$ lines. Each block corresponds to one game, a line in a block corresponds to one table. In each line print the number of players at the table and the indices of the players (numbers from $$$1$$$ to $$$n$$$) who should play at this table.If there are several required schedules, then output any of them. We can show that a valid solution always exists.You can output additional blank lines to separate responses to different sets of inputs.


Sample Inputs:
3
5 2 2
8 3 1
2 1 3

Sample Outputs:
3 1 2 3
2 4 5
3 4 5 2
2 1 3

2 6 2
3 3 5 1
3 4 7 8

2 2 1
2 2 1
2 2 1

Solution (Python):
import math
result = []
for _ in range(int(input())):
    (n, m, k) = list(map(int, input().split()))
    (table1_cap, table2_cap) = (n // m, math.ceil(n / m))
    (tables1, tables2) = (m - (n - m * table1_cap), n - m * table1_cap)
    answer = []
    c_index_addition = 0
    for i in range(k):
        c_index = 0
        for j in range(tables1):
            answer.append([table1_cap] + [u % n + 1 for u in range(c_index_addition + c_index, c_index_addition + c_index + table1_cap)])
            c_index = (c_index + table1_cap) % n
        for j in range(tables2):
            answer.append([table2_cap] + [u % n + 1 for u in range(c_index_addition + c_index, c_index_addition + c_index + table2_cap)])
            c_index = (c_index + table2_cap) % n
        c_index_addition = (c_index_addition + table1_cap * tables1) % n
    result.append('\n'.join(map(lambda x: ' '.join(map(str, x)), answer)))
print('\n \n'.join(result))

Solution (Python):
t = int(input())
for case in range(t):
    (n, m, k) = tuple(map(int, input().split()))
    p = n // m
    q = p + 1
    r = n % m
    nouveau_indice = 1
    for i in range(k):
        indice = nouveau_indice
        for j in range(m):
            if j < r:
                s = str(q)
                for u in range(q):
                    s += ' ' + str(indice)
                    indice += 1
                    if indice == n + 1:
                        indice = 1
                print(s)
            else:
                if j == r:
                    nouveau_indice = indice
                s = str(p)
                for u in range(p):
                    s += ' ' + str(indice)
                    indice += 1
                    if indice == n + 1:
                        indice = 1
                print(s)
    print('')

Solution (Python):
import sys

def read_line():
    return sys.stdin.readline().strip()

def print_table(nums):
    print(f"{len(nums)} {' '.join([str(x) for x in nums])}")
t = int(read_line())
for _ in range(t):
    (n, m, k) = tuple([int(x) for x in read_line().split()])
    big_tables_starting_num = 0
    big_tables_count = n % m
    big_tables_size = 1 + n // m
    small_tables_count = m - n % m
    small_tables_size = n // m
    people_at_big_tables = big_tables_size * big_tables_count
    big_table_nums = [-1] * big_tables_size
    small_table_nums = [-1] * small_tables_size
    for _ in range(k):
        i = 0
        for bt in range(big_tables_count):
            for x in range(1 + n // m):
                big_table_nums[x] = (big_tables_starting_num + i) % n + 1
                i += 1
            print_table(big_table_nums)
        for st in range(small_tables_count):
            for x in range(n // m):
                small_table_nums[x] = (big_tables_starting_num + i) % n + 1
                i += 1
            print_table(small_table_nums)
        big_tables_starting_num = (big_tables_starting_num + people_at_big_tables) % n
    print()