레이팅 미적용베시는 \(x+0.5\)라는 수를 알고 있다. 여기서 \(x\)는 \(0\) 이상 \(N\) 이하의 어떤 정수이다(\(1\le N\le 2 \cdot 10^5\)).
엘시는 이 수를 맞히려 하고 있다. 엘시는 \(1\) 이상 \(N\) 이하의 어떤 정수 \(i\)에 대해 "\(i\)는 높은가 낮은가?" 형태의 질문을 할 수 있다. 베시는 \(i\)가 \(x+0.5\)보다 크면 "HI", \(i\)가 \(x+0.5\)보다 작으면 "LO"라고 답한다.
엘시는 베시의 수를 맞히기 위해 다음 전략을 세운다. 추측을 시작하기 전에, 엘시는 \(1\)부터 \(N\)까지의 모든 수가 정확히 한 번씩 등장하는 \(N\)개의 수의 목록을 만든다(다시 말해, 이 목록은 크기 \(N\)의 순열이다). 그런 다음 목록을 따라가며 목록에 등장하는 순서대로 수를 추측한다.
다만, 엘시는 불필요한 추측은 건너뛴다. 즉, 엘시가 어떤 수 \(i\)를 추측하려고 할 때 이전에 어떤 \(j < i\)를 추측했고 베시가 "HI"라고 답했다면, 엘시는 \(i\)를 추측하지 않고 목록의 다음 수로 넘어간다. 마찬가지로, 어떤 수 \(i\)를 추측하려고 할 때 이전에 어떤 \(j > i\)를 추측했고 베시가 "LO"라고 답했다면, 엘시는 \(i\)를 추측하지 않고 목록의 다음 수로 넘어간다. 이 전략을 사용하면 엘시가 어떤 순열을 만들더라도 항상 \(x\)를 유일하게 결정할 수 있음을 증명할 수 있다.
베시의 "HI" 또는 "LO" 응답을 모두 이어붙여 하나의 문자열 \(S\)를 만들었을 때, 베시가 "HILO"라고 말한 횟수는 \(S\)의 길이 \(4\)인 부분 문자열 중 "HILO"와 같은 것의 개수이다.
베시는 엘시가 이 전략을 사용할 것임을 알고 있다. 게다가 엘시가 사용할 정확한 순열도 알고 있다. 하지만 베시는 어떤 \(x\) 값을 선택할지 아직 정하지 않았다.
각 \(x\) 값에 대해 베시가 "HILO"를 몇 번 말하게 되는지 구하도록 도와주자.
출제자: Richard Qi
배점
- 테스트 1-4는 \(N \leq 5000\)을 만족한다.
- 테스트 5-8은 균등하게 무작위로 생성된 순열이다.
- 테스트 9-20은 추가 제약이 없다.
출제자: Richard Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 엘시의 크기 \(N\)인 순열이 주어진다.
\(0\)부터 \(N\)까지의 각 \(x\)에 대해, 베시가 HILO를 말하는 횟수를 한 줄에 하나씩 출력한다.
5
5 1 2 4 30
1
1
2
1
0For \(x=0\), Bessie will say "HIHI," for a total of zero "HILO"s.
For \(x=2\), Bessie will say "HILOLOHIHI," for a total of one "HILO".
For \(x=3\), Bessie will say "HILOLOHILO", for a total of two "HILO"s.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Gold