Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

Warrior

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

Mensagens Recomendadas

Rui Carlos    309
Rui Carlos

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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?

Partilhar esta mensagem


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

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pcaldeira    0
pcaldeira

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Gooden    0
Gooden

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:

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pcaldeira    0
pcaldeira

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
JoaoRodrigues    0
JoaoRodrigues

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)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
djthyrax    11
djthyrax

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?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

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 a nossa Política de Privacidade