Na czym polega problem z zadaniem SPOJ Liczby wyważone?

Question

Mam problem z zadankiem - wziąłem się za Liczby wyważone http://pl.spoj.com/problems/LICZBYW/ i napisałem program który w skrócie polega na tym że wpisuje się liczbę jako string, wycina się 2 ostatnie cyfry i sprawdza się je. Warunek w zadaniu będzie spełniony jeśli liczba będzie podzielna przez 2 i nie będzie podzielna przez 4 (przynajmniej taki jest mój wniosek). Niestety na stronie SPOJ'a przy 3 teście dostaje rezultat "błędna odpowiedź" i mam problem ze znalezieniem problemu :) gdyż liczby  są wczytywane jako string, więc nie a problemy z długością (w zadaniu jest max 200 znaków, program działa przy większej ich ilości), co do poprawności wyników napisałem program sprawdzający liczbę parzystych i nieparzystych dzielników i sprawdzałem wyniki ręcznie - wszystko się zgadza i tak się zastanawiam co jest nie tak? Tutaj link do kodu: https://gist.github.com/anonymous/4ff850122ebaff0d1cbdcdb48bfdce37

Answer 1

Warunek w zadaniu będzie spełniony jeśli liczba będzie podzielna przez 2 i nie będzie podzielna przez 4 (przynajmniej taki jest mój wniosek)

Mylisz się. Warunek będzie spełniony jeśli będzie tyle samo dzielników parzystych co nieparzystych.

napisałem program który w skrócie polega na tym że wpisuje się liczbę jako string, wycina się 2 ostatnie cyfry i sprawdza się je.

Dlaczego 2 ostatnie cyfry? Jeśli masz jakąkolwiek liczbę większą od 99, to te dwie cyfry ci nie wystarczą. Musisz przekonwertować jakoś tą liczbę na jakiś duży typ danych i sprawdza dzielniki. Po kolei. Zlicza się parzyste i nieparzyste, a na koniec porównuje ich ilość. Jeśli ilość liczb parzystych i nieparzystych jest inna, to bierzemy liczbę większą o 1 od tej wprowadzonej cinem i powtarzamy, do skutku!

Comments

To, że liczba spełnia warunek zadania gdy jest podzielna przez 2 i nie jest podzielna przez 4 to prawda i można to łatwo matematycznie udowodnić (tutaj nie będę opisywał, jak ktoś będzie robił to zadanko niech sam pomyśli dlaczego), a z tego warunku wynika druga część, gdyż liczba jest podzielna przez 2 gdy jej ostatnia cyfra jest podzielna przez 2 i jest podzielna przez 4 jeśli dwie ostatnie cyfry tworzą liczbę podzielną przez 4. Twój sposób ze sprawdzaniem nie jest zbyt dobry bo te liczby z zadania mogą mieć do 200 cyfr więc nie ma szans żeby się zmieścić w czasie (nie mówiąc już o tym, że z tego co wiem nie ma aż tak dużych typów danych dla liczb i trzeba by było się bawić w dzielenie tej liczby na mniejsze). Jednak dzięki za odpowiedź bo znalazłem błąd związany w wypisywaniem dużych liczb np. jak się podawało 199 program wypisywał 1102 zamiast 202, jednak SPOJ dalej nie akceptuje rozwiązania .

---

A działa poprawnie dla 999? :)

---

Dzięki - to pewnie to, tzn. że dla 999 nie działa to zauważyłem czytając poprzedni komentarz - jakoś tak wpadło i zmieniłem ale trochę na szybko i znowu nie działa dla 9999 i teraz muszę tylko tak to pozmieniać żeby działało dla samych 9 (podejrzewam że jeden z testów wygląda tak: 9999...999) - dzięki 

Answer 2

To jest problem bardziej matematyczny. Dam Ci radę:

1. Wypisz ten ciąg 
2. Znajdź prawidłowość
3. Napisz kod(kilkanaście linijek)