레이팅 미적용*참고: 이 문제의 시간 제한은 기본의 두 배인 4초이다.*
음머! 정수 \(N\)(\(2\le N\le 2000\))이 주어진다. \([0,1,2\dots, N-1]\)의 모든 순열 \(p=[p_0,p_1,\dots, p_{N-1}]\)을 생각하자. \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\)를 \(p\)의 연속한 두 원소 사이의 절대 차이의 최솟값이라 하고, \(S\)를 \(f(p)\)의 최댓값을 달성하는 모든 \(p\)의 집합이라 하자.
추가로 \(p_i=j\)(\(0\le i,j
문제 제공: Benjamin Qi
배점
- 입력 5: \(N=15\)
- 입력 6: \(N=2000\)
- 입력 7-9: 모든 테스트 케이스에 제약 \(p_0=\lfloor N/2\rfloor\)가 나타난다.
- 입력 10-13: 모든 테스트 케이스에 \(j\)가 \(\lfloor N/2\rfloor\)와 같은 제약 \(p_i = j\)가 존재한다.
- 입력 14-20: 추가 제약 없음.
문제 제공: Benjamin Qi
첫째 줄에 \(T\)(\(1\le TN\le 2\cdot 10^4\))와 \(N\)이 주어진다. 즉, 각각 서로 다른 제약 집합으로 주어지는 \(T\)개의 독립적인 테스트 케이스를 풀어야 한다.
각 테스트 케이스는 \(K\)로 시작하고, 이어지는 \(K\)개의 줄에 \(i\)와 \(j\)가 각각 주어진다. 다음이 보장된다.
- 같은 테스트 케이스 안에서 같은 \(i\)는 두 번 이상 나타나지 않는다.
- 같은 테스트 케이스 안에서 같은 \(j\)는 두 번 이상 나타나지 않는다.
각 테스트 케이스에 대해, 답을 \(10^9+7\)로 나눈 나머지를 한 줄에 출력한다.
3 4
0
1
1 1
2
0 2
2 32
0
1The maximum possible value of \(f(p)\) is \(2\), and \(S=\{[2,0,3,1], [1,3,0,2]\}\).
9 11
2
0 5
6 9
3
0 5
6 9
1 0
4
0 5
6 9
1 0
4 7
5
0 5
6 9
1 0
4 7
2 6
6
0 5
6 9
1 0
4 7
2 6
9 3
7
0 5
6 9
1 0
4 7
2 6
9 3
5 2
8
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
9
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
10
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
8 106
6
1
1
1
1
1
1
1\(p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]\) should be counted for all test cases.
10 11
0
1
3 8
2
3 8
5 7
3
3 8
5 7
4 2
4
3 8
5 7
4 2
10 6
5
3 8
5 7
4 2
10 6
8 10
6
3 8
5 7
4 2
10 6
8 10
1 9
7
3 8
5 7
4 2
10 6
8 10
1 9
7 5
8
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
9
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
6 0160
20
8
7
2
1
1
1
1
1\(p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]\) should be counted for all test cases.
5 987
3
654 321
543 210
432 106
2
654 321
543 210
1
654 321
1
0 493
00
538184948
693625420
932738155
251798971Make sure to output the answer modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Platinum