Tetraedro

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Tetraedro

Mensagempor Bruno Oliveira em Terça Out 23, 2012 9:15 am

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quarta Out 24, 2012 12:59 am

Boas de novo,

Aqui vai a ideia:

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

Aqui vai o código:
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Quarta Out 24, 2012 7:51 am

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quarta Out 24, 2012 12:49 pm

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.
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Quarta Out 24, 2012 5:57 pm

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quarta Out 24, 2012 8:50 pm

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?
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Quarta Out 24, 2012 9:23 pm

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quarta Out 24, 2012 9:46 pm

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...
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Quarta Out 24, 2012 11:18 pm

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? :)
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quinta Out 25, 2012 12:46 am

O de 30 devolve 347990060
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Quinta Out 25, 2012 8:31 am

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:
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Quinta Out 25, 2012 10:47 am

Tinha-me esquecido de multiplicar por 3, afinal tenho bem
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Sexta Out 26, 2012 4:19 pm

Ó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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Re: Tetraedro

Mensagempor francisco_machado em Segunda Out 29, 2012 12:00 pm

Aqui vai a ideia:


Aqui vai o codigo:
última vez editado por francisco_machado s Quinta Nov 01, 2012 2:48 pm, editado 1 vez no total
francisco_machado
gluão
gluão
 
Mensagens: 27
Registado: Sexta Fev 26, 2010 8:28 pm

Re: Tetraedro

Mensagempor Bruno Oliveira em Segunda Out 29, 2012 11:37 pm

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
e^{ix}=cos x + i\,sin x
Avatar do utilizador
Bruno Oliveira
top-Quark!
top-Quark!
 
Mensagens: 1553
Registado: Quarta Nov 14, 2007 10:19 pm
Localização: Lisboa

Próximo

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 3 visitantes