• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

SPOJ Liczby znaczące - Przekroczono limit czasu

VPS Starter Arubacloud
0 głosów
702 wizyt
pytanie zadane 27 września 2020 w C i C++ przez Baster123 Nowicjusz (220 p.)

Witam! Cały dzień męczę się z zadaniem ze spoja - https://pl.spoj.com/problems/PZPI3/ . Pomimo tego, że kod działa dobrze serwis cały czas wyrzuca "Przekroczono limit czasu". Czy ma ktoś jakiś pomysł na przyspieszenie algorytmu? Z góry dziękuję! 

int significant_numbers(int b, int e)
{
    int number = 6;
    int ans = 0;
    int buf = number * number;
    
    if (e >= 4 && 4 >= b)
    {
        ans++;
    }

    if (e >= 9 && 9 >= b)
    {
        ans++;
    }

    while (buf <= e && buf <= 1000000000)
    {
        int buffor = sqrt(number);
        buf = number * number;

        if (buf >= b)
        {
            for (int i = 3; i <= buffor + 1; i=i+2)
            {
                if ((number - 1) % i == 0)
                {
                    break;
                }

                if (i >= buffor)
                {
                    ans++;
                    break;
                }
            }


            for (int i = 3; i <= buffor+1; i=i+2)
            {
                if ((number + 1) % i == 0)
                {
                    break;
                }

                if (i >= buffor)
                {
                    ans++;
                    break;
                }
            }

            number += 6;
        }
        else
        {
            number += 6;
        }
    }

    return ans;
}

 

1
komentarz 27 września 2020 przez Whistleroosh Maniak (56,980 p.)
Mógłbyś wyjaśnić swój pomysł na rozwiązanie? Bo nie bardzo rozumiem co się dzieje w tym kodzie.
komentarz 27 września 2020 przez Baster123 Nowicjusz (220 p.)
Jasne. Funkcja dostaje dwie zmienne. Początek i koniec przedziału. Funkcja ma za zadanie sprawdzić jakie liczby pierwsze podniesione do kwadratu należą do tego przedziału (tylko kwadraty liczb pierwszych spełniają wymagania z zadania). Pętla while sprawdza podzielność liczb szukanych specjalnym dla liczb pierwszych algorytmem (6*x+-1). Dzielniki są sprawdzane do momentu, w którym nie przekroczą pierwiastka z danej liczby.

1 odpowiedź

+1 głos
odpowiedź 27 września 2020 przez Whistleroosh Maniak (56,980 p.)
wybrane 27 września 2020 przez Baster123
 
Najlepsza
Problem jest taki, że dla każdego testu od początku szukasz liczb pierwszych na danym przedziale. Dla danych a = 1, b = 1e9, Twój program sprawdziłby wszystkie liczby postaci 6n+-1 w przedziale [1, sqrt(1e9)]. Tych liczb może być jakoś sqrt(1e9)/6, a dodatkowo musisz sprawdzić w O(sqrt(x)) czy każda z tych liczb jest pierwsza. Złożoność jest wtedy równa jakoś O(sqrt(b)^2*t), gdzie t to ilość testów, a to jest zdecydowanie za wolne.

Lepiej by było gdybyś sitem znalazł wszystkie liczby pierwsze nie większe niż sqrt(1e9), następnie dla każdego testu, musisz tylko przejść po tych wszystkich liczbach pierwszych  i znaleźć te których kwadraty mieszą się w przedziale [a, b]. Liczb pierwszych mniejszych od sqrt(1e9) nie będzie wiecej niż 10^4, więc to powinno zmieścić się w limitach czasowych
komentarz 27 września 2020 przez Baster123 Nowicjusz (220 p.)

Teraz wygląda to w następujący sposób. Niestety SPOJ nadal wywala "Przekroczono limit czasu". Nie wiem co jeszcze mógłbym poprawić. Oczywiście wszystkie wyniki są poprawne.


int bufor = 31623;

void prime_numbers(bool* chk)
{
    int ans = 0;

    for (int i = 0; i < bufor + 1; i++)
    {
        chk[i] = 0;
    }
    
    for (int i = 2; i * i < bufor; i++)
    {
        for(int j = i * i; j <= bufor; j+=i)
            chk[j] = 1;
    }
}

void significant_numbers(int b, int e, bool* chk)
{
    int ans = 0;
    
    for (int i = 2; i < bufor; i++)
    {
        if (i * i > e)
        {
            break;
        }
        
        if (!chk[i])
        {
            if (i * i >= b)
                ans++;
        }

    }

    cout << ans << endl;
}

 

komentarz 27 września 2020 przez Whistleroosh Maniak (56,980 p.)
Jest za wolno bo za każdym razem przeglądasz całą tablicę chk[]. Zauważ, że większość elementów w tej tablicy ma wartość 1, a nas obchodzą tylko te, które mają wartość 0. Możemy więc bezpośrednio trzymać na wektorze takie i, że chk[i] jest równe 0.
komentarz 27 września 2020 przez Baster123 Nowicjusz (220 p.)
Wszystko działa. Dziękuje za pomoc i pozdrawiam.

Podobne pytania

0 głosów
1 odpowiedź 463 wizyt
pytanie zadane 12 stycznia 2019 w SPOJ przez WireNess Stary wyjadacz (11,240 p.)
0 głosów
1 odpowiedź 277 wizyt
pytanie zadane 12 marca 2023 w C i C++ przez alfutek Początkujący (360 p.)
+1 głos
1 odpowiedź 199 wizyt
pytanie zadane 10 marca 2016 w C i C++ przez CzikaCarry Szeryf (75,340 p.)

92,786 zapytań

141,719 odpowiedzi

320,650 komentarzy

62,115 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...