Problema "altavelocita"

Salve a tutti, ho tentato di risolvere il problema altavelocita ma non ottengo più di 65 punti (Execution timed out) e non riesco a trovare un altro metodo risolutivo per far diminuire il tempo di esecuzione

Il mio codice:

#include <iostream>
#include <stdio.h>
#include <vector>

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    unsigned N;
    unsigned c=0; //conta i chilometri
    unsigned p=0; //progressiva chilometrica
    unsigned long long K;

    std::cin >> N >> K;
    unsigned inizio[N], fine[N];

    for(unsigned i=0; i<N; i++){
        std::cin >> inizio[i] >> fine[i];
    }

    while(c < K){
        for(unsigned i=0; i<N; i++){
            if(p >= inizio[i] && p <= fine[i]) c++;
        }
        p++;
    }

    std::cout << p-1 << std::endl;

    return 0;
}

( http://pastebin.com/9FDVcmsF )

Grazie in anticipo per l’aiuto.

Al posto di contare i chilometri uno per uno ( c++ ), non c’è un modo per “saltare” e contare i chilometri a blocchi più grandi? :slight_smile:

1 Mi Piace

Potresti darmi qualche altro suggerimento?

Se te sai che dal chilometro X al chilometro Y ci sono esattamente B file di binari, allora i binari totali in quell’intervallo saranno (Y-X)*B.

Se poi conosci anche quanti binari in tutto ci sono prima di X allora sai anche se il K-esimo binario si trova in [X, Y], prima oppure dopo!

A questo punto devi trovare un modo furbo e veloce per calcolarti queste informazioni e (soprattutto) scegliere con cura i vari intervalli.

Grazie, finalmente sono riuscito a risolverlo. :grinning:

1 Mi Piace