Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 512 MB Total points: 100
Statistics

Une compagnie de téléphonie mobile propose la promotion suivante : chaque nouveau client peut choisir exactement $k$ autres numéros de téléphone et tous les appels entre le client et l'un quelconque des $k$ contacts choisis sont gratuits (dans les deux sens).

Un groupe de $n$ étudiants (numérotés de $1$ à $n$) souhaite profiter de cette promotion. Chaque étudiant $i$ doit choisir exactement $k$ contacts distincts dans l'ensemble $\{1, 2, \dots, n\} \setminus \{i\}$.

On dit que deux étudiants $i$ et $j$ peuvent se parler gratuitement si au moins l'une des conditions suivantes est vérifiée :

  • $i$ a choisi $j$ parmi ses contacts gratuits, ou
  • $j$ a choisi $i$ parmi ses contacts gratuits.

Les étudiants veulent choisir leurs contacts gratuits de sorte que n'importe quel étudiant puisse parler gratuitement à n'importe quel autre étudiant, c'est-à-dire que pour chaque paire $(i, j)$ telle que $1 \le i < j \le n$, les étudiants $i$ et $j$ puissent se parler gratuitement.

Pour un $k$ donné, votre tâche consiste à :

  • déterminer le nombre maximal possible $n$ d'étudiants pour lequel une telle configuration est possible,
  • construire une configuration valide de contacts choisis pour ce $n$ maximal.

Entrée

L'entrée consiste en un seul entier $k$.

Sortie

Sur la première ligne, affichez un seul entier $n$ — le nombre maximal d'étudiants pour lequel il est possible de choisir les contacts gratuits de sorte que deux étudiants quelconques puissent se parler gratuitement.

Sur les $n$ lignes suivantes, affichez les $k$ contacts gratuits choisis par chaque étudiant : sur la ligne $i+1$ (pour $1 \le i \le n$), affichez $k$ entiers distincts $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Chaque $a_{i,j}$ doit vérifier $1 \le a_{i,j} \le n$ et $a_{i,j} \neq i$. Ces lignes indiquent que l'étudiant $i$ a choisi les étudiants $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ comme contacts gratuits.

S'il existe plusieurs réponses valides, affichez n'importe laquelle d'entre elles.

Contraintes

  • $1 \le k \le 1000$.

Exemple 1

2
5
2 5
3 4
1 5
1 3
2 4

Notes

Dans l'exemple, $k = 2$ et le nombre maximal d'étudiants pour lequel il est possible de choisir les contacts gratuits de sorte que deux étudiants quelconques puissent se parler gratuitement est $n = 5$. Pour chaque paire d'étudiants distincts, au moins l'un des deux a choisi l'autre, donc deux étudiants quelconques peuvent se parler gratuitement.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.