Ir para o conteúdo
anolsi

ONI 2008 - Qualificação - Problema F

Mensagens Recomendadas

anolsi    16
anolsi

Estou a treinar para as ONI e o problema F está-me a dar probelmas, porque obtenho Time Limit Exceeded.  :wallbash:  E não consigo arranjar maneira de o tornar mais rápido.  :wallbash: Será que me poderiam ajudar com umas dicas?

#include <stdio.h>
#include <math.h>

#define LIMITE 46341 /* raiz quadrada de 2147483648, arredondada por excesso*/
char crivo[LIMITE];

int CriaCrivo(){
    unsigned int i, j;

crivo[0] = 0; crivo[1] = 1;
    for(i = 2; i < LIMITE; i++) 
	crivo[i] = 1;
    for(i = 2; i*i <= LIMITE; i++)
	if(crivo[i] == 1) {
		for(j = i; i*j < LIMITE; j++) 
			crivo[i*j] = 0;
	}
    return(0);
}

int main() {
  char eolimp;
  int ncasos, m;
  unsigned int k, conta;
  unsigned long inf, sup, i;

  CriaCrivo();
  scanf("%d", &ncasos); /* Obtêm o número de casos (1 <= x <= 10)*/ 
  for(m = 1; m <= ncasos; m++) {
    conta = 0;
    scanf("%lu %lu", &inf, &sup); /*Lê os dois limites (1 <= x < 2^31 = 2147483648) */
    for(i = inf; i <= sup; i++) {
	eolimp = 1;
    for(k = 1; k <= i && k < LIMITE; k++) {
      if(crivo[k])
	    if(i % k == 0 && i % (k * k) != 0) {
	      eolimp = 0;
	      break;
	    }
	}
    if(eolimp) conta++;
}
    printf("%d\n", conta);
  } 
  return(0);
}

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrosorio    5
pedrosorio

Imagina que o input é algo deste género:

5

1 1000

1 1000

1 1000

1 1000

1 1000

Não achas que não faz sentido estares a calcular se são olímpicos ou não 5 vezes? Eu fazia uma array onde marcava todos os números que já tivesse verificado se eram olímpicos ou não - 0 não verifiquei, 1 verifiquei e é, 2 verifiquei e não é - por exemplo.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
anolsi    16
anolsi

Imagina que o input é algo deste género:

5

1 1000

1 1000

1 1000

1 1000

1 1000

Não achas que não faz sentido estares a calcular se são olímpicos ou não 5 vezes? Eu fazia uma array onde marcava todos os números que já tivesse verificado se eram olímpicos ou não - 0 não verifiquei, 1 verifiquei e é, 2 verifiquei e não é - por exemplo.

Boa ideia. Quase como o crivo...

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
pedrosorio    5
pedrosorio

Por acaso é parecida =)

Não sei se isso resolverá o problema do tempo. Se calhar ainda há optimizações que podes fazer na verificação.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

É impossível fazeres um ciclo de 1 a 2^31 e passar no tempo.

O truque neste problema está em não verificar se um número é olímpico, mas sim gerar todos os números olímpicos.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
anolsi    16
anolsi

Bem alterei o código e ficou assim:

#include <stdio.h>
#include <math.h>

#define LIMITE 46341 /* raiz quadrada de 2147483648, arredondada por excesso*/
char crivo[LIMITE];
char olimpo[LIMITE];

int CriaCrivo(){
    unsigned int i, j;

crivo[0] = 0; crivo[1] = 1;
    for(i = 2; i < LIMITE; i++) 
	crivo[i] = 1;
    for(i = 2; i*i <= LIMITE; i++)
	if(crivo[i] == 1) {
		for(j = i; i*j < LIMITE; j++) 
			crivo[i*j] = 0;
	}
    return(0);
}

int CriaOlimpo(unsigned int min, unsigned int max){
unsigned int i, k;

for(i = min; i <= max; i++) 
	olimpo[i] = 1;

    for(i = min; i <= max; i++) {
    for(k = 1; k <= i && k < max; k++) {
      if(crivo[k])
	    if(i % k == 0 && i % (k * k) != 0) 
		  olimpo[i]= 0;
}

}
return (0);
}
int main() {
  int ncasos, m;
  unsigned int /*k,*/ conta;
  unsigned long inf, sup, i;

  CriaCrivo();
  for (i = 0; i<=LIMITE; i++)
olimpo[i]= -1;
  scanf("%d", &ncasos); /* Obtêm o número de casos (1 <= x <= 10)*/ 
  for(m = 1; m <= ncasos; m++) {
    conta = 0;
    scanf("%lu %lu", &inf, &sup); /*Lê os dois limites (1 <= x < 2^31 = 2147483648) */
    for (i= inf; i<=sup; i++){
	switch (olimpo[i]){
		case 1: conta++; break;
		case -1: CriaOlimpo(i, sup); i--; break;
	}
}
    printf("%d\n", conta);
  } 
  return(0);
}

Estou a procurar os olímpicos e não verificar se ele é olímpico, mas continua igual.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

Eu não preciso de olhar muito para o teu código, a partir do momento que tens isto

for (i= inf; i<=sup; i++){

é impossível ele passar no tempo, só isso.

Olha que o que tu estás a fazer é verificar, e não a gerar os números.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Experimenta dar a volta ao problema, em vez de testar se um número é olimpico, gera os número olimpicos e guarda-os.

Para isso, repara que um número olimpico é resultado de um número primo ao quadrado vezes qualquer coisa (1,2....).

Para resolver isto eficientemente tens de ter algumas noções de teoria dos números (primos, factorização de números...)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Imagina que o input é algo deste género:

5

1 1000

1 1000

1 1000

1 1000

1 1000

Não achas que não faz sentido estares a calcular se são olímpicos ou não 5 vezes? Eu fazia uma array onde marcava todos os números que já tivesse verificado se eram olímpicos ou não - 0 não verifiquei, 1 verifiquei e é, 2 verifiquei e não é - por exemplo.

Não podes porque não tens 2^31 bits de memória para guardar essas verificações, nem tempo para fazer um ciclo com 2^31 iterações. Solução é mesmo gerar os números.

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