Dyzio

[maciej_2ti]

Witam, dopiero zacząłem robić zadanie na spoju, jednak w ostatnim czasie zrobiłem sporo zadań, i przy kilku poległem. Lecz jedno z nich nie daje mi spokoju, mianowicie https://pl.spoj.com/problems/DYZIO2/. Kiedy na ideone wprowadzam wejście i wyjście, program działa poprawnie i kompiluje się błyskawicznie. Ale ciągle mi wyskakuje błąd przekroczono limit czasu, spojrzy ktoś z większą wiedzą na mój kod? https://ideone.com/VGlaRY

[narbej]

Działa poprawnie i kompiluje się błyskawicznie, ale …
Na ideone wprowadzasz [tylko wejście] ale dużo za małe
Potestuj np dla:
10
2 1000000
…
2 1000000
, a potem takie same dane ale 20:
20
2 1000000
…
2 1000000
W zadaniu wystąpi nawet 20000 takich lub podobnych danych i pomyśl - potestuj jak wtedy zachowa się twój program - też błyskawicznie?

To zadanie jest chyba w kategorii średnich, a jeżeli zaczynasz, to raczej powinieneś skupić się na łatwych, np Liczby pierwsze PRIME_T.
Moim zdaniem, jeżeli w w/w uzyskasz czas poniżej 0.1, bardzo ułatwi Ci to “rozprawienie się” z innymi zadaniami dotryczącymi liczb pierwszych.

A propo, czy czytałeś: Jeśli zaczynasz, przeczytaj koniecznie! <--kliknij w to proszę!

[maciej_2ti]

Z zadaniem PRIME_T już sobie poradziłem dlatego chciałem spróbować czegoś trudniejszego związanego z liczbami pierwszymi, ale narzazie poległem,kiedyś się pewnie uda. A propo podesłanego przez ciebie linku, rozumiem co masz na myśli. Następnym razem postaram się staranniej dobierać pytania.

[narbej]

Niezupełnie.
CHodziło mi konkretnie o: http://discuss.spoj.com/search?q=dyzio. Możliwe, że jest lepiej przeglądać kilka[naście] krótkich wątków niż jeden długi, ale może jednak nie? A właśnie powstał kolejny właśnie ten.

Natomiast w prime_t masz czas dużo powyżej 0.1, a dokładniej: 1.68–> https://pl.spoj.com/status/PRIME_T,maciej_2ti/, a najlepsze czasy to 0.00.

Chodzi o to, że uzyskanie AC nie zawsze a nawet najczęściej to jeszcze nie “to” o co chodzi tygryskom, a tygryskom powinno przecież chodzić o naukę pisania dobrych i optymalnych programów, a nie o uzyskiwanie AC, nieprawdaż? Chyba, że tu też jestem w błędzie ;-(
Ale oczywiście [naj]ważniejsze jest robienie i posuwanie się do przodu, czego Ci i sobie szczerze życzę!

[pawoj20]

Tablice dynamiczna deklaruje sie inaczej.
Oczywiscie tablica o stalej wielkosci jest szybsza.
(i to jest podpowiedź).
Po wcieciach wnioskuje ze liczba przypadkow mogla zostac dopisana na samym koncu gdy algorytm obliczajacy pojedynczy przypadek zadzialal (i to tez jest podpowiedź).

[maciej_2ti]

Mam jeszcze jedno pytanie, wprowadziłem do mojego programu większe dane jak radziłeś i nadal kompiluje się on szybko https://ideone.com/q7LMbo. Co jeszcze może być źle, co powinienem poprawić w kodzie? Dużo pytam bo widzę że mam do czynienia z kimś doświadczonym .

[narbej]

Spójrz na linijkę z twoim kodem na ideone:
Sukces #stdin #stdout 0.11s 7348KB

0.11 sek, jest jednak już nie takie błyskawiczne, a to dopiero tylko 20 zestawów. Testuj dalej, powiększając ilość zestawów, lub uwierz, że szybko [powiększając wielkość-ilość zestawów] będzie za wolno.
I nie chodzi tu o czas kompilacji, ale czas wykonannia kodu dla jakiegoś zestawu danych - czym większy tym wolniej. A co powinieneś zrobić - powalczyć “z” PRIME_T