499. Czy umiesz potęgować [PA05_POT]

[mariusz193]

a skąd mam wiedzieć czy usuwasz, czy nie ?

ja w każdym razie po usunięciu tych linii dostałem AC

fragment poniżej znalazł się tu na skutek pomyłki (dotyczy innego zadania)

-choć ze skandalicznym czasem (bo algorytm nie ten właściwy, a przechodzi tylko dlatego, że aktualna maszyna testująca jest około 100 razy szybsza niż w momencie publikacji zadania)

[narbej]

Zobacz: http://discuss.spoj.com/t/nie-wesoly-komentarz-o-komentarzach/22775

[tarpauwatratar]

(...) algorytm nie ten właściwy, a przechodzi tylko dlatego, że aktualna maszyna testująca jest około 100 razy szybsza niż w momencie publikacji zadania

Jakaś szansa na około stokrotne zaostrzenie limitu czasu?

[mariusz193]

nie wiem, pewnie tylko autor zadania może to zmienić, szkoda bo obecnie dla starszych zadań często przechodzą rozwiązania, które miały być (i kiedyś były) niezaliczone

zmniejszenie czasu miałoby także skutki uboczne - dla wielu zadań (głównie z dużymi danymi wejściowymi/wyjściowymi) wyeliminowało by rozwiązania w C#, JAVA, Python, a to obecnie spory procent rozwiązań (a nie egzotyka, jak kiedyś)

[baton351]

Faktycznie teraz działa. Zwraca mi czas 0.0 s.
Tobie pokazuje inny czas?

[mariusz193]

też pokazuje 0.0 - informacja z czasie była błędna, miała dotyczyć innego wątku

[narbej]

Jakaś szansa na około stokrotne zaostrzenie limitu czasu?

Raczej nie, Bo:

1. Limit już jest zmieniony.
2. 100 to jest tylko bardzo grube przybliżenie i uproszczenie.
3. Złe algorytmy nie przechodzą - wystarczy popatrzeć na statystykę i najlepsze wyniki http://pl.spoj.com/ranks/PA05_POT/ :
   Rozwiązało osób Zgłoszeń zaakceptowano Błędna odpowiedź Błąd kompilacji Błąd wykonania Przekroczono limit czasu
   7426 65494 8771 29328 7598 2999 16746
4. Mmoim zdaniem na SPOJ'u, nie ma specjalnego znaczenia, podkręcanie limitów i zwiększanie testów, w przeciwieństwie do konkursów typu algoliga, czy fraktal - ale tam jest to na "bieżąco" robione.
5. Nie jestem zwolennikiem zbytniego podkręcania limitów, bo potem są problemy z zaliczeniem zadań w wolniejszych językach.
6. Rozwiązywacz powinien samodzielnie i krytycznie podejść do swojego rozwiązania i uzyskanego swojego czasu w porównaniu do najlepszego..

PS
AD 3
Oczywiście 16746 zgłoszeń kodów, które były za wolne [TLE] to wynik od początku istnienia zadania. Wystarczy sprawdzić teraz i zobaczyć czy ta liczba się nadal powiększa? I faktycznie tak jest, są nowe takie zgłaszenia.

[tadex0]

Witam, pomoże ktoś rozkminić błąd?
http://ideone.com/SNplXp

Potęgi liczone na ifach (4 potęgi) sprawdzanie czy podstawa nie jest 0 chociaż osobiści wydaje mi się to zbędne bo dane wejściowe 1+..
Ogólnie utknąłem w tym miejscu. Wyniki chyba są ok. Zaczynałem od if w==5 cout 5... i zostały grupy gdzie od wykładnika odejmujemy 2 dla 9 i 4 lub 4 dla 2 3 7 8. Finalnie wszystko sprowadza się do 4 potęg chociaż dla szybkości chyba 1 opcja lepsza.

[mariusz193]

Wyniki chyba są ok.

chyba nie

sprawdź wynik dla danych:

10
999999990 4
999999991 4
999999992 4
999999993 4
999999994 4
999999995 4
999999996 4
999999997 4
999999998 4
999999999 4

[tadex0]

Dziękuję za pomoc ale łatwiej by było podać liczby pokroju sprawdź:
90 4
0 4
91 4
1 4
92 4
2 4
93 4
3 4
po pierwsze nie trzeba ogarniać liczby e i po drugie od razu widać zależność. Mimo wszystko dziękuję i pozdrawiam.
Time 0.0 to poprawny algorytm?

[laurence_par]

Troche juz nad tym zadaniem przesiedzialem i kazdy test ktory przeprowadzam na moim kodzie daje wynik prawidlowy. Problem w tym ze sedzia wyrzuca mi blad. Czy moglby ktos zerknac na moj kod?
http://ideone.com/3vcg3o

[mariusz193]

Troche juz nad tym zadaniem przesiedzialem i kazdy test ktory przeprowadzam na moim kodzie daje wynik prawidlowy

z tego wniosek, że przeprowadziłeś za mało testów - wg. twojego algorytmu masz do przeprowadzania 40 testów - więc się nie leń i je zrób

przekazany kod nie kompiluje się - trochę to nieładnie wobec osób, które mają sprawdzić twój kod

metoda kopiuj/wklej jest świetna- w generowaniu trudnych do zauważenia błędów

a generalnie nawet gdy będziesz miał poprawne wyniki, to sędzia nie powinien ci zaliczyć tego zadania ze względu na wyjątkową brzydotę kodu

[mariusz193]

przeczytałeś ten wątek?
raczej nie - bo niewłaściwy sposób przekazania kodu
również nie zastosowałeś się do rady aby te 40 przypadków sprawdzić - więc zrób to teraz

[jumper_555]

już znalazłem błąd i sorki za zły post

[ccoder]

Witam , czy nakieruje mnie ktoś jak usprawnić poniższy kod , by nie wyrzucało mi przekroczenia czasu ?

#include <iostream>

using namespace std;
int how_many=0;
int principle=0;
int index=0;

long int potega(int podstawa, int wykladnik)
{
    if (wykladnik==0)
    {
        return 1;
    }
    else
    {
        return podstawa*potega(podstawa,wykladnik-1);
    }

}
int main()
{
    cin>>how_many;
    for(int i=0;i<how_many;i++)
    {
        cin>>principle>>index;
        cout<<potega(principle,index)%10<<endl;
    }
    return 0;
}

[narbej]

Tego kodu w kontekście tego zadania nie da się usprawnić. Masz tu nie tylko przekroczenie limitu czasu ale masz też, dla niektórych testów, przekroczenie zakresu typu long long, a tym bardziej long int.

PS
Tyle o tym już tu napisano w tym i innych wątkach poświęconych temu zadaniu, że aż dziwne, że nie doczytałeś.

[ccoder]

Dzięki , trochę szkoda. Miałem poczytać jak to rozwiązać, ale przyszedł mi jeszcze jeden pomysł użycia funkcji potęgowania z biblioteki cmath . Sknociłem poniższy kod i wyrzuca mi tym razem błędną odpowiedź , więc chyba jest ruch w interesie ma ktoś pomysł co jest powodem błędu?

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long long int how_m=0,bufor=0,index=0,principle=0;

    cin>>how_m;
    for(int i=0;i<how_m;i++)
    {
        cin>>principle>>index;
        bufor=(pow(principle,index));
        cout<<bufor%10<<endl;

    }
    return 0;
}

[mariusz193]

w tym wątku wyjaśniano to wiele razy (a są też inne wątki poświęcone temu zadaniu)
więc przeczytaj wątek i będziesz wiedział

[pw1983]

Zrobiłem sporo testów z tego wątku oraz swoich i niby jest ok. Bardziej ciekawi mnie czy ktoś może wskazać błąd w tym programie (od spoja dostaje błędną odp): https://ideone.com/1Gfl5Z#stdin

Ogólnie to pisałem algorytm na podstawie: https://www.matematyka.pl/44958.htm

• najpierw sprawdzamy przypadki brzegowe dla wykładnika = 0 i 1 oraz podstawy = 0
• później liczymy podstawę do 4 potęgi z tego wyciągamy ostatnią cyfrę: liczby[k] = fmod(pow(p, i), 10); Dla przykładu ktoś podał np.16455 44556 to liczę: 16455^1, 16455^2, 16455^3, 16455^4 no i z tych wyników ostatnia cyfra
• sprawdzam ile różnych cyfr jest w 4 elementowej tablicy i ustawiam na tą wartość zmienną licznik
• wyliczam ostatnią liczbę jako liczby[indx]
• kiedy liczby w tablicy się powtarzały zwracam po prostu pierwszą.

OK już mam ten błąd: zamiast liczby[k] = fmod(pow(p, i), 10); powinno być liczby[k] = fmod(pow(p%10, i), 10);

[narbej]

powinno być liczby[k] = fmod(pow(p%10, i), 10);

Masz AAC, więc tak, ale i tak to jest armata na wróble. Przecież wystarczy:
a = p % 10, a potem:
liczby[0] = 1
liczby[1] = liczby[0] * a % 10 // % 10 tu nadmiarowo
liczby[2] = liczby[1] * a % 10
liczby[3] = liczby[2] * a % 10
liczby[4] = liczby[3] * a % 10
ale najlepiej oczywiście w pętli:
liczby[k] = liczby[k-1] * a % 10
no i pomijając fakt, że da się to zrobić dużzo prościej, i na wiele sposobów, niż to robisz i opisujesz. Wystarczy uważnie poczytać ten i inne wątki poświęcone temu zadaniu.