VM7WC '16 #4 Silver - Tests or Test Cases?

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type

Oh no! Jeffrey has a 2-day Mohan Physics test tomorrow on Melanie's theorem and being the responsible student that he is, he hasn't started studying yet! To nobody's surprise, Jeffrey also has not started creating the test case input files for the weekly Seven Week Challenge which are due in 12 hours!

Not wanting to be rejected from University of Waterloo's Computer Science program with his physics marks, Jeffrey has decided to go ham on studying for the night so he can pass the test tomorrow and the day after.

While solving a block-on-block centripetal force with a pulley problem using Melanie's Chain Rule, Jeffrey suddenly came across a great idea! He can just generate all of the test cases by writing a program to do it. Jeffrey was very proud of his genius idea and put Mohan studying aside to work on the program.

Worried about his university acceptance, mark in Mohan's class and the chances of him making out of Massey successfully with enough credits, Jeffrey has assigned you with the task of writing the program for him so he could continue studying for the test.

For each of Jeffrey's test cases, he will need to generate all the words possible, line-by-line, that follow a specific set of rules. To generate them, Jeffrey will be able to use all of the letters in the alphabet in lowercase. However, there are rules on specific types of letters that can precede other specific types of letters. In addition to these rules, the length of the words generated must not exceed some given input, L.

Jeffrey will tell you the number of different restrictions, N, there are for generating the words. Each 'restriction set' contains a set of letters. For any given 'restriction set', S, any of the letters contained in any of the preceding restriction sets can be followed by any of the letters in the set of S. The words can only begin with the letters given in the first restriction set. (See the sample test cases for clarification)

Input Specification

The first line will contain two space separated integers:

  • N (1 \le N \le 26): The number of different restrictions sets that will follow.
  • L (1 \le L \le N): The maximum length of the words generated.

The following N lines will be structured like this:

  • M (1 \le M \le 26): The number of letters in the current restriction set.
  • Followed by M space separated letters on the same input line that are in the current restriction set.

It is guaranteed that there will be no overlap of letters between restriction sets. Each letter will only appear once across all of the sets.

Output Specification

Output all possible words that comply with the restrictions given by Jeffrey, line-by-line in alphabetical order.

Sample Input

4 3
1 a
2 e i
1 j
1 m

Sample Output



  • 1
    kobortor  commented on Feb. 2, 2016, 9:35 a.m.

    P10 has 2 'h's

    2 1
    a b c d e f g h i j 
    h i j k


    • 1
      cheesecake  commented on Feb. 2, 2016, 1:24 p.m.

      The test case has been fixed, note that the correct output was unambiguous despite the contradiction with the problem statement.