예방접종 작전 timer 20s memory 2048MB

전 세계 인구에게 모든 백신을 제공하는 일은 여러 측면에서 매우 복잡한 문제이다. 냠비(Ñambi)는 배송을 최적화하기 위한 선봉에 서 있다. 접근 장벽을 최대한 줄이기 위해, 그녀는 자동 로봇이 환자의 집에서 직접 백신을 전달하고 접종까지 하도록 만들려고 한다.

현재 단계에서 냠비가 설계 중인 로봇은 서쪽에서 동쪽으로 뻗은 하나의 직선 도로에서만 동작한다. 따라서 로봇이 받는 명령은 오직 하나, 'move x meters'이다. x가 양수면 로봇은 동쪽으로 x미터 이동하고, x가 음수면 서쪽으로 -x미터 이동한다.

로봇은 하루가 시작될 때 그날 수행해야 하는 모든 접종 정보가 미리 로드되어 있다. 각 정보에는 백신을 집어야 하는 위치(픽업 위치)와, 그 백신을 전달해야 하는 환자의 위치(배송/전달 위치)가 들어 있다. 각 백신은 한 명의 환자를 위해 맞춤 제작된다. 물론 어떤 백신의 전달 위치는 그 백신의 픽업 위치와 결코 같지 않다. 로봇은 백신을 전달하기 전에 반드시 먼저 픽업해야 한다.

로봇은 백신의 픽업 위치를 처음으로 지나갈 때, 해당 백신을 자동으로 집어 화물칸에 싣도록 프로그램되어 있다. 또한 어떤 위치를 지나갈 때 그 위치가 어떤 백신의 전달 위치이고, 그 백신이 이미 픽업되어 있다면 즉시 그 백신을 전달하도록도 되어 있다. 냠비는 각 이동 명령 이후에 몇 번의 접종이 이루어지는지 추적하고 싶다. 접종은 백신이 전달되는 순간에 일어난다. 백신은 이전 명령들 중에 픽업되었을 수도 있고, 같은 명령의 수행 중(전달보다 먼저) 픽업되었을 수도 있다.

다음 그림은 가능한 한 가지 상황을 보여 준다(아래 Sample Case #1). 스마일 표시는 로봇의 초기 위치이고, 긴 검은 선이 도로를 나타낸다. 선 위의 표시들은 픽업 위치, 선 아래의 표시들은 전달 위치이다. 마지막으로, 아래의 화살표들은 로봇이 수행하는 이동들을 위에서 아래 순서대로 나타내며, 각 이동 중 완료되는 전달(접종)의 개수가 함께 표시되어 있다.

각 이동에서 일어나는 일은 다음과 같다.

• 이동 1. 로봇은 백신 5와 1을 픽업한 다음, 백신 1을 전달하고, 이동이 끝날 즈음에 백신 3을 픽업한다. 로봇은 백신 3의 전달 위치도 지나가지만, 그 지점은 백신 3을 픽업하기 전에 지나가므로 전달할 수 없다.
• 이동 2. 로봇은 백신 1과 4의 전달 위치를 지난다. 하지만 백신 1은 이미 전달되었고 백신 4는 아직 픽업되지 않았으므로, 완료되는 접종은 없다.
• 이동 3. 로봇이 백신 3을 전달한다.
• 이동 4. 로봇은 백신 2를 픽업하고, 백신 5를 전달한 뒤, 백신 4를 픽업한다.

백신 2와 4는 픽업되었지만 전달되지는 않았다는 점에 유의하라. 백신 2의 전달 위치는 끝까지 도달하지 못했고, 백신 4의 전달 위치는 해당 백신이 픽업된 이후에는 도달하지 못했기 때문이다.

주어지는 접종 목록과, 로봇이 순서대로 수행할 이동 명령들의 목록이 주어질 때, 각 명령을 수행하는 동안 완료되는 접종의 수를 계산하라.