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

anolsi

ONI 2008 - Qualificação - Problema F

10 mensagens neste tópico

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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.

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