Ir para o conteúdo
magician

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

Mensagens Recomendadas

Knitter    101
Knitter

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
JoaoRodrigues    0
JoaoRodrigues

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?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Knitter    101
Knitter

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Knitter    101
Knitter
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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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 ?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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))

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
JoaoRodrigues    0
JoaoRodrigues

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..

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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..

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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 ..

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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 ...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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 :)).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

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).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

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...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    311
Rui Carlos

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.

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


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade