Modulo 10 - SPOJ: Błędna Odpowiedź

pytanie zadane 19 września 2017 w SPOJ przez Kamil Paradowski Użytkownik (620 p.)
zmienione kategorie 20 września 2017 przez Patrycjerz

Witam! Czy ktoś z Was mógłby spojrzeć świeżym okiem i dać mi wskazówkę dlaczego mój kod wywala błędną odpowiedź przy zgłaszaniu?

#include <iostream>
#include <math.h>

int main()
{
    short n;
    std::cin>>n;
    std::string binary;
    double decimal=0;
    for (int i=0;i<n;i++)
    {
        std::cin>>binary;
        for (int j=binary.length()-1,k=0;j>=0;j--,k++)
        {
            if (binary[j]=='1')
                decimal+=pow(2,k);
        }
        if (fmod(decimal,10)==0)
            std::cout<<"Tak\n";
        else
            std::cout<<"Nie\n";
        decimal=0;
    }
    return 0;
}

Treść zadania: http://pl.spoj.com/problems/FR_03_11/

Z góry dziękuje za zainteresowanie i pomoc!

komentarz 19 września 2017 przez Kuba321 Użytkownik (730 p.)

Jak dla mnie w pewnym momencie następuje przekroczenie zakresu... np. dla takiego 1000 bitów

komentarz 19 września 2017 przez Kamil Paradowski Użytkownik (620 p.)

W sumie masz rację, sam teraz to zauważyłem. Źle coś policzyłem i stwierdziłem, że maksymalna wartość binarna może wynosić 5.357543e+300, ale to jest wartość dla samego 2^999...

No cóż, muszę wykombinować inny sposób, dzięki!

komentarz 20 września 2017 przez niezalogowany

Zła kategoria, poprawna to spoj

1 odpowiedź

odpowiedź 20 września 2017 przez criss Mędrzec (172,590 p.)
edycja 20 września 2017 przez criss

Spróbuj to zrobić bez konwersji na system decymalny. Na pewno możesz odrzucić wszystkie liczby nieparzyste - tzn. takie których najmłodszy bit jest 1.
Dalej: liczba jest podzielna przez dziesięć jeśli jest wielokrotnością 10. Pojedyncza potęga dwójki nigdy nie będzie wielokrotnością dziesiątki. Dlatego kolejne potęgi muszą się nawzajem "uzupełniać" tworząc wielokrotności 10. Patrz tylko na cyfre jedności kolejnych potęg. Rozpisz sobie kilka pierwszych zaczynając od 1:

1	2	3	4	5	6	7	8	9	10	11	12
2	4	8	16	32	64	128	256	512	1024	2048	4096

Zauważasz pewną prawidłowość? Cyfry jedności 2, 4, 8, 6 powtarzają się co 4 pozycje. Np. jeśli ustawiony jest trzeci bit (2^3 = 8), to musi być też ustawiony 5. (= 3+2) lub 9. (= 5 + 1*4) lub 13. (= 5 + 2*4) bit itd... Musisz znajdować takie pary bitów, które sobie odpowiadają tworząc wielokrotność dziesiątki.

Nigdy nie robiłem tego zadania i nie wiem czy to jest najprostszy sposób, ale ja tak to widzę i myślę, że w tę stronę należy iść.

komentarz 9 września 2018 przez manjaro Nałogowiec (37,390 p.)

Na necie jest trochę inny sposób a mianowicie ostatni bit musi być ustawiony na 0 (podzielność przez 2) i szukamy wtedy liczb podzielnych przez 5. Dodawanie i odejmowanie na przemian bitów.

Ale Twój sposób jest ciekawy, a co ważne sam na to wpadłeś. Z tym że trzeba sumować te cyfry (2 4 8 6) wszystkich bitów ustawionych na 1 i na końcu sprawdzić podzielność przez 10.