#_. League

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

League

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

n 个人进行 n(n−1)2\frac {n(n -1)} {2} 场比赛，每个人都要以一个特定的顺序与其他人比赛。

且每个人每天只可以比一场比赛，问最少比赛的天数为多少，无解输出 −1-1 。

题目描述

N N 人の選手がテニスの大会に参加します。彼らを選手 1 1 、選手 2 2 、… \ldots 、選手 N N と呼びます。

大会は総当たり戦で、合計 N(N−1)/2 N(N-1)/2 試合が行われます。 これらの試合の日程を、以下の条件をすべて満たすように決めることは可能でしょうか。可能である場合、必要な最小の日数も求めてください。

  • 各選手は一日に最大で一試合を行う。
  • 各選手 i i (1 ≤ i ≤ N) (1\ \leq\ i\ \leq\ N) は、選手 Ai, 1, Ai, 2, …, Ai, N−1 A_{i,\ 1},\ A_{i,\ 2},\ \ldots,\ A_{i,\ N-1} とこの順に一度ずつ試合を行う。

输入格式

入力は以下の形式で標準入力から与えられる。

N N A1, 1 A_{1,\ 1} A1, 2 A_{1,\ 2} … \ldots A1, N−1 A_{1,\ N-1} A2, 1 A_{2,\ 1} A2, 2 A_{2,\ 2} … \ldots A2, N−1 A_{2,\ N-1} : : AN, 1 A_{N,\ 1} AN, 2 A_{N,\ 2} … \ldots AN, N−1 A_{N,\ N-1}

输出格式

条件をすべて満たすように全試合の日程を決めることが可能なら必要な最小の日数を、不可能なら -1 を出力せよ。

样例 #1

样例输入 #1

3
2 3
1 3
1 2

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

4

样例 #3

样例输入 #3

3
2 3
3 1
1 2

样例输出 #3

-1

提示

制約

  • 3 ≤ N ≤ 1000 3\ \leq\ N\ \leq\ 1000
  • 1 ≤ Ai, j ≤ N 1\ \leq\ A_{i,\ j}\ \leq\ N
  • Ai, j ≠ i A_{i,\ j}\ \neq\ i
  • Ai, 1, Ai, 2, …, Ai, N−1 A_{i,\ 1},\ A_{i,\ 2},\ \ldots,\ A_{i,\ N-1} はすべて異なる。

Sample Explanation 1

3 3 日間で次のように試合を行えばすべての条件を満たせます。 - 1 1 日目: 選手 1 1 対 選手 2 2 - 2 2 日目: 選手 1 1 対 選手 3 3 - 3 3 日目: 選手 2 2 対 選手 3 3 これが必要な最小日数です。

Sample Explanation 2

4 4 日間で次のように試合を行えばすべての条件を満たせます。 - 1 1 日目: 選手 1 1 対 選手 2 2 、選手 3 3 対 選手 4 4 - 2 2 日目: 選手 1 1 対 選手 3 3 - 3 3 日目: 選手 1 1 対 選手 4 4 、選手 2 2 対 選手 3 3 - 4 4 日目: 選手 2 2 対 選手 4 4 これが必要な最小日数です。

Sample Explanation 3

どのような日程で試合を行っても何らかの条件に違反します。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 31ms
  • Powered by Hydro v4.9.27 Community