TEMA

PROBLEM 1926 - URI Fórum 1.0

beecrowd preguntado 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • eldsmonteiro respondido 8 years ago

    Dica: Não dá pra perceber pelo costume, mas o problema não necessariamente diz que X e Y estão em ordem.

    MOD

  • Josenaldo respondido 7 years ago

    Usei a busca binária e deu ACC. Valeu, Dranoel123!

  • eldsmonteiro respondido 7 years ago

    A dica é evitar pesquisas lineares. Se for pra usar pesquisa, use pesquisa binária. Mas com esse limite pequeno é possível armazenar informações para todas as possíveis respostas.

    MOD

  • Josenaldo respondido 7 years ago

    Gerei à parte todos os gêmeos entre 1 e 1000000 e startei arr[16337] com eles (o que custou 0.268s no URI). Ainda assim, TLE.

    int indexX = std::distance(arr, std::find(arr, arr+16337, x));
        int indexY = std::distance(arr, std::find(arr, arr+16337, y));

        while(indexX==16337){
            x++;
            indexX = std::distance(arr, std::find(arr, arr+16337, x));
        }

        //std::cout << indexX << " " << indexY << std::endl;

        while(indexY==16337){
            y--;
            indexY = std::distance(arr, std::find(arr, arr+16337, y));
        }

        std::cout << indexY - indexX + 1 << std::endl;

  • eldsmonteiro respondido 7 years ago

    Josenaldo, a ideia mais viável nesse caso seria armazenar todas as informações importantes, em meu código resolvi com leitura e o único processamento antes da escrita foi acesso de vetores.

    Dica: Nunca use float em questões que não tem entrada ou saída float, parece dar certo em nossas cabeças, mas no pc a história é outra.

    MOD

  • Josenaldo respondido 7 years ago

    TLE, alguma forma de otimizar o algoritmo? Achei que estava sendo muito custoso o cálculo que gera os primos mas executei apenas ele e rodou em menos de 0.200s...

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

int main(){ 

    //Gerar primos pelo Crivo de Eratóstenes
    vector<bool> primos(1000001, true);
    primos[1] = false;
    int iterator = 2;

    while(true){
        if (iterator>1000) break;
        for(int i = 2*iterator; i<1000001; i+=iterator){
            primos[i] = false;
        }
        for(int i = iterator+1; i<1020; i++){
            if (primos[i]){
                iterator = i;
                break;
            } 
        }
    }

    int qtdConsultas, x, y, aux, contPrimos;
    bool lastVerified;

    cin >> qtdConsultas;

    for(int notUsedIndex = 0; notUsedIndex<qtdConsultas; notUsedIndex++){
        cin >> x >> y;
        contPrimos = 0;

        //Forçar x < y
        if(x>y){
            aux = x;
            x = y;
            y = aux;
        }

        //O 3 não pode ser tratado no método que usei
        if (x<=3) contPrimos++;

        //Colocar x na forma 6k-1
        double trying = ((double)x+1)/6;
        while(trying != floor(trying)){
            x++;
            trying = ((double)x+1)/6;
        }

        while(true){
            //Pare quando sair do intervalo
            if(x>y) break;

            //Possíveis primos gêmeos
            if(primos[x] && primos[x+2]) contPrimos++;

            //Trata os casos em que o segundo
            //primo gêmeo está fora do intervalo
            if((x+2)<=y) contPrimos++;

            x+=6;
        }

        cout << contPrimos << endl;
    }
    return 0;

}

  • eldsmonteiro respondido 8 years ago

    De boa. :)

    MOD

  • Joao40 respondido 8 years ago

    Tentei um monte de vezes esse exercício e só dava WA, valeu pela dica, passou agora.