| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 124 | 32 | 29 | 34.940% |
Huynh은 무한한 길이의 수직선 위에 서있다. 수직선에는 $K$개의 장애물이 있다. $i$ 번째 장애물은 수직선의 원점으로부터 $A_i$ 미터 오른쪽에 있다. 모든 장애물의 위치는 다르다.
Huynh은 다음과 같은 질문을 해결하려 한다.
Huynh은 현재 수직선의 원점으로부터 $P$미터 오른쪽에 서 있다. 이후 Huynh은 $T$초간 매 초 1번씩, 오른쪽으로 1미터 움직이거나 왼쪽으로 1미터씩 움직이려 한다. 단, 장애물이 있는 위치로는 이동할 수 없다. $T$초 뒤, Huynh이 있을 수 있는 위치의 가짓수를 구하여라.
서로 다른 $T, P$ 값들에 대한 질문이 여럿 주어졌을 때, 모든 질문을 해결하라.
첫번째 줄에, 수직선에 있는 장애물의 개수 $K$가 주어진다.
두번째 줄에, 수직선에 있는 각 장애물의 위치 $A_1, \cdots, A_K$가 공백을 사이에 두고 주어진다.
세번째 줄에, 질문의 개수 $Q$가 주어진다.
이후 $Q$개의 줄에, 각 질문에서의 $T$와 $P$의 값이 공백을 사이에 두고 주어진다.
$Q$개의 줄에 걸쳐 출력한다. $i$ ($1 \le i \le Q$)번째 줄에는 $i$번째 질문의 답을 출력한다.
$K = 0$.
$K = 1$.
모든 질문에 대해 $T = 1$.
$K \le 2\,000$, $Q \le 2\,000$.
추가 제약 조건 없음.
4 -10 4 7 15 5 2 0 4 5 3 17 10 10 10 100
3 1 3 4 11
첫 번째 질문에서 Huynh은 원점에 서 있고, 2번 움직일 것이다.
Huynh이 있을 수 있는 위치는 위와 같이 세 가지이다.
두 번째 질문에서 Huynh은 원점으로부터 5미터 오른쪽에 서 있고, 4번 움직일 것이다.
Huynh은 네 번 움직인 다음 무조건 원점으로부터 5미터 오른쪽에 있게 된다. 따라서, Huynh이 있을 수 있는 위치는 1가지 존재한다.