Editorial for COCI '15 Contest 4 #2 Han
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 , which is sufficient for of total points. An additional 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 .
Finally, in order to completely solve the task, we must notice that, if undisturbed with a command, after first spoken letters, Dominik will say each letter exactly times (he will be stuck in a cycle of length ), where is the modulo operator, and is the integer division operator. Using this property, we can simulate each command in constant time.
Comments