24340번 - 가희와 btd5 2

가희는 하나의 라운드를 클리어하려고 합니다. 라운드를 클리어하기 위해 가희는 맵 내에 등장하는 풍선들을 막아야 합니다. [표 1]은 맵 내에 등장하는 풍선들을 나타냅니다.

[표 1] 스테이지에 나오는 풍선의 레벨과 특성

[표 1]에 등장하는 풍선의 종류는 네 종류입니다. 이 중, 레벨 1의 풍선과 레벨 2의 풍선은 데미지를 입으면 맵에서 사라집니다. 레벨 3의 풍선은 데미지를 입으면 빨간 풍선에 씌워진 납이 사라집니다. 레벨 4의 풍선은 데미지를 입으면 은신 빨간 풍선에 씌워진 은신 납이 사라집니다. 레벨이 2인 풍선과 4인 풍선은 은신 속성을 가집니다. 

가희는 저격수 원숭이만 이용해서 스테이지를 클리어하려고 합니다. 저격수 원숭이는 은신 속성이 있는 풍선을 제외한 모든 풍선을 볼 수 있으며, 날카로운 속성의 공격을 합니다. 그리고 공격할 때 하나의 풍선만 공격합니다. 저격수 원숭이가 배울 수 있는 스킬은 L1, R1 2가지가 있습니다. 스킬 L1, R1을 배웠을 때 얻을 수 있는 능력은 아래와 같습니다.

[표 2] 저격 원숭이가 배울 수 있는 스킬의 효과

예를 들어, L1과 R1 모두 배우지 않은 저격 원숭이는 날카로운 속성의 공격을 하므로 납이 씌워진 빨간 풍선을 공격해도 납이 없어지지 않습니다. 날카로운 속성은 납이 씌워진 빨간 풍선에 데미지를 입힐 수 없기 때문입니다. 반면 R1 스킬을 배운 저격 원숭이는 납이 씌워진 빨간 풍선에 데미지를 입혀서 납을 제거할 수 있습니다. 뜨거운 속성의 공격은 납이 씌워진 빨간 풍선에 데미지를 입힐 수 있기 때문입니다.

맵에는 물체들이 갈 수 있는 경로가 있습니다. 경로에 풍선들이 나오면, 경로의 입구부터 일련의 지점들을 거쳐 출구까지 가게 됩니다. 경로의 길이가 r_len이라면, 해당 경로의 지점 번호는 1번부터 r_len번까지 있습니다. 풍선이 x번 지점에 나타난 시간을 게임 시간 t_x초라고 하겠습니다. 

• x가 r_len인 경우 게임 시간 tx + 0.1초에 풍선이 맵에서 사라지게 됩니다.
• 그렇지 않으면 게임 시간 tx + 0.1초에 풍선이 x번 지점에서 사라지고 x+1번 지점에 나타나게 됩니다.

예를 들어 풍선이 (0, 1)에서 들어와서 (0, 2), (0, 3), (1, 3), (1, 2)를 거쳐 다시 (0, 2)로 간 다음에 경로가 끝난다고 생각해 보겠습니다. [표 3]은 이 경로의 지점 번호와 좌표를 나타냅니다.

[표 3] 문제에서 설명하는 경로와 경로의 지점 번호

이 경로에 빨간 풍선이 게임 시간 0.100초에 나타났다고 해 보겠습니다. 시간대별로 빨간 풍선의 위치는 [표 4]와 같습니다.

[표 4] 빨간 풍선이 각 지점에 있는 시간대

게임 시간 0.100초에 빨간 풍선이 경로에 나왔으므로, 1번 지점에 나타난 시간은 0.100초입니다. 6번 지점은 경로의 출구입니다. 따라서 게임 시간 0.700초에 빨간 풍선은 사라지게 됩니다.

경로의 길이가 r_len인 경로의 x번 지점에 id가 balloon_id인 풍선이 있을 때, 이 풍선의 출구로부터의 거리는 r_len-x이고, 입구로부터의 거리는 x-1입니다.

각각의 저격 원숭이들은 선택 우선순위가 있습니다. 선택 우선순위는 FIRST, LAST, STRONG 셋 중 하나입니다.

• FIRST인 경우, 자신이 볼 수 있는 풍선 중 출구에서부터 거리가 가장 짧은 풍선을 선택합니다. 그러한 것이 여러 개라면, 현재 풍선이 있는 지점에 가장 많은 시간 동안 있었던 풍선을 선택합니다. 그러한 것이 여러 개라면 balloon_id가 가장 작은 것을 선택합니다.
• LAST인 경우, 자신이 볼 수 있는 풍선 중 입구에서부터 거리가 가장 짧은 풍선을 선택합니다. 그러한 것이 여러 개라면, 현재 풍선이 있는 지점에 가장 적은 시간 동안 있었던 풍선을 선택합니다. 그러한 것이 여러 개라면 balloon_id가 가장 작은 것을 선택합니다.
• STRONG인 경우, 자신이 볼 수 있는 풍선 중 레벨이 가장 높은 풍선을 선택 합니다. 그러한 것이 여러 개라면 balloon_id가 가장 작은 것을 선택합니다.

예를 들어 1번 경로가 (0,1)에서 출발하여, (0,2), (0,1), (0,2), (0,1)를 거쳐 (1,1)에서 끝나고, 2번 경로가 (2,1)에서 출발하여 (2,2), (2,3), (2,4), (2,5)를 거쳐 (2,6)에서 끝난다고 해 보겠습니다. 1번 경로와 2번 경로는 각각 6개의 지점을 거치게 됩니다. id가 2인 풍선이 2번 경로에 게임 시간 0.110초에 나타나고, id가 1인 풍선이 1번 경로에 게임 시간이 0.120초일 때 나타난다고 하겠습니다.

게임 시간이 0.550초일 때, id가 1인 풍선과 id가 2인 풍선은 각각 경로 1번의 5번 지점, 경로 2번의 5번 지점에 있게 됩니다. 이때, 선택 우선순위가 FIRST인 원숭이가 풍선을 선택하는 과정은 아래와 같습니다.

• 경로 1번의 5번 지점으로부터 출구까지 거리는 1, 경로 2번의 5번 지점에서 출구까지 거리는 1입니다. 즉 두 풍선은 출구로부터 거리가 같습니다.
• 1번 풍선은 경로 1번의 5번 지점에 0.030초 동안, 2번 풍선은 경로 2번의 5번 지점에 0.040초 동안 있었습니다.
• 현 위치에 더 오래 있었던 풍선은 id가 2번인 풍선이므로 선택 우선순위가 FIRST인 원숭이는 id가 2인 풍선을 선택합니다.

이때, 1번 풍선이 경로 1번의 5번 지점에 있었던 시간에는 경로 1번의 1번, 3번 지점에 있었던 시간을 합산하지 않습니다.

스테이지가 시작되면 게임 시스템은 아래와 같이 동작합니다.

• 풍선이 맵에 등장하는 이벤트와 공격 명령이 동시에 주어지면, 풍선이 맵에 등장하는 이벤트가 먼저 실행됩니다.
• 게임 시간 monkey_id × 0.001초에 id가 monkey_id인 저격 원숭이에게 처음 공격 명령을 내리게 됩니다.
  • id가 monkey_id인 저격 원숭이가 있다면, 그 원숭이는 풍선을 선택하고, 선택한 풍선을 즉시 공격합니다.
  • id가 monkey_id인 저격 원숭이가 없다면 해당 명령은 무시됩니다.
• id가 monkey_id인 저격 원숭이에게 공격하라는 명령은 1초 간격으로 이루어지게 됩니다.

예를 들어 id가 500인 저격 원숭이에게 공격하라는 명령은 게임 시간 0.500초, 1.500초, 2.500초, ... 후에 발동되게 됩니다.

가희는 풍선이 데미지를 입았을 때, 어느 저격 원숭이가 데미지를 주었는지 알고 싶어 합니다. 가희를 도와주세요.

첫 줄에 경로의 개수 R과 스테이지 시작 전에 있었던 저격 원숭이의 수 U가 공백으로 구분되어 주어집니다. 경로의 개수는 1개 이상 10개 이하이고, 스테이지 시작 전에 저격 원숭이의 수는 1마리보다 많거나 같고, 10³마리보다 작거나 같습니다.

두 번째 줄에는 R개의 정수가 공백을 구분으로 해서 주어집니다. 이때 x번째 정수는 id가 x인 경로가 몇 개의 지점을 거치는지를 나타냅니다.

다음 R개의 줄에 걸쳐 route_id가 1인 경로부터 route_id가 R인 경로까지 경로에 대한 정보가 한 줄에 하나씩 차례대로 주어집니다.

x번째 경로가 지점 r_x개를 거쳐 간다면, 1번 지점부터 r_x번 지점까지 순서대로 공백으로 구분되어 주어지며, 지점 정보는 아래와 같은 포맷으로 주어집니다.

(정수,정수)

각 경로는 5개 이상 500개 이하의 지점을 거치게 되며, 맵에 등장하는 지점 개수는 3×10³개 이하입니다. 모든 지점의 x 좌표와 y 좌표는 0 이상 10³이하의 정수입니다.

다음 U개의 줄에는 저격 원숭이에 대한 정보인 monkey_id, upgrade_status, select_priority가 공백으로 구분되어 주어집니다. monkey_id는 저격 원숭이의 id, upgrade_status는 저격 원숭이가 어떤 스킬들을 배웠는지, select_priority는 설정된 선택 우선순위를 의미합니다. upgrade_status는 -, L1, R1, L1R1중 하나이며, 각각 아무 스킬도 배우지 않은 상태, L1 스킬만 배운 상태, R1 스킬을 배운 상태, L1과 R1 스킬을 모두 배운 상태를 의미합니다.

그다음 줄에는 이벤트 개수 E가 주어집니다. 이벤트 개수는 1개 이상 5×10⁵개 이하입니다.

다음 E개의 줄에는 발생한 이벤트 목록이 시간 순서대로 주어집니다. 이벤트 목록에 대한 형식은 아래와 같습니다.

• s.T ADD monkey_id
  • 게임 시간 s.T초에 id가 monkey_id이고 아무런 스킬도 배우지 않은 저격 원숭이를 추가합니다. 이때 선택 우선순위는 FIRST로 설정됩니다.
• s.T UPGRADE monkey_id skill_name
  • 게임 시간 s.T초에 id가 monkey_id인 저격 원숭이는 스킬 이름이 skill_name인 스킬을 배웁니다. skill_name은 L1, R1 중 하나로 주어집니다.
• s.T REMOVE monkey_id
  • 게임 시간 s.T초에 id가 monkey_id인 저격 원숭이는 제거됩니다.
• s.T CHANGEPRIORITY monkey_id select_priority
  • 게임 시간 s.T초에 id가 monkey_id인 저격 원숭이의 선택 우선 순위를 select_priority로 설정합니다. select_priority는 FIRST, LAST, STRONG 중 하나로 주어집니다.
• s.T BALLOON balloon_name balloon_id route_id
  • 게임 시간 s.T초에 id가 balloon_id이고 영어 이름이 balloon_name인 풍선이 id가 route_id인 경로에 나옵니다.

풍선은 게임 시각 180.000초 이후에 나오지 않으며, 300.000초 이후의 이벤트는 주어지지 않습니다.

s.T 포맷에서 s는 0 이상의 정수로 주어지며, T는 0 이상 999 이하의 정수로 주어집니다. 이때 T가 두 자릿수라면 T 앞에 0 이, 한 자릿수라면 T 앞에 00 이 붙습니다. 이는, 게임 시간 s+T×10^-3초를 의미합니다.

풍선이 데미지를 입을 때마다 풍선의 id와 데미지를 준 저격 원숭이의 id를 공백으로 구분해서 출력해 주세요. 이때 발생한 시간순으로 출력해 주세요.

• 맵 안에 있는 저격 원숭이의 id는 1 이상 10³ 이하의 정수이며, 게임이 진행되는 도중에 id가 같은 둘 이상의 저격 원숭이가 존재하지 않습니다.
• 맵에 등장하는 풍선 id는 1 이상 10⁶ 이하의 정수로 주어지며, 같은 id의 풍선이 두 번 이상 나오지 않습니다.
• id가 monkey_id인 저격 원숭이가 없을 때, id가 monkey_id인 저격 원숭이를 업그레이드하거나, 제거하거나, 선택 우선순위를 바꾸는 이벤트는 주어지지 않습니다.
• id가 monkey_id인 저격 원숭이가 있을 때, id가 monkey_id인 저격 원숭이를 추가하는 이벤트는 주어지지 않습니다.
• 이미 배운 스킬을 또 배우는 이벤트는 주어지지 않습니다.
• 다음 이벤트는 같은 시각에 주어지지 않습니다.
  • id가 monkey_id인 저격 원숭이에 대한 이벤트와 id가 monkey_id인 저격 원숭이에게 공격 명령이 떨어지는 이벤트
  • id가 monkey_id인 저격 원숭이에 대한 둘 이상의 이벤트
• 같은 경로에 나오는 풍선들의 생성 시각은 모두 다릅니다.
• 게임이 진행되는 동안 데미지를 입는 풍선이 하나 이상 있습니다.

R 제한이 10인 이유는 crypt keeper의 경로 수가 10이기 때문입니다. 해당 맵은 정방향 한정 잠수함이 패치되기 전까지 제일 어려운 맵 중 하나였습니다.