• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

magician

[4] Concatenar Números - Nível médio-alto

73 mensagens neste tópico

Tenho algumas dúvidas/reparos sobre este desafio:

Primeiro, uma concatenar o número 123 uma vez resulta no número 123123, senão a concatenação era do número 123 com nada. Concatenar é encadear/ligar/relacionar duas ou mais coisas.

Logo ou o exemplo 2 está errado ou a definição do problema tem de ser mudada.

Segundo, o que é

tempo de execução (...) aceitável e o gasto de memória também
?, "aceitável" não é quantificável e é sujeito a interpretação não deviam ser colocados pontos num desafio que dependam da interpretação de quem avalia.

Terceiro, o que é

o método trivial de concatenar o numero original numa string
? Para mim, o método trivial é usar buffers, para outros programadores pode não ser.
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ele sugeriu o trivial método de concaternar strings porque por exemplo, em python, era simples demais... Assim obriga um bocadinho mais de raciocinio.. ;)

Porque dizes que o exemplo 2 está errado? Não é o dos 1's?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Input: 121  11

Output: 1

Explicação:  121 é divisivel por 11.

121 foi o número de entrada, se é necessário uma ou mais concatenações, como está no enunciado, concatenar 121 uma única vez com ele próprio resultaria em 121121, logo ou o exemplo está errado ou o enunciado precisa ser mudado para permitir zero ou mais concatenações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fui eu que lancei o desafio, por isso sou eu a responder:

Primeiro, uma concatenar o número 123 uma vez resulta no número 123123, senão a concatenação era do número 123 com nada.

Tens alguma razão. O concatenar aqui significa quantas cópias do número são usadas. Talvez seja melhor colocar isso no enunciado do desafio.

Segundo, o que é ?, "aceitável" não é quantificável e é sujeito a interpretação não deviam ser colocados pontos num desafio que dependam da interpretação de quem avalia.

Aqui eu refiro-me a que o tempo de execução e gasto de memoria do processo (para mim) trivial de ir construindo uma string concatenando o número N é muito grande e não é aceitavel. No 4º exemplo tinhamos uma string com 9876*2 caracteres(digitos) e isso não é necessário (nem é de perto o caso com maior número de digitos).

Terceiro, o que é ? Para mim, o método trivial é usar buffers, para outros programadores pode não ser.

Usar buffers como? Eu expliquei o que era o trivial para mim.

Eu podia fazer uma restrição maior mas tava a dar uma grande dica para a resolução do problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Eu expliquei o que era o trivial para mim.

Esse é que é o problema ;), um desafio não pode conter regras que sejam subjectivas ou sujeitas a interpretações, senão eu proponho uma solução, tu não aceitas porque achas que consome muito tempo ou o método de concatenação é trivial, seja lá isso o que for, e como fico?

Pode ser uma solução válida que não é aceite.

Talvez esteja a ver mal a ideia dos desafios, mas acho que não deviam existir regras que fossem avaliadas de forma diferente com diferentes utilizadores.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ambas as soluções apresentadas estão erradas.

gooden: não testaste os exemplos. A tua solução não detecta os casos em que é impossivel e o programa entra em ciclo infinito.

JoaoRodrigues: O caso de N = 1 não é o unico caso em que é impossivel. Aliás, se N = 1 e K = 1 , há resposta: 1.

E ambos estão a violar a restrição, porque estão a concatenar o número até encontrarem solução. Aliás, conseguem tratar números tipo 10^1000 ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Esse é que é o problema :), um desafio não pode conter regras que sejam subjectivas ou sujeitas a interpretações, senão eu proponho uma solução, tu não aceitas porque achas que consome muito tempo ou o método de concatenação é trivial, seja lá isso o que for, e como fico?

Eu não acho que seja assim tão subjectivo. Eu digo que soluções que calculem o número que é divisivel por k, não são aceites.

com um input N = 1.000.000.000  e  K = 99.999 a resposta é 99.999, ou seja, um número com 999.990 digitos. Não é preciso mostrá-lo...

Pode ser uma solução válida que não é aceite.

Pode ser uma solução que calcule a resposta certa, mas demore um ano a executar ;) Normalmente não são aceites :)

No caso deste exercicio, é uma hiperbole, mas as restrições existem para que se procurem soluções boas.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ia dizer o que o mogers disse, de modo que para não repetir, vou tentar explicar o problema.

Imaginem o número 25 e K.

Não há qualquer necessidade de testar de 25 é divisivel por K, senao for, se 2525 é divisivel, etc..

Há métodos que dão a solução correcta sem estar a fazer estas concatenações que geram números enormes..

Provavelmente devia estar mais claro, mas o desafio é esse: pensei numa maneira de saber quantos números precisam.

(Desculpem o offtopic, mas mogers, tiraste este problema da UVA? Resolvi um muito parecido no estágio das IOI à uns anos (a única diferença é que não se lia o N, usávamos o número 1))

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. Foi do último concurso do topcoder. Demorei 27 min a resolver :s houve pessoal a resolver isto em menos de 2 minutos  :-[

Eu não sei se o pessoal está a testar os exemplos dados nos desafios. Em VBnet ou Python pode-se ter um número de 10000 digitos numa variavel e calcular o resto da divisão por um inteiro? :s

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. Foi do último concurso do topcoder. Demorei 27 min a resolver :s houve pessoal a resolver isto em menos de 2 minutos  :-[

Eu não sei se o pessoal está a testar os exemplos dados nos desafios. Em VBnet ou Python pode-se ter um número de 10000 digitos numa variavel e calcular o resto da divisão por um inteiro? :s

Não programo python, em VB não.

Em Scheme por exemplo pode-se..

De qualquer forma, quem quiser resolver o problema que se guie pelo meu post anterior.

Grau de dificuldade mudado, o desafio não é fácil.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não. Foi do último concurso do topcoder. Demorei 27 min a resolver :s houve pessoal a resolver isto em menos de 2 minutos  :-[

Eu não sei se o pessoal está a testar os exemplos dados nos desafios. Em VBnet ou Python pode-se ter um número de 10000 digitos numa variavel e calcular o resto da divisão por um inteiro? :s

Eu testei nos exemplos que deste e funcionou bem. Náo entendi muito bem o que querias dizer com violar a restrição, porque tu falaste em concatenar numa string e o que eu faço... bem.. não é propriamente concatenar numa string, mas é "matematicamente" como eu considero que devo fazer..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Grau de dificuldade mudado, o desafio não é fácil.

Pois, já tinha sugerido ao magician.

Uma dica: este problema pode ser resolvido eficientemente apenas com 5 variaveis inteiras de 64 bits.

Eu testei nos exemplos que deste e funcionou bem. Náo entendi muito bem o que querias dizer com violar a restrição, porque tu falaste em concatenar numa string e o que eu faço... bem.. não é propriamente concatenar numa string, mas é "matematicamente" como eu considero que devo fazer..

Eu pensava que não se conseguia representar números tão grandes. De qualquer forma, eu queria dizer que não se deve calcular exactamente o número que é divisivel por k. No exemplo que dei à pouco, tinhas um número com quase 1 milhão de digitos.. não é preciso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu testei nos exemplos que deste e funcionou bem. Náo entendi muito bem o que querias dizer com violar a restrição, porque tu falaste em concatenar numa string e o que eu faço... bem.. não é propriamente concatenar numa string, mas é "matematicamente" como eu considero que devo fazer..

Lê o meu outro post. É possível resolver o problema sem testar todas as concatenações possíveis.

Envolve é matemática.

PS: Sinto-me tentado em dizer a palavra mágica..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não se devia fazer alguma coisa quanto às soluções apresentadas, mas que não estão correctas? Não digo que apagar os posts seja a melhor opção, mas talvez colocar um comentário...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Todas as soluções apresentadas até à do djthyrax em python não estão correctas. O caso de ser impossivel não é tão simples como um simples teste ao N e K iniciais.

Quanto as perguntas do djthyrax

Vejam se estes estão correcto:

35 987655

-> 24219

36 987

-> 69

35 982

-> -1

35 983

-> 491

Estão todos correctos. Mas para N = 22 e K = 4 , a resposta é -1. O teu programa não dá a resposta certa. Perceber porque é que é impossivel é uma grande ajuda para resolver o problema.

Já foi dito aqui que não devem usar bignumbers. No caso do python nem se apercebem porque a linguagem consege usar inteiros muito grandes (nestes exemplos tinhas um numero com quase 50000 digitos) sem qualquer alteração do código. No caso de C ou outras linguagens isto não acontece.

Quando disse que este problema pode ser resolvido em qualquer linguagem sem problemas, referia-me a isto. Não é preciso usar números maiores do que inteiros de 64 bits, ou seja, números até 2^64 (números de 20 digitos)  ;)

PS: este é um problema de matemática. É preciso pensar um pouco para dar a volta aos números :)

Edit: Nas linguagens que já usei, conseguia sempre usar inteiros de 64 bits, se existir alguma linguagem usada aqui que não dê, tenho que editar os meus posts ..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

mogers, eu pus o belo do aviso no meu código de propósito. Só o deixei lá estar porque achei roto estar a tirar ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Será que era possível colocar mais alguns exemplos em que dê -1?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Será que era possível colocar mais alguns exemplos em que dê -1?

Sim

N = 1 e K = 5

N = 2 e K = 15

N = 11 e K = 30

N = 10 e K = 8

Há muitos ...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Há muitos ...

Isso já eu percebi. E já encontrei 4 condições que fazem com que o resultado seja -1, mas podem ainda não cobrir todos os casos, por isso é que pedia mais alguns exemplos.

De qualquer modo, vou colocar a minha solução.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso em haskell ;)  Não consigo analisar :)

Mas para tornar mais claro o que disse anteriormente: eu acho que não é possível com uma condição ou conjunto de condições sobre N e K dados no input determinar se é impossivel ou não. Não tenho a certeza porque era preciso provar. Há uma forma mais fácil de ver isso.

Apesar de não perceber haskell, acho que já chegaste à solução B) só não creio que sejam suficientes essas 4 condições para determinar se é impossivel. Vou tentar arranjar um caso em que o código não dê (se conseguir passar esse código para outra linguagem :)).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A parte mais complicada de perceber tem mais ou menos isto:

se existe a tal que 2^a==y então:

  if mod x y==0 then 1 else -1

se existe a tal que 5^a==y então

  if mod x y==0 then 1 else -1

se mod x 2/=0 && mod y 2==0 então

  -1

se mod x 5/=0 && mod y 5==0 então

  -1

senão faux

Não sei se as condições são suficientes, mas penso que pelo menos essas são válidas (não fiz uma demonstração, mas tenho uma ideia de como a fazer).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim

N = 1 e K = 5

N = 2 e K = 15

N = 11 e K = 30

N = 10 e K = 8

Há muitos ...

Eu já tinha descortinado isso, mas não consigo encontrar a relação matematicamente...
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Repara na relação existente entre os números resultantes das várias concatenações.

Dá para ver que o 5 e o 2 tem uma particularidade em relação ao outros números primos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora