GPT DarkDown

Mahdieh는 Divar 오픈 플랫폼(Kenar Divar)용 챗봇을 개발하고 있다. 그녀는 이 챗봇에 ChatGPT API를 쓰려고 한다. 챗봇은 ChatGPT가 보낸 메시지를 받아 사용자에게 전달한다. 챗봇이 메시지 생성을 요청하면 ChatGPT는 메시지를 여러 조각(chunk)으로 나누어 보낸다. 각 조각에는 챗봇이 그 조각을 받은 시각과 조각에 담긴 문자열이 함께 있다.

부드러운 사용자 경험을 위해 챗봇은 1밀리초에 한 글자씩 입력한다. 글자는 수신되기 전에는 입력할 수 없으므로, 차례가 된 글자는 이미 챗봇에 도착해 있어야 한다. 챗봇은 한동안 아무것도 입력하지 않고 기다렸다가, 그 뒤로는 멈추지 않고 계속 입력한다. Mahdieh는 가상의 메시지에 속한 모든 조각의 정보를 알고 있으며, 챗봇이 입력을 시작할 수 있는 가장 이른 시각을 구하려고 한다.

ChatGPT의 텍스트에는 Darkdown 서식이 적용되어 있다. Darkdown에는 굵은 글씨, 기울임꼴, 인라인 코드, 이모지가 있다. 예를 들어 [Let's] (Code!) :rocket:는 24글자이지만, 렌더링하면 Let's Code! 🚀 가 되어 13글자가 된다. 서식 문자는 최종 출력에 나타나지 않으므로, 실제로 렌더링되는 내용만 따진다.

이 문제에서 구하는 것은 렌더링된 메시지 전체를 끊김 없이 입력할 수 있는, 입력 시작의 가장 이른 시각이다.

첫 줄에는 조각의 개수 k가 주어진다 (1 ≤ k ≤ 10^5). 다음 k줄에는 조각이 한 줄에 하나씩 주어지며, 각 조각은 비어 있지 않다. 메시지에는 줄바꿈 문자가 없고, 조각은 공백으로 시작하거나 끝날 수 있다. 모든 조각의 글자 수 합은 10^5를 넘지 않으며, 렌더링된 최종 메시지는 비어 있지 않다.

마지막 줄에는 공백으로 구분된 정수 t_1, t_2, ..., t_k가 주어진다. t_i는 챗봇이 i번째 조각을 받은 시각이다 (1 ≤ t_1 < t_2 < ... < t_k ≤ 10^9).

입력은 다음 Darkdown 규칙을 따른다.

• 인라인 코드: 백틱 한 쌍으로 감싼 부분이다. 백틱 문자는 렌더링되지 않는다. 인라인 코드 안에는 백틱이 없다. 인라인 코드 안의 (나 \ 같은 서식 기호는 글자 그대로 렌더링되며 서식으로 해석되지 않는다.
• 특수 문자: (, ), [, ], :, , '는 앞에 백슬래시를 붙여 이스케이프한다. 예를 들어 (, ), [], ], :, \, '처럼 쓴다. \는 백슬래시 한 글자로 렌더링된다. 인라인 코드 안과 이스케이프된 \ 뒤를 제외하면, 모든 백슬래시는 특수 문자 앞에 온다.
• 굵은 글씨: (굵은 글씨)처럼 소괄호로 감싼다.
• 기울임꼴: [기울임꼴]처럼 대괄호로 감싼다.
• 굵은 글씨 블록과 기울임꼴 블록은 중첩할 수 없고, 한 블록이 굵은 글씨이면서 기울임꼴일 수도 없다. [(bold and italic) italic]이나 ((superbold) bold)는 나오지 않는다.
• 인라인 코드와 이모지는 굵은 글씨나 기울임꼴 안에 들어갈 수 있다.
• 이모지는 두 콜론 사이에 든 비어 있지 않은 소문자 영문자열이다. 예: :smile:, :rocket:.
• 마침표, 쉼표, 느낌표, 물음표, 작은따옴표, 하이픈, 슬래시와 공백은 그대로 렌더링된다.

입력은 항상 이 규칙을 지키며, 렌더링된 텍스트는 하나로 정해진다.

렌더링된 메시지 전체를 끊김 없이 입력할 수 있는, 챗봇이 입력을 시작할 수 있는 가장 이른 시각을 출력한다.