## RGPC '17 P5 - Scrabble Nuts

View as PDF

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

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.