|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||4||3||3||75.000%|
In the pirate society, each pirate captain is obligated to obtain a pet. This pet should be at the side (or on the shoulder) of a pirate captain at all times, especially during conversations with good doers who wish to challenge the captain’s evil ways.
Greedbeard is the infamous and feared captain of the pirate ship Greatlooter. His pet is the infamous and feared parrot known as Polly. As a parrot, Polly likes to mimic the conversations he overhears. Unfortunately, Polly is not very good at mimicking the sentences he hears. For this reason, Greedbeard has taken it upon himself to assist Polly as he learns to speak the human tongue.
Greedbeard noted that Polly is able to speak whole sentences, but often makes one or more of the three following mistakes:
Note that Polly never mimics the same word twice in a sentence. The captain always knows the original sentence that Polly is trying to mimic.
Captain Greedbeard is not interested in the first two mistakes. However, mixing up letters or adding/removing letters from a word makes his blood boil. Therefore, each time Polly makes mistakes in a sentence by mixing up letters, the captain will take away one cracker from his lunch, for each letter he mixes up. The number of crackers that the captain removes per word, is the minimum number of edits needed to transform the spoken word into the word that Polly was trying to say. An edit is defined as either an insertion, deletion or substitution of a single letter.
It is not always clear how words in the mimicked sentence correspond to words in the original sentence. Greedbeard assumes the mimicked words are matched with the original words in such a way that the total number of mistakes is minimal.
For instance, if Polly should have said: “polly wants a cracker” and says: “polly crackets wantsu”, the captain will remove 3 crackers from his lunch. These are 2 crackers for messing up the word “cracker” and 1 cracker for adding a letter to the word “wants”. He does not care that the word “a” is missing, or that words are spoken in the wrong order.
2Read: mixes up, adds or removes letters
The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
For every test case in the input, the output should contain one integer on a single line: the number of crackers that Greedbeard will withhold from Polly’s lunch.
3 polly wants a cracker polly crackets wantsu pretty polly petty polli pieces of eight eight of pieces
3 2 0