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

Warrior

[3] Números amigos - Nível de aprendizagem

43 mensagens neste tópico

"nos digam quantos pares não ordenados e diferentes de números amigos existem. "

isto significa que (1,9) é diferente de (9,1) ?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

"nos digam quantos pares não ordenados e diferentes de números amigos existem. "

isto significa que (1,9) é diferente de (9,1) ?

Se são pares não ordenados, acho que (1,9) deveria ser igual a (9,1)..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso fez-me um pouco de confusão. Nesse caso dá para resolver isto em O( N ), se não me engano.

Eu tenho k sair do pc, vi as soluções apresentadas. A do pcaldeira assume que o limite dos numeros do input é 5000, mas isso não foi especificado. A do skin não conta pares distintos. Falha naquele caso do 1,9,9,1 acho eu (mas isso foi uma olhadela na diagonal).

PS: é possivel saber o limite máximo dos numeros do input?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A do pcaldeira assume que o limite dos numeros do input é 5000, mas isso não foi especificado.

Explicação de Input

Linha 1 - um inteiro N (2 <= N <= 5000), representando o número de inteiros a ler. (não deve ser considerado)

Linhas 2 - N+1 - N inteiros a ser considerados

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

São coisas diferentes!

Eu refiro-me ao valor dos números do input e não à quantidade. (talvez não tenha explicado bem :/)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Exactamente, ia agora mesmo dizer isso.

O pcaldeira assume que o tamanho de cada número é < 5000, mas só é dito que são no máximo 5000 números, coisas diferentes.

A do skin falha naquele caso (1,9), (9,1) (são de factos iguais, dava para perceber pelo segundo input) e também conta várias vezes repetidos.

Comecei a colocar restrições e compliquei um bocado demais, se calhar devia estar um patamar acima.

Já agora, a solução que pensei é O(N log N), se existir melhor estou interessado em ver.

Edit: Acho que com uma Trie dá mesmo O(N), mas tenho que pensar melhor, vou almoçar.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu fiz agora rápidamente uma solução com 20 linhas em O(N log N). Se soubessemos o limite do tamanho dos números era trivial passar para O( N ). Mesmo assim, com uma hash table consegue-se na mesma sem saber o tal limite.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O 5000 foi um número como podia ter sido outro qualquer, por acaso usei o mesmo para não ter que definir outra constante. Para inputs maiores, basta declarar o array seen[][] com outras dimensões (sim, eu sei que é bastante ineficiente a nível de memória, mas como o limite não foi especificado, não dei grande importância a isso).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em php:

<?php
$nums = array(6, 1, 9, 2, 8, 4, 22);
$quantd = 0;
for ($i = 0; $i < count($nums); $i++) {
for ($j=$i+1; $j < count($nums); $j++) {
	if ( (($nums[$i]+$nums[$j]) % 10) == 0 ) {
		$quantd++;
		echo "(" . $nums[$i] . "," . $nums[$j] . ")<br />";
	}
}
}
echo $quantd;
?>

Adaptar o Input é fácil :) mas dava mt trabalho tar a pôr ai uns post e uns forms :D.

E para este desafio só vou escrever em PHP, porque o C já está escrito e porque em Perl e JavaScript é só adaptar o que já foi feito no PHP dando assim hipóteses ao godeen :D

Tiveste bem skin xD Brevemente posto aqui em vb.net

5 min e ja posto :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O 5000 foi um número como podia ter sido outro qualquer, por acaso usei o mesmo para não ter que definir outra constante. Para inputs maiores, basta declarar o array seen[][] com outras dimensões (sim, eu sei que é bastante ineficiente a nível de memória, mas como o limite não foi especificado, não dei grande importância a isso).

Desafio: admitindo que sabes o limite máximo dos números, resolve o exercicio com tempo O(N).

Eu não vou postar já a minha proposta de solução. Acho que devia haver um periodo em que não se pode submeter, senão o pessoal é tentado a olhar para as soluções antes de pensar em resolver os problemas.

Gooden: a tua solução falha no segundo exemplo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Desafio: admitindo que sabes o limite máximo dos números, resolve o exercicio com tempo O(N).

Eu não vou postar já a minha proposta de solução. Acho que devia haver um periodo em que não se pode submeter, senão o pessoal é tentado a olhar para as soluções antes de pensar em resolver os problemas.

Ok, vou pensar nisso. Agora vou sair, mas quando voltar a casa tento uma solução mais rápida.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pá, a minha solução está trivial e peca por contar duplamente com os pares. Mas uma solução simples para contar os pares certos é dividir o número de pares por 2... fora isso, ainda vou pensar numa solução que verifique e só faça o output dos pares únicos (x,y == y,x)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

gooden: a tua solução não está na mesma? acho que continua a contar duplicados...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não... modifiquei a de c# que tava a dar erros

cm assim??? tas a dizer tipo (2,8) e (8,2)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

cm assim??? tas a dizer tipo (2,8) e (8,2)

Sim. O 2º exemplo ilustra isso. Experimentaste?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Há MUITAS soluções erradas neste desafio.

A do skin em PHP, (conta os pares vezes demais, pode por exemplo contar (1,9) várias vezes), as do gooden e JoaoRodrigues idem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Postei agora a minha solução em Python, agradecia comentários ;)

Parece-me correcto, não o mais eficiente possível mas isso já é outro pormenor, para o que era pedido no enunciado (limite de 5000) funciona perfeitamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Parece-me correcto, não o mais eficiente possível mas isso já é outro pormenor, para o que era pedido no enunciado (limite de 5000) funciona perfeitamente.

Pois, eu sei disso. Reparei que há uma relação qualquer ali que eu não tou a descortinar... Dicas?
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, eu sei disso. Reparei que há uma relação qualquer ali que eu não tou a descortinar... Dicas?

Assim que eu tiver um bocadinho de tempo vou resolver alguns dos problemas e já explico a solução. Se não tivesse 3 frequências esta semana..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, eu sei disso. Reparei que há uma relação qualquer ali que eu não tou a descortinar... Dicas?

Não é preciso somar cada par de números e verificar se a soma % 10 == 0  ;)

O desafio é como :)  Mais logo posto a minha solução.

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