65 - ZOJ Monthly, May 2008 - 1005
The problem made whatashya need be rejudged again, and this time he comes to you for help. So fool as he is, he isn't able to get the right input and output efficiently. Assume that the solution is always right, and there is something wrong with the input. As it's unsuitable to public the input and output, so what you can do is just telling him the least time he need to fix his input.
There are three kinds of input errors:
And each time poor whatashya can do these operations:
Now give you the number of case in the input and some strings describe the errors in it. Find the least times of rejudges. The number of cases should keep the same.
There will be multiple cases. Each case begin with a integer N (N will not be more than 505) indicating the number of cases in the wrong input. Then N strings follow, each stands for a case and lenth for each string is less than 20. If the case is right, the string will be "o". Otherwise it will be made by 'p','r' and 'n' (e.g. "pr" or "nnpn").
For each case, output a line telling the least times of rejudges. The output should be in the form as follow:
2 o o 4 prn prn prn prn 6 prn pnr rpn rnp npr nrp
Impossible! re-re-re-re-rejudge re-re-re-re-re-rejudge
Author: WU, Zejun