Página 1 de 2

Tetraedro

MensagemEnviado: Terça Out 23, 2012 9:15 am
por Bruno Oliveira
Uma formiga extremamente activa, está no vértice D de um tetraedro, como o mostrado abaixo.

A uma dada altura, a formiga viaja de um vértice para outro através de uma das várias arestas do tetraedro, e a tarefa apresentada não envolve muitos cálculos.

Simplesmente, calculem o número de maneiras em que a formiga pode ir do vértice inicial D, de volta a ele próprio em apenas N passos.

Novamente, o resultado pode ser enorme, logo, devolvam-no reportado mod 10^9 + 7.

Exemplos:
Claramente, para N = 1 não há caminhos possíveis.

Para N = 2 a resposta é 3, e os caminhos possíveis são: D-B-D; D-A-D; D-C-D

Sabe-se ainda que, para N= 4, a resposta é 21!!

Imagem

Have fun!!

Bruno

source: CodeForces

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 12:59 am
por francisco_machado
Boas de novo,

Aqui vai a ideia:

Super-spoiler (só olhar em caso de extrema necessidade:

Aqui vai o código:

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 7:51 am
por Bruno Oliveira
Tenho uma ideia mais "matemática", um pouco baseada em intuição mas que acaba por ser talvez mais elegante... :wink:

Se ninguém chegar lá, posto a minha solução dentro em breve!!!

Muitos parabéns de novo Francisco!!

PS: O Francisco está a dominar ehehe, ninguém se opõe? :P
PPS: Tharis, is that you? :wink:

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 12:49 pm
por francisco_machado
Boas,

Depois de pensar um pouco mais no que poderia ser essa ideia mais matema´tica, acho que ja´ a descobri.

Aqui vai a ideia:



Aqui vai o codigo:



Peço desculpa pelos acentos, mas estou nos pcs do departamento e isto na~o tem os acentos bem.

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 5:57 pm
por Bruno Oliveira
Bem, andaste a aprender algoritmos com os famosos CLRS? Estes são mesmo muito bons!!

Parabéns pelos insights todos!! :hands:

Mas há ainda outra maneira!!

Bruno

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 8:50 pm
por francisco_machado
CLRS? Não conheço, o que é?

Muito obrigado.

A outra maneira que vejo é arranjar a fórmula fechada para isso que uma pesquisa rápida no google já me deu. É essa que estás a pensar?

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 9:23 pm
por Bruno Oliveira
Sim, francisco é exactamente isso!! :wink:

No entanto, aviso-te que existe uma pequena nuance relacionada com a implementação dessa ideia...

Ora corre o teu programa com a fórmula fechada para o valor de 30...

Bruno

PS: CLRS é a designação pela qual é conhecido o livro de algoritmos mais divulgado por várias universidades, o famoso: "Introduction to Algorithms" ;) As letras são as iniciais dos apelidos dos autores.

PPS: Se não o conheces, onde aprendeste tanto de algoritmia? :shock:

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 9:46 pm
por francisco_machado
Tenho esse livro, mas não o conhecia por esse nome. Quanto a saber tanto de algoritmia advém de ter participado nas Olimpíadas Internacionais de Informática e a preparação deu-me bases fortes.

Deveria entrar em overflow não é? No meu não está a entrar...

Re: Tetraedro

MensagemEnviado: Quarta Out 24, 2012 11:18 pm
por Bruno Oliveira
De repente, acho que o problem setter, passou a coder e vice-versa ;)

Não, nada de overflows... não esquecer que o valor máximo aqui pode ser relativamente grande... da ordem de 10.000.000 (esqueci-me das constrains... Fuck me, right? ), pelo que o problema é outro, mais matemático novamente...

Que valor devolve o teu programa? :)

Re: Tetraedro

MensagemEnviado: Quinta Out 25, 2012 12:46 am
por francisco_machado
O de 30 devolve 347990060

Re: Tetraedro

MensagemEnviado: Quinta Out 25, 2012 8:31 am
por Bruno Oliveira
Ehehe consegui apanhar um Olímpico em contra-pé... :P Ao fim de anos aqui no fórum..

Agora mais a sério, então e para N = 15?

Eu bem disse que havia um problema eheh!!!

A resposta para N = 15 é 3587226 e para N = 30 é 782663359

Boa sorte no debugging!! :wink:

Re: Tetraedro

MensagemEnviado: Quinta Out 25, 2012 10:47 am
por francisco_machado
Tinha-me esquecido de multiplicar por 3, afinal tenho bem

Re: Tetraedro

MensagemEnviado: Sexta Out 26, 2012 4:19 pm
por Bruno Oliveira
Óptimo!!

Congrats, então se puderes coloca aqui a resolução para os newbies que aí vierem possam aprender também! ;)

Eu posso depois colocar também a minha resolução aqui para ficarem duas explicações distintas!!

Cumprimentos,
Bruno

Re: Tetraedro

MensagemEnviado: Segunda Out 29, 2012 12:00 pm
por francisco_machado
Aqui vai a ideia:


Aqui vai o codigo:

Re: Tetraedro

MensagemEnviado: Segunda Out 29, 2012 11:37 pm
por Bruno Oliveira
O que o Francisco fez está tudo correcto, mas e que tal demonstrar directamente a fórmula fechada, sem indução? :wink:



Edit: Franscisco, há muitos problemas com esse código :p