499. Czy umiesz potęgować - SPOJ przekroczono limit czasu

Question

Próbuję rozwiązać http://pl.spoj.com/problems/PA05_POT/. Niestety sędzia "twierdzi", że został przekroczony limit czasu. Mój kod polega na liczeniu potęgi, a później z tego wyniku wypisuje tylko cyfrę jedności. Testowe wyniki działają. Nie wiem co można zrobić tutaj szybciej.

Answer 1

W tym zadaniu chodzi o to, żeby zauważyć jak zmienia się ostatnia cyfra, czy powtarza się cyklicznie?

2^1 = 2

2^2 =4

2^3 =8

2^4 =16

2^5=32

2^6=64

itd...

 

Comments

Tak, tylko dla pewnych przypadków możesz wyjść poza zakres unsigned int

---

Pisałem już : "Dla b!=0 które jest podzielne przez 4 wyjdzie, że to a^0, czyli 1, a to nie prawda, więc po modulo 4, trzeba dodać 4"

---

Dla a=10^9 i b=3, trzeba będzie obliczyć 10^9*(3+4), czyli 10^63, a tego żadna zmienna nie zmieści, trzeba tutaj wykorzystać pewien trik

---

czemu tylko przy a=10^9 i b=3 ? jak byloby a=10^9 i b=4 to przecież tym bardziej się nie zmieści. Albo nawet gdyby a = 999999999 (czyli o 1 mniej) to przecież też się nie zmieści.

---

Witam, zrobiłem to zadanie innym sposobem mianowicie zauważyłem, że niezależnie jak wielką liczbę potęgujemy i tak dla ostatniego znaku liczą się ostatnie znaki tych "dużych" liczb np. 1234^1234 ostatni znak będzie taki sam jak 4^4 albo 134^62 jest jak 4^2. Zrobiłem program, który liczy to w ten sposób, jednak sędzia cały czas odrzuca jako zły wynik. Zrobiłem do tego kolejny program, który porównuje wyniki tej mojej wersji z tym waszym wzorem wyżej i dla pierwszych 999999 a i 999999 b (tyle policzyłem) wyniki są identyczne, więc nie wiem czy to ja coś źle robię czy sędzia jest zepsuty. Program z tym waszym wzorem sędzia akceptuje

Answer 2

Dlaczego wypisujecie tutaj klucze na rozwiązanie tego zadania 0_0

Przecież osoba pisząca kod, powinna sama na to wpaść... Podaliście teraz wszystkim to na tacy.

Sens tego zadania polegał na tym, aby doszukać się zależności powstawania ostatniej cyfry... I tę zależność wy tutaj rozpisaliście, rozwalając tym samym sedno problemu i całe zadanie... GRATULUJĘ.

Sam autor ma prawo poprosić o wskazówki oraz nie wysłał działającego kodu, więc to mieści się w granicach regulaminu forum.

Ale wskazówka to nie jest podanie klucza na rozwiązanie zadania !

Comments

Myślę, że jeżeli ktoś szuka rozwiązania to wie co robi. Tzn jest świadomy, że patrząc na rozwiązania nie wymyśli ich sam. Czasem jednak lepiej zobaczyć jak zadanie jest rozwiązane i się czegoś nauczyć niż zrezygnować i nic się nie nauczyć.

---

Jeśli patrząc na rozwiązania wiesz, że nie wymyśliłbyś ich sam, to znaczy, że nie jesteś gotowy na to zadanie i jeśli wyślesz na SPOJ poprawną odpowiedź, to będzie to nie fair w stosunku do innych użytkowników.

Porażki uczą czasami więcej niż się Tobie wydaje. A jeśli ten post pozostanie na tym forum, to wygooglowanie treści Twojego pytania: "499. Czy umiesz potęgować - SPOJ przekroczono limit czasu" sprawi, że każda osoba, która tu trafi, dostanie rozwiązanie na tacy.

Przeczytaj ten post:
https://forum.pasja-informatyki.pl/90416/spoj-zasady-umieszczania-postow
to może zrozumiesz dlaczego nie należy umieszczać rozwiązania zadań SPOJ'a na żadnym forum. Jestem prawie pewny, że ten wątek zniknie stąd również.

---

Ok, jestem zmuszony przyznać Ci rację. Myślałem, że chodzi CI o to, że ktoś przez to się nie nauczy. Mówisz, że jak się wrzuci taki kod do sędziego to to nie fair w stosunku do innych użytkowników spoja i to jest fakt. Oczywiście mi nie zależy w tym momencie na rywalizacji z kimś, ale wrzucając zadania psuje reputację spoja. Tzn kogoś dobry wynik przestaje coś znaczyć.

---

Dokładnie o to mi chodziło. Sam bym lepiej tego nie napisał jak Ty teraz :-)

Masz moje uznanie i dam Ci łapkę dla postu za to ;-)

---

Usunąłem lub zmieniłem moje wpisy, w których był kod.

---

Cieszę się, że kolejny użytkownik tego forum zaczyna się uczyć porządnie i nie ułatwia tej nauki innym użytkownikom.

---

Tak bym tego nie ujął :P W forum chodzi o to, żeby tą naukę ułatwiać. Jednak w sposób przemyślany.

Ta sytuacja kojarzy mi się z certyfikatem ECDL. Niby europejski certyfikat, który potwierdza wiedzę w dziedzinie informatyki, a tak naprawdę, żaden pracodawca na to nie patrzy. I nie mówię teraz o programiście szukającym pracy, bo to akurat nie dziwne, że w jego przypadku taki certyfikat nie ma większego znaczenia. Ale ktoś kto aspiruje na stanowisko, na którym wymagane są tylko podstawy komputera też niestety nie za bardzo może się szczycić certyfikatem ECDL jeżeli go ma, a to dlatego, że ten certyfikat jest za łatwo dostać. U mnie w szkole jak był to można było nie przyjść na żadne zajęcia i podejść tylko do egzaminu, który był po pierwsze za prosty, a po drugie można było na nim ściągać. To samo z tytułem technika. Kwalifikacje zawodowe niczego nie potwierdzają bo są za łatwe, za mało praktyczne (przecież pisząc strony internetowe można korzystać z internetu i każdy webmaster to robi, a na takim egzaminie nie, dodatkowo kto w przyszłości będzie potrzebował, aż tyle teorii, która nie ma praktycznego zastosowania?). Tydzień przed tym jak pisałem kwalifikacje E.13 zadania były już na youtube wraz z dokładną instrukcją ich rozwiązania.

---

a tak naprawdę, żaden pracodawca na to nie patrzy

oraz

To samo z tytułem technika

Nie rozumiesz podstawowych rzeczy. ECDL jest certyfikatem respektowanym za granicą - musisz mieć dodatkowo język opanowany. W Polsce ludzie nie wiedzą czym jest, ale faktem jest, że ceny egzaminów są niższe niż gdzie indziej. W Polsce dużo łatwiej i szybciej oraz z mniejszym kosztem zdobędziesz ten certyfikat. Jednak jeśli szukasz pracy z nim, to w Polsce do niczego Ci się nie przyda. Chociaż są wyjątki.

Jeżeli chodzi o egzamin na technika to w ogóle się minąłeś. Dam Ci przykład. Poszedłem u mnie w mieście do firmy Sii, międzynarodówka - korporacja. Chciałem pójść na programistę (javy, c++, c# - cokolwiek). Nie miałem żadnego doświadczenia z programowaniem (zawodowo). Ale wystarczył miesiąc praktyk zawodowych jako technik informatyk i papier potwierdzający te umiejętności - z miejsca dostałem propozycję zostania wdrożeniowcem i technikiem.

Prawda jest taka, że bez tego papieru nie chcieliby rozmawiać. Nawet gdybym miał doświadczenie. Oczywiście odmówiłem, w końcu poszedłem tam na rozmowę o pracę jako programista.

Racją jest, że doświadczenie > papiery. Jednak bez papieru dużo nie osiągniesz, na pewno nie w tym kraju.

---

Tak papier jest waży, ale właśnie zbyt łatwe testy, które może zdać każdy zmniejszają wagę takiego papieru. Studia jest zdać ciężko, dlatego liczą się najbardziej. W Japonii z kolei tytuł technika jest zdobyć bardzo ciężko, ale dzięki temu jest on właściwie gwarantem znalezienia pracy.

Oczywiście nie chodzi mi teraz jak bardzo liczy się tytuł technika czy tam ECDL (moim zdaniem mało), chodzi mi o to, że ułatwiając zdobycie dyplomów obniża się ich znaczenie.

Wracając do spoja. Gdyby wszystkie zadania były rozwiązane w internecie, ktoś kto miałby na nim bardzo dużo punktów nie mógłby się tym chwalić no bo i czym tu się chwalić, umiejętnością kopiowania ? A jeżeli nie ma zadań w internecie i ktoś zrobi ich chociaż 10 to już dobrze o nim świadczy.

---

Mysle to samo

Answer 3

HINT1. Działania modulo są bardzo wolne, podobnie pętle.

HINT2. Zobacz jaki jest limit pamięci.

Comments

1. Nie widzę opcji obliczenia potęgi bez pętli. Podobnie nie mam pomysłu jak wyciągnąć jedności bez modulo (używam go raz do każdorazowego obliczenia wyniku, to chyba, aż tak nie spowalnia ?)

2. Nie wyskakuje mi błąd wykonania programu tylko limit czasowy.

---

1. Da się zmniejszyć ilość iteracji pętli (zmieni się także ilość operacji, a także same operacje co może poprawić szybkość): a) możesz zejść na bity, b) możesz użyć rekursji (ma to swoje wady)
2. Wiem, to była wskazówka mówiąca: "możesz użyć rekurencji, albo innych sposobów, które zużywają więcej pamięci, ale są szybsze"