Maycon,
isso tudo que eu falei acaba saindo simplesmente usando uma DP.
A idéia é bem parecida com o que falei... e isso fica completamente fora da
discussão da lista da OBM! :)
Qquer coisa, falamos em PVT.
abraços,
Salhab
2010/5/31 Maycon Maia Vitali <mayconm...@yahoo.com.br>
> O 'm' (K no problema) por ir ao máximo de 100. Estou lendo sua resposta.
>
> Em 31/05/2010 02:15, Marcelo Salhab Brogliato escreveu:
>
>> Maycon,
>> qual o tamanho do m?
>>
>> Se m não for muito grande, vc pode montar um grafo com m vértices,
>> representando as classes de
>> equivalencia {0}, {1}, ..., {m-1}.
>> Então, vc replica esse grafo n+1 vezes, criando um grafo n-dimensional.
>> No total, vc tem nm vértices.
>>
>> Vamos denotar esses grafos por g[i], onde i é a dimensão.
>> E vamos denotar o j-ésimo vértice da i-ésima dimensão por w[i][j].
>> Desta maneira, vamos definir as arestas de acordo com a seguinte regra:
>>
>> edge(w[i-1][j], w[i][k]) se, e somente se, j+v_i == k (mod m) ou j-v_i
>> == k (mod m)
>>
>> Desta maneira, só temos que verificar se existe um caminho de w[0][0]
>> até w[n][0].
>>
>> Dependendo do valor de m e n, parece bem viável.
>> Agora, se não tiver memória pra isso, veja que vc só depende da dimensão
>> n-1 para passar
>> para a dimensão n, dá pra ir construindo o grafo conforme vai buscando
>> um caminho.
>> (Mas, sinceramente, não acredito que seja necessário)
>>
>> Compliquei?! hehehe... talvez... espero que ache uma maneira mais simples.
>>
>> Boa noite!
>>
>> abraços,
>> Salhab
>>
>>
>>
>> 2010/5/31 Maycon Maia Vitali <mayconm...@yahoo.com.br
>> <mailto:mayconm...@yahoo.com.br>>
>>
>>
>> Existe algum método que nos ajude a provar que:
>> v_1 +/- v_2 +/- v_3 +/- ... +/- v_n
>>
>> É divisível por um 'm' qualquer dado?
>>
>> O problema é que se for testar todas as combinações de sinais + ou -
>> teríamos 2^{n-1} possibilidades, o que fica inviável para um 'n'
>> grande. E no problema o 'n' pode ir até 10000, o que é absurdamente
>> grande computacionalmente.
>>
>> Existe algum método matemático que eu possa utilizar para reduzir
>> esse problema?
>>
>> Abraços,
>> Maycon Maia Vitali
>> __________________________________________________
>> Faça ligações para outros computadores com o novo Yahoo! Messenger
>> http://br.beta.messenger.yahoo.com/
>>
>> =========================================================================
>> Instruções para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>>
>> =========================================================================
>>
>>
>>
> __________________________________________________
> Faça ligações para outros computadores com o novo Yahoo! Messenger
> http://br.beta.messenger.yahoo.com/
>
