Universal Cup Judging System

Universal Cup

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

Operator sieci komórkowej oferuje następującą promocję: każdy nowy klient może wybrać dokładnie $k$ innych numerów telefonów, a wszystkie połączenia pomiędzy klientem a dowolnym z $k$ wybranych kontaktów są darmowe (w obu kierunkach).

Grupa $n$ studentów (ponumerowanych od $1$ do $n$) chce skorzystać z tej promocji. Każdy student $i$ musi wybrać dokładnie $k$ różnych kontaktów ze zbioru $\{1, 2, \dots, n\} \setminus \{i\}$.

Mówimy, że dwaj studenci $i$ oraz $j$ mogą rozmawiać za darmo, jeśli zachodzi co najmniej jeden z poniższych warunków:

  • $i$ wybrał $j$ jako jeden z darmowych kontaktów, lub
  • $j$ wybrał $i$ jako jeden z darmowych kontaktów.

Studenci chcą wybrać swoje darmowe kontakty tak, aby każdy student mógł rozmawiać z każdym innym studentem za darmo, tzn. dla każdej pary $(i, j)$ spełniającej $1 \le i < j \le n$ studenci $i$ oraz $j$ mogą rozmawiać za darmo.

Dla danego $k$ Twoim zadaniem jest:

  • wyznaczyć maksymalną możliwą liczbę $n$ studentów, dla której taka konfiguracja jest możliwa,
  • skonstruować jedną poprawną konfigurację wybranych kontaktów dla tego maksymalnego $n$.

Wejście

Wejście składa się z jednej liczby całkowitej $k$.

Wyjście

W pierwszym wierszu wypisz jedną liczbę całkowitą $n$ — maksymalną liczbę studentów, dla której możliwe jest wybranie darmowych kontaktów tak, aby dowolnych dwóch studentów mogło rozmawiać ze sobą za darmo.

W kolejnych $n$ wierszach wypisz po $k$ darmowych kontaktów wybranych przez każdego studenta: w wierszu $i+1$ (dla $1 \le i \le n$) wypisz $k$ różnych liczb całkowitych $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. Każde $a_{i,j}$ musi spełniać $1 \le a_{i,j} \le n$ oraz $a_{i,j} \neq i$. Wiersze te oznaczają, że student $i$ wybrał studentów $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ jako swoje darmowe kontakty.

Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.

Ograniczenia

  • $1 \le k \le 1000$.

Przykład 1

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

Uwagi

W przykładzie $k = 2$, a maksymalna liczba studentów, dla której możliwe jest wybranie darmowych kontaktów tak, aby dowolnych dwóch studentów mogło rozmawiać ze sobą za darmo, wynosi $n = 5$. Dla każdej pary różnych studentów co najmniej jeden z nich wybrał drugiego, więc dowolnych dwóch może rozmawiać za darmo.

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.