RiseOJ – 소들의 원

설명

농부 존은 둘레가 $$C$$ 인 원 위의 서로 다른 위치 $l_1,\dots, l_N$ 에 있는 $$N$$ ( $2\le N\le 1000$ )마리의 소를 가지고 있다 ( $\(0\le l_1 < l_2 < \dots < l_N ).$

농부 존은 $$k$$ 쌍의 소를 선택할 것인데, 여기서 $1\le k\le \lfloor N/2\rfloor$ 이고 어떤 소도 두 번 이상 선택되지 않는다. 그는 같은 쌍에 속한 두 소 사이의 원 둘레를 따라 잰 거리의 최솟값이 최대가 되도록 쌍들을 선택하고 싶다.

각 $$k$$ 값에 대해, 가능한 최소 거리의 최댓값을 구하는 것을 도와주자.

문제 제공: Benjamin Qi

제약

채점 방식

입력 3-4: $2l_N \le C$
입력 5-6: $N\le 20$
입력 7-14: $N\le 100$
입력 15-22: 추가 제약 조건이 없다.

문제 제공: Benjamin Qi

입력 형식

첫째 줄에 $$N$$ 과 $$C$$ 가 주어진다.

둘째 줄에 $l_1\dots l_N$ 이 주어진다.

출력 형식

$k=1\dots \lfloor N/2\rfloor$ 순서대로의 답인 $\lfloor N/2\rfloor$ 개의 정수를 공백으로 구분하여 한 줄에 출력한다.

예제 1

입력

4 100
0 25 50 75

출력

50 50

설명

For $$k = 1$$ , cow 1 can be paired to cow 3, which is distance $$50$$ away along the
circumference of the circle, making the answer $$50$$ .

For $$k = 2$$ , cow 1 can be paired to cow 3, and cow 2 can be paired to cow 4,
which is distance $$50$$ away from it along the circumference of the circle,
making the answer still $$50$$ .

예제 2

입력

4 100
0 1 2 99

출력

3 2

설명

For $$k = 1$$ , cow 3 can be paired to cow 4, which is distance $$2 + 100 - 99 = 3$$
away from it along the circumference of the circle, making the answer $$3$$ .

For $$k = 2$$ , cow 1 can be paired to cow 3 and cow 2 can be paired to cow 4. Each
of these pairs contains two cows at a distance of $$2$$ from each other along the
circumference of the circle, making the answer $$2$$ .

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > Second Contest > Platinum

올림피아드 > USACO > 2025-2026 > Second Contest > Platinum

태그

JudgeUSACO

소들의 원

평가 및 의견

풀이 제출