Bessie는 Elsie의 다가오는 어휘 퀴즈를 도와주고자 합니다. 시험에 출제될 단어들은 M개의 서로 다른 단어들로 구성된 단어 은행에서 가져오게 되며, 이 단어 은행 내의 어떤 단어도 다른 단어의 접두사(prefix)가 되지 않습니다.

단어 은행이 비어 있지 않은 동안, Bessie는 단어 은행에서 단어 하나를 선택하여 제거한 후, 그 단어를 왼쪽에서 오른쪽으로 한 글자씩 읽어 Elsie에게 전달합니다. Elsie의 임무는 단어를 유일하게 식별할 수 있게 되는 순간 Bessie에게 알려주는 것이며, 그 즉시 Bessie는 읽기를 멈춥니다.

Bessie는 단어 은행에 있는 단어들을 w₁, w₂, …, w_M의 순서로 읽기로 이미 결정해 두었습니다. 만약 Elsie가 가능한 한 빨리 답한다면, Bessie는 각 단어에 대해 몇 글자를 읽게 될까요?

단어들은 압축된 형식으로 주어집니다. 먼저 N+1개의 서로 다른 단어들을 정의한 후, 단어 은행은 다른 단어의 접두사가 아닌 단어들로 구성됩니다. 단어들은 다음과 같이 정의됩니다:

처음에 0번째 단어는 빈 문자열입니다.

그 후, 1 ≤ i ≤ N에 대해 i번째 단어는 pᵢ번째 단어에 한 글자를 덧붙인 것으로 정의됩니다 (0 ≤ pᵢ < i). 모든 N+1개의 단어들이 서로 다르도록 글자들이 선택됩니다.

#8312 upload 17 done 2 how_to_reg 2 call_split Subtask

Vocabulary Quiz timer 2s memory 2048MB

#8312
Subtask

Vocabulary Quiz 2s 2048MB