Vocabulary Quiz
플래티넘 IV의견: 0
Bessie is helping Elsie with her upcoming vocabulary quiz. The words to be
tested will be drawn from a bank of \(M\) distinct words, where no word in the
bank is a prefix of another word in the bank.
While the bank is nonempty, Bessie will select a word from the bank, remove it
from the bank, and read it to Elsie one character at a time from left to right.
Elsie's task is to tell Bessie once she can uniquely identify it, after which
Bessie will stop reading.
Bessie has already decided to read the words from the word bank in the order
\(w_1,w_2,\dots,w_M\). If Elsie answers as quickly as possible, how many
characters of each word will Bessie read?
The words are given in a compressed format. We will first define \(N+1\)
(\(1\le N\le 10^6\)) distinct words, and then the word bank will consist of all
those words that are not a prefix of another word. The words are defined as
follows:
- Initially, the \(0\)th word will be the empty string.
- Then for each \(1\le i\le N\), the \(i\)th word will be equal to the \(p_i\)th word plus an additional character at the end (\(0\le p_i
Problem credits: Benjamin Qi
SCORING
- Inputs 4-5: No word has length greater than \(20\).
- Inputs 6-10: The sum of the lengths of all words in the word bank does not exceed \(10^7\).
- Inputs 11-18: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\), where \(N+1\) is the number of words given in the
compressed format.
The next line contains \(p_1,p_2,\dots,p_N\) where \(p_i\) represents that the
\(i\)-th word is formed by taking the \(p_i\)-th word and adding a single character
to the end.
Let \(M\) be the number of words that are not a prefix of some other word. The
next \(M\) lines will contain \(w_1,w_2,\dots,w_M\), meaning that the \(w_i\)th word
will be the \(i\)th to be read. It is guaranteed that the words to be read form a
permutation of the words in the word bank.
Output \(M\) lines, where the \(i\)th line contains the number of characters of the
\(i\)th word that Bessie reads.
5
0 1 2 3 4
50There are \(6\) words labeled \(0\dots 5\). Word \(5\) is the only one that is not a
prefix of another word, so it is the only one in the bank. In general, once only
one word is left in the bank, Elsie won't need any characters to identify it.
4
0 0 1 1
4
3
22
1
0The bank consists of words \(2\), \(3\), and \(4\).
Elsie needs two characters to identify word \(4\) since words \(3\) and \(4\) share
their first character in common.
Once Bessie reads the first character of word \(3\), Elsie has enough characters
to uniquely identify it, since word \(4\) was already read.
4
0 0 1 1
2
3
41
2
0riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Silver
평가 및 의견
Vocabulary Quiz
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Vocabulary Quiz