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


[Pequeno grande PROBLEMA] Many a Little makes a Mickle

6 posts in this topic

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.


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.


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













Sample Output

Set 1: 5.

Set 2: Not possible.


Share this post

Link to post
Share on other 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.


Share this post

Link to post
Share on other 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)


Share this post

Link to post
Share on other 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."


Share this post

Link to post
Share on other sites

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


Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now