## RGPC '17 P5 - Scrabble Nuts

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

Nutter is a weird kid. As an infant, he was obsessed with the prefixes of nutt (nut, nu, and n), but hated the word nutt itself. When his parents bought him a box of Scrabble, he realized that the board already contained a single word: putt, which got him thinking. He wondered how he could add, swap, or remove blocks from a word to make all the prefixes of another word .

Nutter has access to an infinite supply of Scrabble blocks, and can only add, swap, or remove blocks to form his desired prefixes. Each operation takes 1 move, but since he's quick with his hands, he isn't worrying about shifting blocks (you can add, swap, or remove non-terminal blocks). Nutter wants to know how he can turn word into word 's prefixes (not including word itself) using the minimum number of moves.

#### Input Specification

The first line of input will contain two integers and separated by a single space. The second line will contain a single string of length , and the third line will contain a single string of length .

#### Output Specification

Output a single integer representing the minimum number of moves to change word to all of word 's prefixes.

#### Sample Input

4 4
nutt
putt

#### Sample Output

9

#### Explanation

The prefixes of putt are put, pu, and p, and Nutter wants to try and make them all from the word nutt.

To get put from nutt, swap the n with a p and remove a t from the end (2 operations).
To get pu, do the same operations as put, but remove another t (3 operations + 2 = 5 total).
To get p, do the same operations as pu, but remove the u at the end (4 operations + 5 = 9 total).

Since Nutter doesn't want to make putt itself, he uses 9 operations in total.

• commented on Feb. 17, 2017, 9:50 p.m. edit 6

Words ARE case-sensitive.

Swap = Replace 1 character from word A WITH another character to MAKE word B.

• commented on Feb. 17, 2017, 2:30 p.m. edited

What can be swapped? Is it allowed to...

• swap blocks within the word A
• swap block from the word A and a block taken from the supply

Also, are the words case-sensitive?

I hope these can be clarified. Thank you.