Editorial for COCI '15 Contest 4 #2 Han


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

If we simulate the process described in the task by constructing a word that consists of the letters Dominik is saying, and for each UPIT command we count the required letters in the word, we are left with an algorithm of time complexity \mathcal O(QN), which is sufficient for 40\% of total points. An additional 20\% of points could have been won by keeping track of how many of which letter appeared so far while constructing the word. Now it is possible to answer each UPIT command in \mathcal O(1).

Finally, in order to completely solve the task, we must notice that, if undisturbed with a command, after first N \mathbin\% 26 spoken letters, Dominik will say each letter exactly N/26 times (he will be stuck in a cycle of length 26), where \% is the modulo operator, and / is the integer division operator. Using this property, we can simulate each command in constant time.


Comments

There are no comments at the moment.