ICPC ECNA 2016 E - Red Rover

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 1G

Problem type
ICPC East Central NA Regional Contest 2016, Problem E

One of our older Mars Rovers has nearly completed its tour of duty and is awaiting instructions for one last mission to explore the Martian surface. The survey team has picked a route and has entrusted you with the job of transmitting the final set of instructions to the rover. This route is simply a sequence of moves in the cardinal directions: North, South, East, and West. These instructions can be sent using a string of corresponding characters: N, S, E, and W. However, receiving the signal drains the rover's power supply, which is already dangerously low. Fortunately, the rover's creators built in the ability for you to optionally define a single macro that can be used if the route has a lot of repetition. More concretely, to send a message with a macro, two strings are sent. The first is over the characters {N,S,E,W,M} and the second is over {N,S,E,W}. The first string represents a sequence of moves and calls to a macro (M), while the second string determines what the macro expands out to. For example:

WNMWMME
EEN

is an encoding of

WNEENWEENEENE

Notice that the version with macros requires only 10 characters, whereas the original requires 13.

Given a route, determine the minimum number of characters needed to transmit it to the rover.

Input Specification

Input consists of a single line containing a string made up of the letters N, S, E, and W representing the route to transmit to the rover. The maximum length of the string is 100.

Output Specification

Display the minimum number of characters needed to encode the route.

Sample Input 1

WNEENWEENEENE

Sample Output 1

10

Sample Input 2

NSEW

Sample Output 2

4

Sample Input 3

EEEEEEEEE

Sample Output 3

6
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.