Página 2 de 2

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 6:49 am
por Bruno Oliveira
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?

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 11:06 am
por Ivo_Timóteo
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 :)

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 6:40 pm
por Tharis
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.

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 8:32 pm
por Bruno Oliveira
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:

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 8:52 pm
por Tharis

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 10:47 pm
por Ivo_Timóteo
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 :)

Re: Números Reversíveis

MensagemEnviado: Segunda Jun 07, 2010 10:56 pm
por jap
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:

Re: Números Reversíveis

MensagemEnviado: Terça Jun 22, 2010 9:27 am
por Bruno Oliveira
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 :)

Re: Números Reversíveis

MensagemEnviado: Terça Jun 22, 2010 8:15 pm
por jap
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:

Re: Números Reversíveis

MensagemEnviado: Quarta Jun 23, 2010 9:04 pm
por Bruno Oliveira
Ah, pensei que o prof. soubesse, dado que deu o valor correcto à uns posts atrás... :lol:

Re: Números Reversíveis

MensagemEnviado: Quarta Jun 23, 2010 10:55 pm
por jap
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

Re: Números Reversíveis

MensagemEnviado: Quinta Jun 24, 2010 2:57 pm
por Tharis
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.

Re: Números Reversíveis

MensagemEnviado: Quinta Jun 24, 2010 3:19 pm
por Bruno Oliveira
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?)

Re: Números Reversíveis

MensagemEnviado: Quinta Jun 24, 2010 6:28 pm
por jap
Diabólico! :crazy:

Brilhante! :D

:hands: