Jump to content
Warrior

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

Recommended Posts

mogers

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

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


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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)..

Share this post


Link to post
Share on other sites
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?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
mogers

São coisas diferentes!

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


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
skin

Hmm, então eu depois corrijo que agora tenho de almoçar para sair :thumbsup: .


Our lives begin to end the day we become silent about things that matter - Martin Luther King

Share this post


Link to post
Share on other sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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:

Share this post


Link to post
Share on other sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
mogers

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


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
Gooden

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

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

Share this post


Link to post
Share on other sites
mogers

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

Sim. O 2º exemplo ilustra isso. Experimentaste?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
djthyrax

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


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
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..

Share this post


Link to post
Share on other sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.