Números Reversíveis

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

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Segunda Jun 07, 2010 6:49 am

Tharis, mais uma vez obrigado pelas dicas!!

Vou ver se depois da minha época de exames, ou talvez um bocadinho ao fim da tarde ou à noite nestes dias, começo a tentar resolver os da USACO, mas eles parecem-me mesmo dificieis... :?

ETA: Tharis, já que sou um bocado newbie no que toca à USACO, podemos submeter o nosso solution file em Python?
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: Números Reversíveis

Mensagempor Ivo_Timóteo em Segunda Jun 07, 2010 11:06 am

O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...

Spoj tem problemas muito engraçados mas também tem muitos ridículos, é uma questão de seleccionar :)

Embora já me esteja a desligar um pouco das provas da ACM, em termos de algoritmia aconselho a aprender as bases ao mesmo tempo no USACO e no Introduction to Algorithms.
Depois pode-se ir ao SPOJ resolver os problemas das provas regionais da ACM. Esses já dão para pensar mas com eles é que se aprende verdadeiramente, a ir consultar e estudar para ir resolvendo.

Quanto às questões de velocidade, não são tão "inacreditáveis" como vocês dizem :) Naturalmente há linguagens mais rápidas mas o mais relevante é mesmo o algoritmo. Como curiosidade, vejam as optimizações do gcc ou do g++ e depois pensem se afinal o código que corre é mesmo o vosso :P

Por vezes é melhor escrever o código o mais simples possível e deixar as optimizações para o compilador (que assim compreende melhor o que deve fazer sem ter de cair para estados de menor optimização por causa de expressões complexas) do que tentar optimizar.

Bem, sobre compiladores muito se pode dizer, até que acabam por não respeitar a "vontade" do programador. Linguagens interpretadas não podem ter muitas dessas optimizações, c'est la vie :)
Avatar do utilizador
Ivo_Timóteo
charm-Quark!
charm-Quark!
 
Mensagens: 579
Registado: Quarta Nov 15, 2006 7:25 pm
Localização: V. N. Gaia

Re: Números Reversíveis

Mensagempor Tharis em Segunda Jun 07, 2010 6:40 pm

Ivo_Timóteo Escreveu:O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...


Não concordo quando dizes que é difícil nem quando dizes que torna-se aborrecido. É difícil para quem tá a aprender, sem dúvida. E não se torna aborrecido, o nível de problemas que te colocam é que aumenta de uma maneira um pouco abrupta que podes ficar parado numa secção durante meses e noutras passares num dia.

@Bruno Oliveira, não. O USACO só aceita Pascal, C, Cpp, Java.
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Segunda Jun 07, 2010 8:32 pm

Ohh raios...

As ferramentas para tratamento de strings e listas no Python, estão-me a deixar muito mal habituado...

Como é que raio se fará uma função para converter uma letra para um número e uma palavra para um produto de letras? :P

I miss str(word)[0:1] etc :XD

Tenho de olhar para as funções dísponiveis em C++ como o atoi ou algo dessa familia :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: Números Reversíveis

Mensagempor Tharis em Segunda Jun 07, 2010 8:52 pm

Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números Reversíveis

Mensagempor Ivo_Timóteo em Segunda Jun 07, 2010 10:47 pm

Tharis Escreveu:
Ivo_Timóteo Escreveu:O USACO é engraçado, não é difícil, bom para aprender mas torna-se um pouco aborrecido...


Não concordo quando dizes que é difícil nem quando dizes que torna-se aborrecido. É difícil para quem tá a aprender, sem dúvida. E não se torna aborrecido, o nível de problemas que te colocam é que aumenta de uma maneira um pouco abrupta que podes ficar parado numa secção durante meses e noutras passares num dia.

@Bruno Oliveira, não. O USACO só aceita Pascal, C, Cpp, Java.



Eu disse que não era muito difícil mas, para mim, a certa altura torna-se aborrecido :) Mas o pior problema mesmo é já não estar no secundário com muito tempo :) E o facto de, a certa altura, amortizar NP's ter muito mais piada :)
Avatar do utilizador
Ivo_Timóteo
charm-Quark!
charm-Quark!
 
Mensagens: 579
Registado: Quarta Nov 15, 2006 7:25 pm
Localização: V. N. Gaia

Re: Números Reversíveis

Mensagempor jap em Segunda Jun 07, 2010 10:56 pm

Ivo_Timóteo Escreveu:(...)

Eu disse que não era muito difícil mas, para mim, a certa altura torna-se aborrecido :) Mas o pior problema mesmo é já não estar no secundário com muito tempo :) E o facto de, a certa altura, amortizar NP's ter muito mais piada :)


Oh, the good old days... :F

Um grande abraço, Ivo! :friends:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Terça Jun 22, 2010 9:27 am

Prof, peço desculpa por reabrir este tópico, mas sempre podia dar umas dicas sobre como fazer um algoritmo para resolver este problema que corra em menos de 1 minuto? :roll:

De facto, fiquei curioso sobre este problema e gostaria de o conseguir resolver ou pelo menos perceber como se resolve :)
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: Números Reversíveis

Mensagempor jap em Terça Jun 22, 2010 8:15 pm

Bruno Oliveira Escreveu:Prof, peço desculpa por reabrir este tópico, mas sempre podia dar umas dicas sobre como fazer um algoritmo para resolver este problema que corra em menos de 1 minuto? :roll:

De facto, fiquei curioso sobre este problema e gostaria de o conseguir resolver ou pelo menos perceber como se resolve :)


Eu não sei qual é o algoritmo rápido (não pensei mais sobre o assunto) mas sei que ele existe! :lol:

Any clues da comunidade quarkiana? :roll:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Quarta Jun 23, 2010 9:04 pm

Ah, pensei que o prof. soubesse, dado que deu o valor correcto à uns posts atrás... :lol:
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: Números Reversíveis

Mensagempor jap em Quarta Jun 23, 2010 10:55 pm

Bruno Oliveira Escreveu:Ah, pensei que o prof. soubesse, dado que deu o valor correcto à uns posts atrás... :lol:


O meu programa deu a resposta correcta no meu Mac em tempo útil...mas não num minuto! :F
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Números Reversíveis

Mensagempor Tharis em Quinta Jun 24, 2010 2:57 pm

Finalmente acabei de escrever uma solução decente. Primeiro, este é um problema de teoria dos números. Vou primeiro dar indicações para perceber como funciona o programa e depois vou dar uma solução que corre instantaneamente.

RN = Reversible Number

Este é um problema em que devemos usar uma approach Divide and Conquer. Neste caso podemos dividir o problema em 2 partes: calcular o número de RN com comprimento par e com comprimento ímpar.

COMPRIMENTO PAR

Convém notar um propriedade muito importante: NÃO EXISTE CARRY. Deixo a prova em SPOILER para não ocupar espaço (espero que alguém a leia porque deu um bocadinho de trabalho :|).

Prova


Este pormenor tem duas grandes implicações (uma delas é ele próprio): a soma de cada par de algarismos terá de ser menor que 10 e ímpar. Terá de ser ímpar, porque se for par, vai necessitar de um carry para se tornar ímpar e tal não acontece numa soma reversível. Para a soma ser ímpar, um deles terá de ser par e o outro ímpar.

Portanto basta pegar em todos os pares (i,j) de números menores que 10, verificar quais aqueles em que (i+j) < 10 e (i+j) % 2 == 0 e ir construíndo o nosso número reversível de dentro para fora ou de fora para dentro, tanto faz, com especial atenção que o par exterior não poderá conter qualquer 0.


COMPRIMENTO ÍMPAR

Nos de comprimento ímpar, a propriedade do carry já não se verifica. Podemos ser erradamente levados a pensar que não existem RNs com comprimento ímpar porque o algarismo do meio irá ser somado consigo próprio e 2k é sempre par para qualquer k natural. No entanto podemos encontrar rapidamente um contra-exemplo como 318 (318+813 = 1131). O que acontece é que o algarismo central recebe carry mas não fornece.

Vou resumir esta parte e apresentar a solução sem prova. Só existem RNs de comprimento ímpar quando duas condições se verificam:

    O comprimento é da forma 3+4k (3,7,11,...)
    A sequência de pares de algarismos tem a forma (ip)u(pi), em que i é um par cuja soma é ímpar e maior que 10, p um par cuja soma é par e menor que 10 e u um número inteiro tal que 0 <= u <= 4

É relativamente fácil ver a olho porquê se "brincarem" com os números. A prova será na linha da que apresentei nos comprimentos pares.


Agora que já passámos as matematiquices, vamos ao código.

Basicamente usa-se um dfs (Depth First-Search) para gerar todos os números. Começa-se com comprimento 0 e escolhe-se um par de algarismos. Avança-se para o comprimento 2 e escolhe-se outro par de algarismos. Fazemos isto até comprimneto = d e voltamos para trás e escolhemos outro par, etc. Quem não perceber bem, veja aqui.



O melhor é que eles só nos pedem o número de RNs e não os RNs em si, por isso, existe uma maneira mais fácil e rápida de calcular para qualquer comprimento.

Se considerarmos o comprimento máximo d, então o número de RNs é dado pela soma de RNs de comprimento par e de comprimento ímpar.

Podemos chegar facilmente a uma fórmula para cada usando combinatória simples.

Par: 20 \sum_{i=2}^{d} \left [ 30^{ \left \lfloor \frac{i-2}{2} \right \rfloor } \times (1-i \mod 2) \right ]

Ímpar: 5 \sum_{i=2}^{d} \left [ 20^{ \left \lfloor \frac{i}{4} + (1-i \mod 2) \right \rfloor } \times 25^{\frac{i}{4}} \times (1 - ((i-3) \mod 4))   \right ]

Os \left \lfloor \right \rfloor indicam a função floor, basicamente vai fazer o trabalho da divisão inteira.

Em código fica, de uma forma simples:
Código: Seleccionar Todos
def rev(d):
    return sum([20 * 30**((i-2)/2) * (1-i%2) + 20**(i/4+(i/2)%2) * 25**(i/4) * 5 * ((i-3)%4==0) for i in range(2,d+1)])


Código: Seleccionar Todos
>>> rev(9)
608720



Alguma dúvida é só deixar que eu tento ajudar.

Cumps ;)

P.S.: Não sei bem o formalismo de uma proof, algum matemático que queira corrigir está à vontade.
P.S.2: Acho que existe uma forma mais simples e limpa para as fórmulas, mas não sei bem.
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números Reversíveis

Mensagempor Bruno Oliveira em Quinta Jun 24, 2010 3:19 pm

Sem dúvida uma solução épica!! Uma das melhores que alguma vez já li.

Vou imprimir este post, e tentar percebe-lo mesmo bem, mas achei que a solução estava absolutamente genial.

Parabéns!! :hands:

E claro, um grande obrigado por partilhares aqui a solução, porque assim, aos poucos e poucos vou aprendendo :) (grão a grão enche a galinha o papo não é verdade?)
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: Números Reversíveis

Mensagempor jap em Quinta Jun 24, 2010 6:28 pm

Diabólico! :crazy:

Brilhante! :D

:hands:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Anterior

Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron