• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

filipemm

[Pequeno grande PROBLEMA] Many a Little makes a Mickle

6 mensagens neste tópico

Deixo aqui um pequeno problema para quem o quiser resolver!!  :P

Many a Little makes a Mickle

A long string does not look so long if we can identify a few short substrings that were used (possibly more than once) in some permutation to construct the longer string. Your task is to find if a given (long) string can be made up by choosing some (shorter) strings from a given collection.

You should note that:

  1. All the strings are composed of ASCII characters in the range 33 to 127.

  2. Any of the short strings or their reversed forms can be used any number of times to construct the long string

  3. Each use of a short string or its reverse would be counted as one occurance of that short string

When you construct the longer string from these short strings you should ensure that it is done by keeping the total occurances of the short strings minimum.

For example, if we want to construct the string "aabbabbabbbb" from the set {"a","bb","abb"}, there can be many ways to achieve the goal. "a-abb-abb-abb-bb" and "a-abb-a-bba-bb-bb" are two such valid constructions. However, we would prefer "a-abb-abb-abb-bb" (5 substrings) over "a-abb-a-bba-bb-bb" (6 substrings) because it uses lesser number of substrings. You would only need to find the minimum number of substrings that could be used to construct the given string.

Input

The first line of the the input contains S (S<51), the number of data set. Then S number of data set follows. First line of each data set contains the long string, P (0 < length (P) < 10001). The next line contains the number of short strings, N (0 < N < 51) to choose from. Each of the next N lines contain the short string Pi (0 < length (Pi) < 101) [ i >= 1,2,3….N]. You can safely assume that there is no blank/empty line in the input file.

Output

For each data set print exactly one line of output.

Either “Set S: C.”

Or “Set S: Not possible.”

If it is possible to construct the string using the given strings then print the first line otherwise print the second line. Here S is the serial of data set (sequentially from 1 to S) and C is the minimum number of times the substrings were used to construct P. For clarification see sample output below.

Sample Input

2

aabbabbabbbb

3

a

bb

abb

ewu**bbacsecsc

4

ewu

bba

cse

csc

Sample Output

Set 1: 5.

Set 2: Not possible.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

#  Problem          Verdict Language  Run Time  Submission Date

6765420 10860 Many a Little makes a Mickle Accepted C++ 0.070 2008-10-31 18:55:45

Belo problema :P  Submeti aqui

Só não gostei do facto que no inicio do enunciado fala em construir a string maior através do uso de permutações de strings mais pequenas e depois mais abaixo só fala no uso do uso de strings mais pequenas e no seu reverso. De facto, só é preciso considerar as strings e o seu reverso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Também fiquei na dúvida, mas depois aqueles 3 pontos esclarecem.

Não gosto muito de problemas de strings, mas este não me parece difícil. (aliás, de strings tem pouco)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Dada uma string S, e N strings (mais pequenas), saber qual o número mínimo de strings pequenas necessário para formar a grande.

A isto acresce a particularidade das pequenas poderem estar invertidas.

Caso seja impossível, imprimir "Not possible."

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Vou tentar por aqui a solução em c pode ser que consiga. Vamos la ver.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora