Jump to content
Sign in to follow this  
skiller10

ONI 2010 A-qualif

Recommended Posts

skiller10

Boas,

tive a resolver este problema

http://www.dcc.fc.up.pt/oni/problemas/2010/qualificacao/probA.html

no entanto, embora me tenham dados todos os casos correctos, ao submeter apenas tive pontuação 40.

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{
    int qdiv, ncasos, cont;

cin >> qdiv; 
cin >> ncasos;

    int lims[ncasos][2], result[ncasos];
    
//Inicializar:
for(int i=0; i<ncasos; i++){
    result[i] = 0;        
}      

//Ler intervalos e calcular:
for(int i=0; i<ncasos; i++){
    cin >> lims[i][0] >> lims[i][1];
}
for(int i=0; i<ncasos; i++){
    for(int j=lims[i][0]; j<=lims[i][1]; j++){
        cont = 0;
        for(int k=1; k<=j; k++){
            if(j%k==0){
                cont++;
            }        
        }
        if(cont==qdiv){
            result[i] ++;               
        }
    }       
}     

//Output:
for(int i=0; i<ncasos; i++){
    cout << result[i] << endl;        
}   

//system("PAUSE");
return 0;
}

Alguém me consegue dar uma ajuda?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Repara que os nºs dos intervalos estão sempre entre 1 e 100.000

Seria bom pré-calculares o nº de divisores de cada número antes de processar cada caso, senão estás a recalcular várias vezes o nº de divisores do mesmo número.


"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
pedrosorio

As Olimpíadas têm em conta a correcção e a eficiência da tua solução. Ela é de facto correcta, mas se olhares para os limites do problema vês que não pode funcionar:

1 <= Intervalos <= 1000

1 <= Ai <= Bi <= 100000

Se tiveres 1000 intervalos todos eles com Ai=1 e Bi=100000, vais ter que testar o número de divisores 1000*100000 vezes, e a  testar o número de divisores é proporcional ao número em causa pelo que claramente são operações a mais para que o programa corra num tempo aceitável.

Se reparares o problema diz:

"Para um conjunto de casos de teste valendo 40% dos pontos, o número de intervalos é inferior a 10 e quer a quantidade de divisores, quer os números que limitam o intervalo, são inferiores 1000."

E são exactamente estes casos que o teu algoritmo consegue resolver no tempo permitido. Vais ter que pensar numa forma de o resolver mais eficientemente.

Dica: não calcules a mesma coisa várias vezes.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
skiller10

ja melhorei um pouco e obtive 60

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{
    int qdiv, ncasos, min=100001, max=0;

cin >> qdiv; 
cin >> ncasos;

    int lims[ncasos][2], result[ncasos];
    
//Inicializar:
for(int i=0; i<ncasos; i++){
    result[i] = 0;        
}      

//Ler intervalos:
for(int i=0; i<ncasos; i++){
    cin >> lims[i][0] >> lims[i][1];
}

//Calcular
for(int i=0; i<ncasos; i++){
    if(lims[i][1]>max){
        max = lims[i][1];
    }
    if(lims[i][0]<min){
        min = lims[i][0];
    }
}        

    int divs[max];

for(int i=0; i<max; i++){
    divs[i] = 0;
}

for(int num=min; num<=max; num++){
    for(int i=1; i<=num; i++){
        if(num%i==0){
             divs[num-1]++;
        }
    }
}

for(int i=0; i<ncasos; i++){
     for(int j=lims[i][0]; j<=lims[i][1]; j++){
          if(divs[j-1]==qdiv){
               result[i]++;   
          }
     }
}
    
//Output:
for(int i=0; i<ncasos; i++){
    cout << result[i] << endl;        
}   

//system("PAUSE");
return 0;
}

Estou a calcular os divisores de cada número desde o limite inferior mais baixo até ao limite superior mais alto.

Alguma dica para melhorar e obter os 100 pontos?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
pedrosorio

Já está melhor, mas repara que ao longo de todo o problema só tens que saber quantos números têm exactamente D divisores.

Ou seja, tens um array com uma série de valores (o número de divisores de cada número), como é que o podes alterar para que possas calcular facilmente quantos D existem num intervalo [Ai,Bi]?

Dica: Como é que alterarias o array para saber quantos D existem em [0,Bi]? E em [0,Ai[?


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
skiller10

Fiz umas pequenas alterações e deu-me a mesma pontuação, acho que nao percebi a 100% o que disseste

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{
    int qdiv, ncasos, min=100001, max=0, divs;

cin >> qdiv; 
cin >> ncasos;

    int lims[ncasos][2], result[ncasos];
    
//Inicializar:
for(int i=0; i<ncasos; i++){
    result[i] = 0;        
}      

//Ler intervalos:
for(int i=0; i<ncasos; i++){
    cin >> lims[i][0] >> lims[i][1];
}

//Ver menor limite inferior e maior limite superior:
for(int i=0; i<ncasos; i++){
    if(lims[i][1]>max){
        max = lims[i][1];
    }
    if(lims[i][0]<min){
        min = lims[i][0];
    }
}        

//Calcular divisores:
for(int num=min; num<=max; num++){
    divs = 0;
    for(int i=1; i<=num; i++){
        if(num%i==0){
             divs++;
        }
    }
    if(divs==qdiv){
        for(int i=0; i<ncasos; i++){
             if(num>=lims[i][0] && num<=lims[i][1]){
                 result[i]++;   
             }
        }            
    }
}
  
//Output:
for(int i=0; i<ncasos; i++){
    cout << result[i] << endl;        
}   

//system("PAUSE");
return 0;
}


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
pedrosorio

Em teoria isso devia melhorar o tempo de execução. Mas não chega. Algumas coisas que estás a fazer mal:

- Verificas todos os números de 1 até num para ver se são divisores - qualquer número em ]num/2 , num[ não é divisor obviamente, por exemplo - na realidade se i for divisor de num então num/i também é divisor de num (porque num/(num/i) = i). Pelo que quando encontras um divisor podes contar 2 (quase) sempre e só precisas de verificar divisores até um certo número (qual?).

- Continuas a percorrer todos os casos de cada vez que encontras um número com D divisores. Isso é capaz de dar para passar, mas há outra maneira de processar o vector divs que te permite calcular rapidamente quantos números têm D divisores num dado intervalo. Dica: se tens o vector [0,1,0,0,0,1,1,1,0,0,0,1,0,1] como é que o podes alterar para depois conseguires calcular facilmente o número de 1's até uma posição i qualquer? E depois de feita essa alteração como é que calculas o número de 1's entre i e j?


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
skiller10

Já corrigi a parte de qualquer numero no intervalo ]num/2 , num[ não ser divisor desse numero, mantém-se a mesma pontuação.

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int qdiv, ncasos, min=100001, max=0, divs;

cin >> qdiv; 
cin >> ncasos;

    int lims[ncasos][2], result[ncasos];
    
//Inicializar:
for(int i=0; i<ncasos; i++){
    result[i] = 0;        
}      

//Ler intervalos:
for(int i=0; i<ncasos; i++){
    cin >> lims[i][0] >> lims[i][1];
}

//Ver menor limite inferior e maior limite superior:
for(int i=0; i<ncasos; i++){
    if(lims[i][1]>max){
        max = lims[i][1];
    }
    if(lims[i][0]<min){
        min = lims[i][0];
    }
}        

//Calcular divisores:      
for(int num=min; num<=max; num++){
    divs = 1;
    for(int i=num/2; i>=1; i--){
        if(num%i==0){
             divs++;
        }
    }
    if(divs==qdiv){
        for(int i=0; i<ncasos; i++){
             if(num>=lims[i][0] && num<=lims[i][1]){
                 result[i]++;   
             }
        }            
    }
}

//Output:
for(int i=0; i<ncasos; i++){
    cout << result[i] << endl;        
}   

//system("PAUSE");
return 0;
}

Apenas posso contar um divisor como 2 quando o divisor for par, certo? mas surge-me outro problema se contar 2, porque o for vai andar apenas uma posição e não posso avançar logo para o outro divisor/2 porque podias estar a ignorar alguns divisores entre divisor e divisor/2.

A única maneira que sei para ver quantos 1's existem é com um ciclo for, e ir comparando o valor da posição do array. Há outra maneira de o fazer?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
pedrosorio

Tu respondes sempre com código às minhas perguntas ;) Não te fazia mal pensar um bocadinho, responder às perguntas e depois tentar escrever o código :D

Vamos ver um exemplo - achar os divisores de 20:

1 é divisor -> logo 20/1=20 também é

2 é divisor -> logo 20/2=10 também é

3 não é divisor

4 é divisor -> logo 20/4=5 também é

5 é divisor... mas calma... já o contámos... e se reparares já contámos todos os divisores maiores que 4, portanto só precisamos de fazer um ciclo de 1 até 4.

Temos 6 divisores.

Achar os divisores de 25:

1 é divisor -> logo 25/1=25 também é

2 não é divisor

3 não é divisor

4 não é divisor

5 é divisor -> logo 25/5=5 também é (mas neste caso não contamos 2 porque num/i = i)

E repara que já não precisamos de contar mais. 25 tem 3 divisores.

Consegues perceber até que número é que tens que ir para verificar todos os divisores de num?

Em relação à maneira de ver quantos 1's existem  e se fizeres um ciclo for ao longo do array e em cada posição meteres quantos 1's é que já apareceram até ali? i.e. se tiveres um array [0,1,0,0,0,1,1,1,0,0,0,1,0,1], consegues transformá-lo em [0,1,1,1,1,2,3,4,4,4,4,5,5,6], e a partir deste se eu te perguntar quantos 1's havia entre a posição 4 e a posição 6 sabes calcular?


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
skiller10

Eu ontem estava uma beca stressado porque a pensar que tinha tudo feito e a funcionar, afinal estava bem longe disso  ;)

Agora que li com mais calma o que tinhas dito, apenas é preciso calcular os divisores enquanto num/divisor>divisor e ter em atenção para os casos em que:

I é divisor, e num/I=I, para apenas contar uma vez.

Percebi tudo correctamente até aqui acho.

Em relação aos 1's. pode ser algo do genero:

se x for divisor entao

    para i=x, i<num, i++

          array ++;

Depois para calcular torna-se simples porque basta fazer array[j]-array. Mas ao fazer isto não há perda de eficiencia, porque estamos a criar um array que pode ser muito grande?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

apenas é preciso calcular os divisores até num/5

edit: entretanto corrigiste.

num/divisor>divisor

ou seja, até RaizQuadrada(Num) ou sqrt(Num)


"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
skiller10

Já submeti e obtive os 100pontos, mas vou ainda implementar a parte dos 1's.

Obrigado a todos pela ajuda ;)

edit:

Estive a pensar sobre este assunto e lembrei-me que a solução pode ser melhorada, porque se por exemplo forem dois intervalos:

1-10

90000-100000

O programa vai calcular tudo desde 1 a 100000, ou seja 100000x, quando apenas é necessário fazer o calculo para 10010 números.

Alguém sabe uma forma eficiente de ver quais os intervalos necessários e os intervalos em que não é preciso calcular? Tipo juntar os intervalos que são dados. Exemplo:

1-10

1-15

11-15

1-5

20-30

podia ficar simplesmente:

1-15

20-30


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

edit:

Estive a pensar sobre este assunto e lembrei-me que a solução pode ser melhorada, porque se por exemplo forem dois intervalos:

1-10

90000-100000

O programa vai calcular tudo desde 1 a 100000, ou seja 100000x, quando apenas é necessário fazer o calculo para 10010 números.

Alguém sabe uma forma eficiente de ver quais os intervalos necessários e os intervalos em que não é preciso calcular? Tipo juntar os intervalos que são dados. Exemplo:

1-10

1-15

11-15

1-5

20-30

podia ficar simplesmente:

1-15

20-30

Numa prova como as ONI, uma coisa destas nunca de vai ajudar a ter mais pontos. São o tipo de optimizações que só te faria perder tempo porque os testes vão ser sempre exaustivos ;)

edit: btw, uma forma eficiente de calcular os divisores todos dos números seria algo inspirado no http://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes

// warning: código escrito directamente aqui sem testar
int divisores[MAX+10];
// <init divisores a 1>
for (i = 2 ; i + i <= MAX ; i++ )
     for (j = i+i ; j <= MAX ; j+= i )
          divisores[j]++;


"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
skiller10

Hum ok, obrigado ;)


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

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
Sign in to follow this  

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