Re: [obm-l] Cone Sul - Problema 6

["Domingos Jr." <dopikas@xxxxxxxxxx>]

bom, a minha proposta para a função que conta quantos caminhos num tabuleiro
m x n tem área a é a recorrência:

f(m, n, a) = f(m - 1, n, a - n) + f(m, n - 1, a)

A idéia é a seguinte: qualquer caminho acaba no ponto do canto
inferior-esquerdo. Só há duas maneiras de chegar nesse ponto, uma é por cima
e a outra é pela direita.

Se o caminho vem por cima, então todos os n quadradinhos da última linha são
incluídos e o caminho a partir do ponto logo acima é um caminho num
tabuleiro m-1 x n cuja área deve ser a - n para que a área total seja a.

Se ele vier pela direita então não há nenhum quadradinho da primeira coluna
entrando para a contagem da área, logo qualquer caminho desse tipo é na
verdade um caminho num tabuleiro m x n-1 de área a.

A base da recorrência é bem simples:
f(1, k, a) = f(k, 1, a) = { 0 ... se a > k ou a < 0k
                                { 1 ... caso contrário

a propósito, coloquei minha solução para o problema 3 da Cone Sul junto com
a solução de vários outros problemas em:

www.linux.ime.usp.br/~domingos/problemas_resolvidos.pdf

[ ]'s

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================