520. Dyzio

[anim_90]

Wybaczcie, że ostatnio Was torpeduję pytaniami, ale jestem w ciągu jak narkoman ^^ Robię Dyzia. I wyskakuje mi błąd "Przekroczono limit czasu". Ok, to jestem w stanie zrozumieć, ale dlaczego zajmowana pamięć poniższego kodu wynosi 132M ? Skoro na ideonie wynosi ledwo 3.4 ? A swoją drogą może jeszcze jakiś pomysł dotyczący tego, dlaczego mam błąd? Tz. jak usprawnić to zadanie - rozwiązując spoja już wiem z czym mam największy problem. Optymalizacja to nie jest mój sprzymierzeniec ^^ To jak, pomożecie? ^^

Ps: Już wiem dlaczego miałem 132 M, teraz pozostał problem z limitem

AC :)

[narbej]

Faktycznie, daje się zauważyć
Czytałeś mój dopisek do twojego wątku: Cwany Lutek? Jeżeli nie to polecam
To zadanie też może być takim przykładem, że przyśpieszeniem wczytywania nic nie wskórasz.
Nawiasem mówiąc instrukcja:

ios_base::sync_with_stdio(0);

nic nie ma wspólnego ze scanf/printf, więc lepiej jej nie stosować. Dotyczy ona tylko cin/cout/cerr, pod warunkiem, że jednoczenie nie korzystasz z printf i scanf.
Twoje sito ma mały błąd, liczba 1 jest liczbą pierwszą? Ale to oczywiście nie powód TLE.
Tle powoduje wielokrotne "przebieganie" tablicy i zliczanie liczb pierwszych. Czy można inaczej?
Zobacz, twoja tablica bool wygląda jakoś tak - piszę z pamięci, więc mogłem się pomylić:
000010101110101110101110

a gdyby od razu policzyć i zapisać ilość zer, liczb pierwszych [po poprawieniu twojego sita]:
001223344445566667788889 itd
012345678901234567890123 <-- to są indeksy do tablicy int
Gdy masz taką tablicę od razu możesz odpowiedzieć, w zakresie od zera do np 23 jest 9 liczb pierwszych.
A w zakresie 6 23 zapytasz? Tyle samo co wyżej - 9 ale trzeba odjąć dolny zakres - 1, czyli 9 - 3

PS
Twój program dla zakresu 0 23 wypisuje więcej - wlicza 0 i 1 jako liczby pierwsze.

PS 2
Możesz tak zmodyfikować swoje sito, rezygnując z tablicy bool na rzecz int, aby od razu zapisywać ilość liczb pierwszych, ale wtedy dodatkowo trzeba policzyć powyżej magicznej granicy i*i, ale na początek lepiej zrób to "tradycyjnie".

[anim_90]

Dziekuję przemyślę to z rana i zabiorę się do pracy

Ps1: ios::base pozostał z "wczesnej" fazy kodu ^^ Zaraz wyrzucę

[travisp1]

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

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/ymGCIY

[mariusz193]

po pierwsze program źle liczy -> twój kod + moje dana = błędne wyniki

po drugie, źle zrozumiałeś poradę narbeja, przeczytaj jeszcze raz uważnie i zastanów się nad kolejnością działań w twoim programie - czy o to chodziło w poradzie ?

[matiutd888]

Witam wszystkich 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;

}`

[rafal06]

Zadeklaruj tablicę jako globalne, tzn. poza main.

[matiutd888]

Dziękuję! Zaakceptowane : Tylko czemu to rozwiązało problem?

[konrad87]

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]

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

[m00_sq]

Wywala mi błąd TLE. Czy ktoś może mi powiedzieć dlaczego?

https://ideone.com/wgl252

Jakieś usprawnienia co do programu?

[narbej]

Wywala mi błąd TLE. Czy ktoś może mi powiedzieć dlaczego?

Twój program za długo liczy.

Jakieś usprawnienia co do programu?

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.

[cyberstormppc]

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

Ideone.com

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]

Czy ktoś ma pomysł o co chodzi sędziemu?

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

[cyberstormppc]

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/d1IzdX 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/ 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]

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]

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.

[alfonsue]

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

[narbej]

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]

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.