(UWAGA kod) PA05_POT - Czy umiesz potęgować, program zwraca poprawne dane - sędzia SPOJ'a zwraca "błędna odpowiedź"

pytanie zadane 20 września 2018 w C i C++ przez Milesq Nałogowiec (32,020 p.)
zamknięte 20 września 2018 przez Milesq

#include <iostream>

using namespace std;

int pow(int number, int toPower) {
    int ret = number;
    for (toPower;toPower>1;toPower--) // one not zero, because 2 ** 1 is equal 2 not 4!
    {
        ret *= number;
    }

    return ret;
}

//4 ** 93 it is to much, but (4 ** x) % 10 == (4 ** x%4). So I shouldn't calculate 4 ** 94
int main()
{
    short i;
    long long number, power;

    cin >> i;
    for(int j=i;j>0;--j)
    {
        cin >> number >> power;
        cout << pow(number % 10, power % 4) % 10 << endl;
    }
    return 0;
}

nigdzie nie przekraczam zakresu zmiennej ;) I tak, zapoznałem się z innymi pytaniami tego typu i nic nie pomogło.

komentarz zamknięcia: Padła już wystarczająca odpowiedź :)

4 odpowiedzi

odpowiedź 20 września 2018 przez monika90 Pasjonat (22,940 p.)
wybrane 20 września 2018 przez Milesq

Najlepsza

Twój program daje błędne wyniki. Np. ostatnia cyfra 7^4 to 1, a wg twojego programu to 7.

Ale wystarczy zamienić na:

pow(number % 10, (power - 1) % 4 + 1) % 10

i będzie dobrze.

Nie musisz też pisać własnej funkcji pow, ta z biblioteki standardowej jest wystarczająca.

PS. To twoje pow też jest błędne, bo źle oblicza potęgi o wykładniku zerowym.

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

1) wiem że jest pow() z cmath i na początku jej używałem ale pomyślałem że sędzia może sprawdzać czy używam tej funkcji i nie zaliczać takich zadań (chociaż wtedy byłby błąd wykonania)

2) wcześniej miałem osobny warunek dla wykładnika równego zero, ale spoj i tak daje liczby >=1

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

@monika90, dzięki działa, tylko niezbyt rozumiem dlaczego akurat tak zmodyfikowałaś tę linię?

1	komentarz 20 września 2018 przez monika90 Pasjonat (22,940 p.) Dzięki tej modyfikacji, gdy wykładnik jest podzielny przez 4, to będziemy podnosić od potęgi czwartej, bez modyfikacji byłoby podnoszenie do zerowej.

odpowiedź 20 września 2018 przez Piotr Batko Stary wyjadacz (13,190 p.)

Brak przejścia do nowej linii po wypisaniu wyniku? :)

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

Sprawdziłem już wcześniej i nadal nie działa :(

odpowiedź 20 września 2018 przez mokrowski Mędrzec (155,460 p.)

Nie rozwiążesz tego zadania próbując potęgować. Proponuję wypisać najpierw potęgi dla zakresu 1..30 i zobaczyć jak wyglądają zależności związane z ostatnią cyfrą. Z całą pewnością trafisz na rozwiązanie :)

komentarz 20 września 2018 przez niezalogowany

Jeżeli używa się modulo to zadanie można rozwiązać za pomocą potęgowania (Milesq jest na dobrej drodze). Mogę Ci wysłać rozwiązanie na PW ;)

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

@mokrowski, na wiki sources jest tablica potęg i korzystałem z niej, i na jej podstawie stwierdziłem że okres dla kolejnych wykładników to max. 4 i uwzględniłem to w programie

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

@hipcio No właśnie wydaje mi się że ten program jest dobry ponieważ nie znalazłem jeszcze danych wejściowych które dałyby błędny wynik...

komentarz 20 września 2018 przez niezalogowany

@Milesq myślę, że odpowiedź monika90 jest najlepsza. Ja podobnie rozwiązałem to zadanie (ale z użyciem std::pow);

komentarz 20 września 2018 przez mokrowski Mędrzec (155,460 p.)

@Hipcio, to zadanie jest tak proste że nie ma sensu silić się na jakąkolwiek arytmetykę. Gdyby problem był modulo około 16 i więcej, mogły by mieć sens jakieś obliczenia. Dla takiego małego problemu w mojej ocenie nie. Podałem najprostsze rozwiązanie z możliwych i to punktowane bardzo wysoko jeśli chodzi o czas i zajętość pamięci.

Oczywiście każdy ma prawo do własnych pomysłów :)

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

Tak jest proste bo w teori wystarczy zrobić

pow(number, power) % 10

ale chodzi o to żeby zrobić to inaczej

komentarz 20 września 2018 przez mokrowski Mędrzec (155,460 p.)

@Milesq, a bez pow(...) potrafisz? :) Spróbuj... :) Choćby dla samego siebie bo problem jest prosty i nawet nie trzeba szukać jakiegoś wyrafinowanego algorytmu w literaturze.

komentarz 20 września 2018 przez Milesq Nałogowiec (32,020 p.)

zrobiłem...

komentarz 20 września 2018 przez mokrowski Mędrzec (155,460 p.)

@Milesq, No to jeszcze "wyzwanie" bez % (modulo), bez jakiegokolwiek mnożenia. Jedynie dodawanie, odejmowanie i operacje bitowe.

Z każdego zadania da się wycisnąć więcej niż się wydaje. Oczywiście to już taki sport dla sportu.

1	komentarz 20 września 2018 przez niezalogowany Nie rozwiążesz tego zadania próbując potęgować. @mokrowski chodziło mi, że swoim sposobem też dojdzie do rozwiązania ;) Nie kwestionuję, że można lepiej.