RTE '16 S2 - Fire Evacuation Plan

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Python 2 1.4s
Python 3 1.4s
Memory limit: 64M
Python 2 64M
Python 3 64M

Problem type

At RHHS, the school is on fire every other day, because safety is our number one priority. After administration has decided enough was enough, they decided to place detailed evacuation plans in each and every classroom to ensure everyone's safety during fire evacuations.

An evacuation plan consists of a list of movements in cardinal directions (North, South, East, West), which detail the exact movements a student must make in order to make it to safety.

One such evacuation plan may be NNWS, which describes an evacuation plan where the student must move one meter north, one meter north, one meter west, then one meter south in order to reach safety.

However, administration has decided that these evacuation plans were too easy to follow, and did not foster the academic atmosphere RHHS is so famously known for having. As a result, administration decided to encode the evacuation plans with a different encoding for each room.

With this encoding, each cardinal direction is replaced with a string of letters, and the final evacuation plan is the concatenation of this string of letters. For example, the following mapping represents a possible encoding:

N → AA
S → A
E → B
W → AB

With this encoding, our original evacuation plan of NNWS becomes AAAAABA.

A side effect of this encoding is that it may represent multiple possible original evacuation plans. With the above encoding, AAAAABA could not only represent NNWS, but also SSSSSES.

Given an encoding and an evacuation plan, determine the number of possible distinct destinations the evacuation plan could lead to.

Input Specification

The first four lines will contain the encoding for North, South, East, and West respectively. Each encoding will not exceed 128 characters. The next line will contain an evacuation plan encoded with the given encoding, of length L (1 \leq L \leq 2\,500).

For test cases worth 20 of 100 points, 1 \leq L \leq 10.

Output Specification

Output a single integer representing the number of possible distinct destinations the evacuation plan may lead to.

Sample Input


Sample Output


Explanation of Sample Output

The possible original evacuation plans the encoded plan may represent are as follows:


However, many of them represent the same destination (for example, NNSES and NSNES are both syntactically identical to E). 6 of these plans lead to a distinct location.


  • -1
    Mahagoni  commented on April 10, 2018, 12:05 p.m. edited


  • 7
    kobortor  commented on April 6, 2018, 5:28 p.m.

    This problem got used in the recent Bubble Cup!

    • 3
      kipply  commented on April 6, 2018, 6:33 p.m.

      We've had another "fire" and several false alarms since this problem was created (vaping in bathrooms set off an alarm). RHHS is a lit school.