Apr 2017
9 / 9
Apr 2017
Apr 2017
narbej
Apr '17
1
  1. Naucz się korzystać z wyszukiwarki tu na forum
  2. Czytaj to co już napisano [milion razy?] na temat tego zadania!
  3. Jeżeli nie znajdziesz odpowiedzi i koniecznie chcesz zadać pytanie, to "doklejaj się" do istniejącego wątku, a nie zakładaj bez potrzeby ciągle nowych wątków gdy już taki istieją.
  4. Naucz się czytać treść zadania?
  5. Naucz się w końcu testować nie tylko na teście przykładowym z zadania

PS

A bo niby jaka? wg Ciebie to jest POPRAWNA!? -> https://ideone.com/9malKg35

Time limit exceeded: https://ideone.com/Dl0JPJ14 to właśnie przekroczenie limitu czasu.

jumper_5
Apr '17
1

No tematów jest sporo ale...
Większość implementacji jest w C++ czy językach podobnych, piszę w C#, fakt zasady działania są bardzo podobne ale jak w jednym wątku są 3 takie języki i trzeba tak "skakać" aby się dobrze wczytać "dlaczego?" dany kod komuś nie działa i wyciągnąć z tego jakieś wnioski jest to bardzo... męczące.
Czytam i zacząłem wgłębiać się w dany temat... żeby znaleźć prawidłowość...coś się powtarza i trzeba "zauważyć", "wypisać sobie potęgi"... potęgowanie modularne... próba z System.Numerics... To takie pytanie, czemu TO zadanie jest w kategorii "ŁATWE"?

Więc mówię sobie aaa, zostawię to zadanie na kiedy indziej bo mnie przekracza ale.. pierw spróbuję jakby to "pójść na łatwiznę". Jest temat o tym na wikipedii: https://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania34
Sprawdziłem co się stanie jak wyślę takie kody:
https://ideone.com/fjHabh13
https://ideone.com/HpLI6W11
No i oczywiście nie działa.
Ja TO zadanie dałbym conajmniej do kategorii "średnie"...

Co do podczepiania się pod inny wątek to dzięki za informację, faktycznie lepiej to wygląda jak wszystko jest w jednym miejscu :slight_smile:

PS: Ostatecznie zrobiłem ale... to zadanie to jakaś totalna porażka... nie ten poziom :confused:

szio
Apr '17

To wyobraź sobie jak bardzo męczące musi być czytanie co drugi dzień na forum postów podobnych do twojego. Alternatywą dla twoich "męczarni" wcześniej czy później będzie ignorowanie twoich zapytań, bo podejrzewam, że nawet @narbej może się zmęczyć odpowiadając Ci na posty tego typu.

mariusz193
Apr '17
jumper_5

niewątpliwie łatwiej narzekać, niż chwilę pomyśleć
zadanie jest w łatwych bo jest bardzo łatwe, i rozwiązanie jest krótkie, w C po usunięciu spacji i tabulatorów wystarczyło mi 160 znaków (a w skracaniu kodu jestem słaby)

loginus
Apr '17
jumper_5
  • Nauczyles się w szkole lub sam programowania.
  • Umiesz odpalić kompilator i zrobić program , może nawet obiektowy. Śmiało myślisz o sobie jako o programiscie . Może nawet myślisz aby zostać profesjonalnym liderem .
  • Usłyszałes szukając czegoś w necie o spoj.pl ( szukałeś bo metoda kopiuj i wklej to postawa twoich umietnosci kodowania )
  • Myślisz to coś dla mnie - w końcu już znam jeden język programowania - prawie jestem hakerem .
  • Wchodzisz na spoj - rejestracja - dział łatwe - czytasz zadanie "liczby pierwsze" i czujesz że to jest "To" . Nie musisz się wysilać a w głowie same układają się wiersze z kodem . To twój żywioł . Co prawda głupi sędzia się czepia składni ( kod piszesz w notatniku jak prawdziwy haker ) a potem jeszcze czepia się jedynki w testach ale udaje się zaliczyć zadanie za 10 podejściem .
  • Kolejne zadanie " 2 cyfry silni " - walka trwa 2 dni jednak sędzia ciągle odrzuca kod z powodu prrzekroczenia czasu . Poddajesz się i postanawiasz sprawdzić forum - jak zawsze zadanie jest na "topie" więc tym razem nie musiałeś zakładać nowego wątku - przez to też unikasz uwag od użytkowników uwag typu " było milion razy" , " nie umiesz kozystac z wyszukiwarki na forum " itd itp . Przebijasz się przez 2500 postów , odkrywasz nowe znaczenie słowa chaos . W 1976 poście jakiś użytkownik zamieścił prawie działający kod ( i nie usunął gdy już znalazł przyczynę błędu ) - czytasz go , analizujesz i doznajesz objawienia . Przez ostatnie 3 dni błądziłeś - niepotrzebnie napisałeś bibliotekę do obsługi bardzo dużych liczb , niepotrzebnie przeszukałeś Wikipedię w celu znalezienie szybszej metody mnożenia , niepotrzebnie implementowałeś fast i-o w celu poszukania sędziego - 30 kb kodu 5 tysiecy mini kodu i wszystko na nic . Zadanie można rozwiązać w 8 liniach .
  • Jest kac - głowa boli , psycha siada - a to wszystko bez udziału żadnych środków chemicznych . Trzeba odpocząć od kodowania .
  • Kolejny wieczór i czas na kolejne zadanie - "Czy umiesz postępować" - prrrrrrr - każdy umie potegowac znaczy się mnożyć . Jedna pętla i już .Może nawet wiesz o funkcjach matematycznych jakie ma twój język i je wykorzystasz wtedy nawet tej jednej pętli nie trzeba będzie pisać . Wysyłasz zadanko i zonk - sędzia znowu zgłasza błąd przekroczenia czasu . Nie pomaga użycie liczb flota , mie pomaga mnożenie liczb w twojej biblitece do obslugi dużych liczb . Tak zaczyna się depresja kodera . Ostatnia szansa to forum . Wycieńczony zakładasz nowy temat gdzie kulturalnie przedstawiasz problem - niestety zmęczenie daje się we znaki , masz zawezone pole widzenia i nie zauważasz że 5 postów poniżej już jest temat do tego zadania . Liczysz na szybką pomoc , że ktoś poda tobie pomocna dłoń , wskaże linię i numer znaku który trzeba poprawidz aby doszlifowac kod . Na szczęście odpowiedź pojawia się szybko - dostajesz maila z powiadomieniem . 33 minuty od napisania postu masz już 2 odpowiedzi - zaczynasz czytać i szok - szok i niedowierzaniem . Pierwsze co czytaszto "było milion razy " , drugie " naucz się korzystać z wyszukiwarki" , itp itd ... Czujesz jak by ktoś dał ci w twarz . Miała być pomocna dłoń a czujesz że toniesz .

Problem jest taki : aby rozwiązać to zadanie w zadanym czasie trzeba je przeanalizować i uświadomić sobie jak będzie się zachowywał program dla małych testów jak i maksymalnych . Jeżeli już sobie uswiadomisz że nie da się wykonać podnoszenia miliarda do potęgi miliard trzeba znaleść inny sposób niż hamskie liczenie . Do tej pory wszystkiego ciebie uczyli inni - teraz sam musisz odkrywać problemy i je rozwiązywać . Pierwsze odkrycie istnieje wiedzą o której nie wiesz . Jak dłużej posiedzisz nad problemem to Wikipedia powie tobie że istnieje coś takiego jak szybkie potegowanie , że jest coś takiego jak arytmetyka modularna i że w systemach modulo występują cyklicznie powtarzające pierścienie . Tego nie uczą w szkole podstawowej .

  • Każde kolejne zadanie to kolejny strzał w pysk . Sprowadza ciebie na ziemię . Analizujesz problem , szukasz rozwiązania , piszesz kod , zloscisz się na sędziego - podejrzewasz błędne testy , błąd autora zadania - na końcu odkrywasz że kod źle robi jakaś operację .
jumper_5
Apr '17

Macie racje, bardzo dziękuję za tak wylewne odpowiedzi! Będę o tym pamiętał na przyszłość!
Trochę mi się głupio zrobiło... czy można ten temat usunąć ew. scalić z tym większym?

tjm
Apr '17

To zadanie z pewnością nie jest trywialne w tym sensie że wystarczy bezpośrednio przenieść treść zadania na kod. Chociażby ze względu na fakt że rezultat potęgowania nie będzie reprezentowalny w żadnym standardowym typie liczbowym.

Konieczna zatem jest pewna praca koncepcyjna. Minimalnie należy zaobserwować że podstawę potęgi można zredukować mod 10, co dość łatwo uzasadnić (nawet bez większego doświadczenia z operacjami modulo) poprzez przedstawienie podstawy jako pewnej wielokrotności 10 i reszty, i zaobserwowanie że tylko jeden czynnik we wzorze dwumianowym Newtona będzie potencjalnie niepodzielny przez 10. Taka redukcja powinna być wystarczająca do rozwiązania zadania za pomocą algorytmu szybkiego potęgowania modularnego, przy czym należy pamiętać że redukcje modulo należy stosować konsekwentnie podczas obliczeń (czego zabrakło w rozwiązaniach z tego tematu).

Można iść nawet krok dalej i zredukować także wykładnik, stosują chociażby relację a^n ≡ a^(n-φ(n)) mod n, chociaż to już będzie trudniejsze do uzasadnienia. Otrzymujemy wtedy małą podstawę i wykładnik, a zadanie można skutecznie rozwiązać używając potęgowania poprzez mnożenie w pętli, tak jak robi to jeden z pierwszych rozwiązań w tym temacie.

Kwestia czy to zadanie powinno się znaleźć w łatwych czy nie to kwestia bardzo subiektywna. Przykładowo, ostatnio w zadaniach trudnych pojawił się problem z AlgoLigi, który praktycznie nie wymaga żadnej pracy koncepcyjnej i sprowadza się do bezpośredniej implementacji treści zdania.

sig
Apr '17

To zadanie jest łatwe, ale dopiero kiedy zauważy się pewne prawidłowości. Wtedy nie trzeba nawet potęgować w samym zadaniu. Jest tu też zresztą więcej zadań bardziej na spostrzegawczość niż algorytmy, np 2 cyfry silni.