Internet Problem Solving Contest

IPSC 2005

Problem F – Find The Right Words

Danka and Janka spend most of their time inventing and playing new games. The most recent game they play has these rules: At first player One chooses two letters. Player Two gives him a sequence of K letters li. Player One has to say K different words Wi such that the word Wi contains the letter li and the two letters chosen at the beginning of the game. (The order of these letters in the word doesn't matter. If some of the three letters are equal, it is sufficient if the word contains the corresponding letter once.) Player Two scores as many points as is the sum of the lengths of the words. Then they swap the roles and start again. The player with the most points wins.

They made a record of every game they played. Sadly, Danka lost all the games. Now she thinks that Janka cheated in some of the games. So Danka tried to check all previous games – but she found out that they forgot to record the chosen words. They recorded only the letters chosen by both players. Now she needs your help to find out how many points Player Two could get in each of the games.

Task specification:

You are given a wordlist with allowed words and specifications of some games. The specification of a game consists of two letters A, B chosen at the beginning of the game and of a sequence of N letters Li. For each game your task is to output N different words Wi from the given wordlist. The i-th word Wi must contain the letters A, B and Li. The sum of the lengths of the words must be minimal.

Input specification:

The first line of the input file contains one integer X denoting the number of words in the wordlist. On the next X lines there is the wordlist – X words, one word per line. On the X+2-nd line there is one number M denoting the number of games played. Next M lines contain the specifications of the games, one game per line. The specification of the i-th game consists of two letters ai, bi and a sequence of ki letters lij. All letters are separated by single spaces.

Output specification:

Output M blocks, one for each game in the input. If the i-th game doesn't have a valid solution, its block shall contain one line with the number -1. Otherwise the block starts with the number ki of words followed by ki different words from the wordlist, separated by whitespaces. The j-th of these words must contain characters ai, bi and lij and the sum of the lengths of the words must be as small as possible.

Note: string comparison should be done case sensitive.


c t e
c t E
c t e e
h l a
e e c
1 contest
2 contest
1 contest

Problemsetter(s): misof
Contest-related materials: Palo, Lukas
Special thanks: to the puzzle journal Relax for the game Abeceda that inspired this task