1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

[PYTHON][Pequeno grande PROBLEMA] Many a Little makes a Mickle

Discussão em 'Programação' iniciada por filipemm, 31 de Outubro de 2008. (Respostas: 2; Visualizações: 757)

  1. filipemm

    filipemm Power Member

    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.
     
  2. arkannis

    arkannis Power Member

    Problemas desses existem aos milhares aqui (aliás, esse que está ai foi tirado daqui):
    http://icpcres.ecs.baylor.edu/onlinejudge/

    E já agora, tanto faz ser python ou outra linguagem qualquer. A questão aí é o algoritmo, não a linguagem que se usa.
    E se for ajuda que precisares, podes sempre usar isto:
    http://acm.uva.es/board/
     
  3. AliFromCairo

    AliFromCairo Power Member

    Algo do género:

    Código:
    def mickle(s, substrings):
        count = 0
        i = 0
        substrings = substrings + [x[::-1] for x in substrings if x[::-1] != x]
        substrings.sort(lambda x, y: cmp(len(y), len(x)))
        while i < len(s):
            for ss in substrings:
                if s[i:i+len(ss)] == ss:
                    count = count + 1
                    i = i + len(ss)
                    break
            else:
                return 'Not possible.'
        return count
    
    Alguns testes:

    Código:
    >>> mickle('aabbabbabbbb', ['a', 'bb', 'abb'])
    5
    >>> mickle('ewu**bbacsecsc', ['ewu', 'bba', 'cse', 'csc'])
    'Not possible.'
    >>> mickle('aabbabbabbbb', ['a', 'bb', 'abx'])
    8
    >>> mickle('aabbabbabbbbabababa', ['a', 'b'])
    19
    
    Não li o enunciado todo, portanto é possível que falte alguma coisa, mas penso que está a funcionar correctamente.

    Espero que ajude.
     

Partilhar esta Página