레이팅 미적용베시는 대포알로 변신해 길이 \(N\) \((1 \leq N \leq 10^5)\)의 수직선 위를 튀어 다니는 기술을 완벽히 익혔다. 수직선의 위치에는 왼쪽부터 오른쪽으로 \(1,2,\dots,N\)의 번호가 붙어 있다. 베시는 어떤 정수 위치 \(S\) \((1 \leq S \leq N)\)에서 시작해 파워 \(1\)로 오른쪽으로 튀어 나간다. 베시의 파워가 \(k\)이면, 다음 도약은 현재 위치에서 진행 방향으로 거리 \(k\)만큼 떨어진 곳에 착지한다.
\(1\)부터 \(N\)까지의 모든 정수 위치는 표적이거나 점프대이다. 각 표적과 점프대는 \(0\) 이상 \(N\) 이하의 정수 값을 가진다. 값이 \(v\)인 점프대는 베시의 파워를 \(v\)만큼 증가시키고 방향을 반대로 바꾼다. 값이 \(v\)인 표적은 파워 \(v\) 이상으로 착지하면 부서진다. 표적에 착지해도 베시의 파워나 방향은 바뀌지 않는다. 한 번 부서진 표적은 계속 부서진 상태로 남으며, 베시는 그 위에서도 여전히 튈 수 있고 이때도 파워와 방향은 바뀌지 않는다.
베시가 무한히 튀거나 수직선을 벗어날 때까지 튄다면, 몇 개의 표적이 부서지는가?
베시가 부술 수 있는 표적 위에서 시작하면 즉시 그 표적을 부순다. 마찬가지로 점프대 위에서 시작하면 첫 도약 전에 점프대의 효과가 적용된다.
출제: Suhas Nagar
배점
- 입력 3-5: \(N \le 100\)
- 입력 6-10: \(N \le 1000\)
- 입력 11-20: 추가 제약 없음.
출제: Suhas Nagar
입력의 첫째 줄에 \(N\)과 \(S\)가 주어진다. \(N\)은 수직선의 길이, \(S\)는 베시의 시작 위치이다.
다음 \(N\)개의 줄에 각 위치에 대한 설명이 주어진다. 이 중 \(i\)번째 줄에는 정수 \(q_i\)와 \(v_i\)가 주어지는데, 위치 \(i\)가 점프대이면 \(q_i = 0\), 표적이면 \(q_i = 1\)이고, \(v_i\)는 위치 \(i\)의 값이다.
부서지는 표적의 개수를 나타내는 수 하나를 출력한다.
5 2
0 1
1 1
1 2
0 1
1 11Bessie starts at coordinate \(2\), which is a target of value \(1\), so she
immediately breaks it. She then bounces to coordinate \(3\), which is a target of
value \(2\), so she can't break it. She continues to coordinate \(4\), which
switches her direction and increases her power by \(1\) to \(2\). She bounces back
to coordinate \(2\), which is an already broken target, so she continues. At this
point, she bounces to coordinate \(0\), so she stops. She breaks exactly one
target at located at \(2\).
6 4
0 3
1 1
1 2
1 1
0 1
1 13The path Bessie takes is \(4\to 5\to 3\to 1\to 6\), where the next bounce would
take her out of the number line (\(11\)). She breaks targets \(4, 3, 6\) in that
order.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Bronze