Faktoryzacja [FACTORIZ]

bo masz błędny (trochę, ale sędzia jest dokładny) algorytm - widać to na zamieszczonym przez ciebie na ideone przykładzie

Tak szczerze siedzę nad tym już trzydziestą którąś godzinę i nadal nie mogę znaleźć tego błędu, ale wydaje mi się, że tablica bool już mniejsza być nie może, próbowałem też zmienić tą listę na tablicę, ale nadal wyskakiwał mi limit czasu.

Ja u siebie poprawiłem linijkę 63 z continue na break ale dalej mam limit czasu.

za mało poprawiłeś - po drobnych poprawkach zadanie zostało zaliczone

użycie tablicy zamiast listy jeszcze nieco by przyspieszyło - czyli taka metoda jest wystarczająca do rozwiązania zadania

sprawdziłem swoje stare rozwiązanie - z kłopotami, gdyż dawało SIGSEGV, po sprawdzeniu wyszło, że brakowało inicjacji 2 zmiennych, i teraz nie wiem, czy wtedy zaliczyło bo był inny kompilator, czy też te kilka znaków znikło w czasie przeprowadzek (obie hipotezy są tak samo mało prawdopodobne)

w każdym razie czas jest nieznacznie lepszy 3,36/4,66 - ale w tym zadaniu głównym kosztem są operacje wejścia/wyjścia - musiałbym użyć fast i/o aby mieć bardziej wiarygodne dane, na ile moja metoda jest szybsza

Zamieniłem liste na tablice i funkcje na te fast io, dalej limit czasu

to jeszcze trochę pomyśl - bo naprawdę tylko kilka linijek zmieniłem w twoim programie aby zaliczyło

w szczególności pomyśl nad kolejnością wykonywanych działań

Trochę nad tym popracowałem i jest AC przy nawet nie najgorszym czasie 1.56s ;D Dzięki wszystkim za pomoc, a kodd usuwam.

Cześć, zrobiłem już kilka wersji rozwiązania i ciągle dostaję TLE. W trakcie testów widzę, że pojawia się liczba 7 - czyli jest blisko. Ale już brak mi pomysłów jak to przyspieszyć.
Ktoś coś podpowie?
Mój kod:

Zrób jeszcze co najmniej dwie wersje:

1. wersja:

main () {
}

A potem drugą:
2. wersja:

main () {
   int a_kuku;
   while (std::cin  >> a_kuku) ; /// nic nie rob
   /// wczytaj jeszcze kilka razy nic
   std::cin  >> a_kuku;
   std::cin  >> a_kuku;
}

Możliwe, że w pierwszej wersji nie zobaczysz 7, ale gdy wyślesz drugą, napewno pojawi się 7, czyli jest blisko.

Moim zdaniem, dwie tablice to stanowczo za dużo, dzisiaj zrobiłem dla testu, wersję zupełnie bez tablic i bez sita. Czas nie jest powalający, ponad 5 sek, ale z tablicowaniem mam o wiele lepszy więc czemu Ty masz problemy?

Pomyś o tym i przeanalizuj jak bardzo nieefektywnie twój program sprawdza np liczbę 2833.
Przy okazji większych liczb, twój program jest błędny, więc testuj naprawdę swój kod albo u siebie albo na ideone dla większego spektrum liczb a nie tylko dla przykładu z zadania, a nie wysyłaj do sprawdzenia na spoja i nie nazywaj tego [sprawdzania] testowaniem, bo to nie jest testowanie. Zrób też test wydajnościowy, a dopiero potem, gdy uzyskasz AC zacznij myśleć jak przyśpieszyć swój kod.

To jest zadanie z kategorii trudnych, więc może powinieneś zacząć od perfekcyjnego rozwiązania łatwiejszych?

Gdy zadanie PRIME_T rozwiążesz w czasie 0.00, to z tym też będzie Ci łatwiej.

Prezent na dzień dziecka, nie tylko dla dzieci

Jeżeli masz kłopot, z wypisaniem gwiazdek w odpowiedniej ilości i w odpowiednich miejscach to jest prezent dla Ciebie:

factor (liczba) {     
   dzielnik = 2;
   dopóki  dzielnik * dzielnik jest mniejszy lub równy liczba 
             jezeli liczba dzieli sie bez reszty przez dzielnik : 
                         wypisz dzielnik  oraz gwiazdkę
                         liczba = liczba podzielona przez dzielnik
             w przeciwnym wypadku powieksz dzielnik 
   /// liczba - po ewentualnym wczesniejszym podzieleniu przez  dzielniki jest liczba pierwsza - i wypisujemy ja bez gwiazdek:
   wypisz liczba
koniec

Powyższy algorytm, można zapisać w dowolnym języku, ale nie gwarantuje on automatycznie AC, np jeżeli będziemy powiększać dzielnik tylko o 1, będzie za wolny. Gwarantuje za to poprawny format wypisywanych danych.

PS
Powyższy prosty algorytm działa także dla liczby jeden, mimo, że jedynka nie jest liczbą pierwszą.

Cześć,
jako że dostaję bez przerwy TLE, podepnę się pod post. Jakieś sugestie, co mogę robić nie tak?
Jeszcze jedno - jak spradzacie szybkość swoich programów?

Można nawet użyć do tego ideone - do sprawdzania szybkości działania, ale napewno wklejając tam “odrobinę” większe testy niż takie jakie tam wkleiłeś. Możliwe, że testujesz u siebie dokładniej, ale jak chcesz pomocy, to postaraj się lepiej, przecież to nawet nie są tak małe testy jak z zadania, to żart a nie test.

Nie wystarczy się podpiąć, należy przeczytać [przestudiować] dokładnie wątek i skorzystać z rad. Na przykład PRIME_T == 0.0 jest wielce pomocne, ale nie wystarczające. Po co robisz sito jak i tak z niego potem nie korzystasz? Nie jestem pewny i nie chcę tego wiedzieć, czy robisz je w ogóle poprawnie.

Ale do sprawdzenia jak wolne jest moje rozwiązanie nie trzeba wklejać aż tyle, przecież chodzi tylko o porównywanie kolejnych poprawek mojego kodu czy są lepsze czy nie, więc jeżeli dla jakiegoś możliwie dużego testu, na ideone dostaję np 0.05 sek, to muszę tak poprawiać program aby uzyskać krótszy czas dla tego samego testu.

“Surowe” wykorzystanie mojej propozycji gwarantuje TLE, ale zadanie jest trudne. To tylko drobna podpowiedź, jak do zadania można podejść. Można rozwiązać je nawet w BASHU, ale będzie to oczywiście raczej trudne albo może nawet bardzo trudne;-) : https://pl.spoj.com/ranks/FACTORIZ/lang=bash7 i oczywiście nie w taki, powyżej opisany sposób.

Tak na wyjściu limit danych jest 64kB.
Żeby zobaczyć sukces to w tym przypadku trzeba zamienić w pierwszej linii 9788 na 8754.
(dla liczby większej niż 8754 -> błąd wykonania)

Wszystko jasne, dzięki!