Feb 2016
9 / 24
Nov 2017
Apr 2023
travisp1
Oct '16
1

Witam,
znajdzie się jakaś dobra dusza, która podpowie mi jak zoptymalizować powyższy kod tak, żeby SPOJ nie wyrzucał "Przekroczono limit czasu"? Po przerobieniu wielu kombinacji rozwiązania problemu doszedłem do tego momentu i już bardziej czasu wykonania skrócić nie potrafię. Z góry dzięki za pomoc :wink:

PS. Próbowałem zgodnie ze znalezionymi na forum wskazówkami, tworzyć tablicę int'ów zawierającą ilości liczb pierwszych, czyli {0,0,1,2,2,3,3,4...}, ale w tym wariancie program się wysypuje dla testu 2 1000000.

https://ideone.com/ymGCIY38

1 month later
matiutd888
Nov '16

Witam wszystkich :slight_smile: Mam problem: otóż gdy robiłem sitem eratostenesa i potem deletowałem tablicę wyskakiwał mi błąd przekroczenia limitu czasu. Natomiast gdy pomyślałem by wykorzystać poradę narbeja coś chyba szwankuje z pamięcią, bo program się zamyka od razu po włączeniu, gdy miejsc w tablicy dam 1 000 000, natomiast gdy miejsc w tablicy będzie 100 000 wszystko działa jak należy. Czy ktoś poratuje mnie i powie jak rozwiązać ten problem?

include

include

void sito(bool *tab, int n)
{
tab[1]=1;
tab[0]=1;

for ( int i=2; i*i<=n; i++)
{
    if(!tab[i])
    {
        for ( int j = i*i ; j<=n; j+=i)
            tab[j] = 1;
    }
}

}
void zamiana(bool*tab, int *tablica, int n)
{
for(int i=2; i<=n; i++)
{
if(!tab[i])
{
tablica[i]=tablica[i-1]+1;
}
else
{
tablica[i]=tablica[i-1];
}
}
}
int main()
{

bool tablica[1000001]= {};
int tablica2[1000001]= {};
sito(tablica,1000000);
zamiana(tablica, tablica2,1000000);
int test;
scanf("%d",&test);
for( int t=0; t<test; t++)
{
    int suma, dolny, gorny;

    scanf("%d%d",&dolny,&gorny);
    suma=tablica2[gorny]-tablica2[dolny-1];
    printf("%d ",suma);
}
return 0;

}`

11 months later
konrad87
Nov '17
1

Witam,
Na wstępie, jest to mój pierwszy post i przepraszam za ewentualne uchybienia. Dlaczego wywala mi przekroczenie czasu? C++ 4.3.2

#include <iostream>

using namespace std;
int ile, wynik;

bool czy_pierwsza(int n)
{
  if(n<2)
    return false;

  for(int i=2;i*i<=n;i++)
    if(n%i==0)
      return false;
  return true;
}

int main()
{
    cin >> ile;
    int * tab = new int[ile*2];

    for(int i=0; i<ile*2; i++)
    {
        cin >> tab[i];
    }


    for(int i=0; i<ile; i++)
    {
        for(int j=tab[i*2]; j<=(tab[(i*2)+1]); j++)
        {
            if(czy_pierwsza(j))
            {
                cout << "Liczba pierwsza: " << j << endl;
                wynik++;
            }
        }
        cout << wynik << endl;
        wynik = 0;
    }
    return 0;
}
mariusz193
Nov '17

skoro umiesz pisać, to może i umiesz czytać - więc przeczytaj ten wątek, jest tam odpowiedź dlaczego masz TLE

20 days later
narbej
Dec '17

Twój program za długo liczy.

Czasami łatwiej budować zupełnie od nowa, niż poprawiać czy usprawniać. I tak jest w twoim wypadku. Poszukaj i “postudiuj” tematykę liczb pierwszych. Potem wróć do zadania Liczby pierwsze [pierwsze zadanie łatwe] i popraw swój wynik [najlepsi mają tam 0,00] Gdy to zrobisz, dopiero wróć do Dyzia.

1 year later
cyberstormppc
Dec '18

Podłączam się pod temat.
Napisałem Dyzia z użyciem tablicy wzorcowej do liczb pierwszych poniżej 1000 i przy użyciu LIST:


Program pokazuje wszystkie dobre wyniki chyba i wykonuje się na ideone w 0.14 sek a sędzia i tak twierdzi że za wolny. W programie są liczniki czasu, wrzucałem do sędziego oczywiście bez nich.
Czy ktoś ma pomysł o co chodzi sędziemu?

mariusz193
Dec '18

skoro dla 3 zakresów (bo przecież 2 z 5 są oczywiste) czas wynosi 0,15 sekundy do dla maksymalnego testu (20000 zakresów) będzie to około 1000 sekund - to chyba tłumaczy, dlaczego sędzia jest niezadowolony :slight_smile:

cyberstormppc
Dec '18

Słuszna uwaga z tymi 20 ty.s zapytań zapomniałem o tym.
Jednak chyba niezbyt dokładnie przeanalizowałeś mój kod, albo ja zagmatwałem te opisy pomiaru czasu.
Wstawiam drugi raz https://ideone.com/d1IzdX8 kod, tym razem dodaję 20 ty.s testów od 1 do 1 MLN i poprawiłem opisy pomiaru czasu co jest kiedy.
Program wykonał się jak widać w 2.25529 sek, gdyż samo utworzenie bazy liczb pierwszych zajmuje 0.147636 s, pozostałe ponad 2 sek to właśnie sprawdzenie 20tys razy listy 78498 liczb pierwszych.
Czyli wadą programu jest wolne przeszukiwanie bazy szybko utworzonych listy liczb pierwszych.
Problem chyba leży w tym że nie wiem jak wykonać wyświetlenie tylko części LISTY z jakiegoś konkretnego zakresu, a być może się nawet nie dać.
Zajrzałem tu : http://www.cplusplus.com/reference/list/list/1 i widzę że jest więcej iteratorów niż begin i end, ale nadal nie mówi mi to czy da się i jak wyświetlić zawartość listy np. mniejszą / większą niż X czy Y.
Czy może lepszym rozwiązaniem byłoby tu przeniesienie tego np do tablicy o 78498 elementach?

mariusz193
Dec '18

w tym wątku opisano poprawny sposób rozwiązania tego zadania, można też rozwiązać to inaczej, też mieszcząc się w czasie
możesz więc jeszcze trochę pomyśleć, może sam wymyślisz jeden z tych sposobów (a może jest więcej niż dwa sposoby) lub przeczytać ten wątek

cyberstormppc
Jan '19

Rzeczywiście nie doczytałem zbyt dokładnie tego wątku wcześniej, a teraz przysiadłem na nowo po chwili przerwy i mam już AC.
Potwierdzam że porada Narbeja w tym wątku jest jednym z poprawnych rozwiązań tego zadania.
Dziękuję za pomoc.

11 months later
alfonsue
Dec '19
1

Wywala mi błędną odpowiedź
<tu był kod>
wie ktoś może o co chodzi

narbej
Dec '19

Na spoju jest kilka kompilatorów c++, a wybrałeś najstarszy. W takim razie dlaczego na jednym “idzie” a na innym nie?

Nie mam pojęcia, ale może dlatego, że najnowszy kompilator potrafi “rozprawić” się z różnymi błędami i niedociągnięciami widocznymi gołym okiem w twoim kodzie, a starszy nie potrafi?

pawoj20
Dec '19
alfonsue

Program powoduje naruszenie ochrony pamięci:
Na początku zadeklarowana tablica jako:
bool tablica[1000001] = {0};
później wywołana jest funkcja:
sito_erastotenesa(tablica, 1000001);
W funkcji liczba 1000001 staje się zmienną n.
Dodatkowo 1000001 ma dzielniki 101, 9901, wiec we fragmencie:
for (int j = 2*i ; j <= n; j += i)
numbersTable[j] = true;
trafi poza tablicę.
Dla kompilatora C++ 4.3.2 na SPOJ spotkałem się z sytuacją gdzie w rezultacie była błędna odpowiedź, a tak naprawdę następowało naruszenie ochrony pamięci.

1 month later
korkirw
Feb '20
vanillabear

1
53 97
Wiem, jestem trochę złośliwy, bo mogłem dać łatwiejszy przypadek, ale mogłem dać też trudniejszy… :slight_smile:

3 years later
marcel6600oo
Apr '23

Podłączam sie do tematu, kod mój działa idealnie, ale brakuje mu prędkości
#include

using namespace std;

int main()
{
ios_base::sync_with_stdio(0);
long long a;
cin>>a;
for(long long i=0;i<a;i++){

long long n=0,m=0,wart=0;
cin>>m;
cin>>n;
long long *tab;
tab = new long long [n+1]{0};
tab[0]=1;
tab[1]=1;
for(long long i=2;i<n;i++){
if(tab[i]==0){

for(long long j=i*i;j<=n;j=j+i){
  tab[j]=1;



}
    }

}
for(long long i=m;i<=n;i++){
if(tab[i]==0){
// cout<<i<<" ";
wart++;
}
}
cout<<wart<<endl;
delete [] tab;
}
}