쇼핑
시간 제한2초메모리 제한256 MB
안나는 18비트 이하로 구간을 브루노에게 보내고, 브루노는 10000비트 이하로 답해 안나가 그 구간에서 가장 싼 물건을 알아내도록 통신 전략을 설계한다.
문제
JOI Store는 0번부터 N − 1번까지 번호가 붙은 N개의 상품을 판다. 상품 i (0 ≤ i ≤ N − 1)의 가격은 Pi이다. 모든 상품의 가격은 서로 다르다.
Anna는 JOI Store에 쇼핑을 하러 왔다. Anna는 번호가 L 이상 R 이하인 상품 중 가장 싼 상품을 사려고 한다. Anna는 각 상품의 가격을 모르므로, JOI Store의 점원 Bruno와 의사소통하여 어떤 상품을 살지 결정한다. Bruno는 모든 상품의 가격을 알지만 L과 R의 값은 모른다.
Anna와 Bruno는 통신 기기로 문자를 주고받는다. 주고받는 문자는 각각 0 또는 1이다. Anna는 Bruno에게 문자를 최대 18개 보낼 수 있고, Bruno는 Anna에게 문자를 최대 10 000개 보낼 수 있다. Bruno는 가능한 한 적은 문자를 보내려고 한다.
N, L, R의 값은 Anna에게 주어지고, N의 값과 각 상품의 가격은 Bruno에게 주어진다. Anna가 어떤 상품을 살지 결정할 수 있도록 Anna의 전략과 Bruno의 전략을 구현하는 프로그램을 작성하라.
입력
채점기는 표준 입력에서 다음 데이터를 읽는다.
N L R
P0 P1 · · · PN−1
출력
프로그램이 정상적으로 종료되면, 채점기는 표준 출력에 다음 정보를 출력한다(따옴표는 명확성을 위해 표기한 것이다).
- 답이 맞으면 Anna가 Bruno에게 보낸 문자의 총 개수 Y와 Bruno가 Anna에게 보낸 문자의 총 개수 X를 “
Accepted: Y X” 형식으로 출력한다. - 프로그램이 Wrong Answer로 판정되면 그 유형을 “
Wrong Answer [1]” 형식으로 출력한다. - 여러 유형의 Wrong Answer에 해당하는 경우, 채점기는 그중 하나만 보고한다.
제한
- 1 ≤ N ≤ 1 000 000.
- 0 ≤ L ≤ R ≤ N − 1.
- 1 ≤ Pi ≤ N (0 ≤ i ≤ N − 1).
- Pi ≠ Pj (0 ≤ i < j ≤ N − 1).