루미 알고리즘

#1116골드거울거울

KOI 2025 2차코딩초등부 2번, 중등부 1번출제 반딧불이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

거울

원제: 거울

문제

당신은 수직선 위에서 게임을 하고 있다. 당신의 캐릭터는 위치 ss에 있으며, 수직선 위에는 NN개의 거울이 배치되어 있다. 각 거울의 위치는 왼쪽부터 A1≤A2≤⋯≤ANA_1 \le A_2 \le \cdots \le A_N으로 나타낼 수 있다. 한 위치에 여러 개의 거울이 있을 수도 있다.

당신은 거울을 사용해 캐릭터의 위치를 바꿀 수 있다. 이때, 거울을 사용하면 캐릭터의 위치는 거울을 기준으로 점대칭인 지점으로 이동한다. 즉, 당신의 캐릭터가 위치 aa에 있을 때 위치 bb에 있는 거울을 사용하면 당신의 캐릭터는 위치 2b−a2b - a로 이동한다.

NN 개의 거울은 정확히 한 번씩 사용되어야 한다. 즉, 한 거울을 사용하지 않고 무시할 수는 없으며, 한 거울을 두 번 이상 사용할 수도 없다. 각 거울을 모두 정확히 한 번씩 사용해야 하는 것을 제외하고는, 거울은 당신이 원하는 아무 순서대로 사용할 수 있다.

당신은 이 조건하에서 캐릭터의 위치의 최댓값을 계산하여 출력해야 한다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤200 0001 \le N \le 200\,000
  • −109≤s≤109-10^9 \le s \le 10^9
  • −109≤A1≤A2≤⋯≤AN≤109-10^9 \le A_1 \le A_2 \le \cdots \le A_N \le 10^9

부분문제

  1. (7점) N≤2N \le 2.
  2. (25점) NN은 짝수, A1=A2=⋯=AN/2<s<AN/2+1=AN/2+2=⋯=ANA_1 = A_2 = \cdots = A_{N/2} < s < A_{N/2+1} = A_{N/2+2} = \cdots = A_N.
  3. (19점) NN은 짝수, AN/2<s<AN/2+1A_{N/2} < s < A_{N/2+1}.
  4. (49점) 추가 제약 조건 없음.

입력 형식

첫째 줄에는 거울의 수 NN과 당신의 위치 ss가 공백으로 구분되어 주어진다.

둘째 줄에는 각 거울의 위치 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 주어진다.

출력 형식

NN개의 거울을 모두 정확히 한 번씩 사용했을 때 캐릭터의 최종 위치의 최댓값을 출력한다.

답이 커질 수 있으므로 일부 프로그래밍 언어에서는 64비트 정수 변수(long long)를 사용해야 할 수도 있음에 유의하라.

예제

예제 1

입력
2 0
-1 2
출력
6

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

11번 거울을 먼저 이용하고, 그다음에 22번 거울을 이용한다면, 위 그림처럼 캐릭터의 최종 위치는 66이 된다. 반면, 22번 거울을 먼저 이용하고, 그다음에 11번 거울을 이용한다면, 캐릭터의 최종 위치는 −6-6이 된다. 고로, 이 예시의 정답은 66 이 된다.

예제 2

입력
6 3
-4 -2 2 6 8 9
출력
57

예제 3

입력
9 9
0 1 3 3 4 5 8 9 10
출력
49

예제 4

입력
1 1000000000
-999999999
출력
-2999999998

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.