AL_05_01 Czarodziejskie lusterko SPOJ

Question

Cześć wszystkim !

Bardzo proszę o pomoc, co może być nie tak w moim kodzie do zadania jak w temacie ? SPOJ cały czas bardzo długo go przetwarza, aż w końcu wywala że jest błędna odpowiedź. A tak naprawdę, sprawdzając kod na ideone dla danych wejściowych wszystko jest w najlepszym porządku. Dziękuję z góry za wszelkie podpowiedzi :)

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

using namespace std;

int czarodziejskieLusterko (long long int n)
{
    long long int bin[100000],odwrocona[100000];
    int i,j;
    for(i=0; n>0; i++)
    {
        bin[i]=n%2;
        n= n/2;
    }
    j=0;
    long long int liczbaDziesietna=0;
    for(i=i-1 ; i >= 0 ; i--)
    {
        liczbaDziesietna += bin[i]*(pow(2,j));
        j++;
    }
    return liczbaDziesietna;
}

int main()
{
    long long int liczba;
    while (cin >> liczba)
    {
        cout << czarodziejskieLusterko(liczba) << endl;
    }
    return 0;
}

oraz link na ideone : link

 

Answer 1

Myślę, że problem jest tutaj niedopasowany typ zmiennej - powinna być unsigned long long int aby zmieścić 2^64–1 wartości . Po co tworzysz tablice 100000 elementowe? Można prościej.

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

using namespace std;

constexpr auto digits = numeric_limits<unsigned long long int>::digits;

int czarodziejskieLusterko( unsigned long long int number )
{
    int step1 {0}, step2 {0};
    bool binary[digits] = {};
    unsigned long long result {0};

    while( step1<digits )
    {
        if( number>>step1 == 0 ) break;
        binary[step1] = ( number>>step1 ) & 0x1;
        ++step1;
    }

    while( step2<step1 )
    {
        result <<= 1;
        result += binary[step2];
        ++step2;
    }

    return result;
}

int main()
{
    cout << czarodziejskieLusterko(13) << endl;
    cout << czarodziejskieLusterko(47) << endl;
    cout << czarodziejskieLusterko(11) << endl;
    cout << czarodziejskieLusterko(61) << endl;
    return 0;
}

 

Comments

Typ zwracany przez funkcję czarodziejskieLusterko należy jeszcze zmienić na unsigned long long i SPOJ powinien zaakceptować

---

Zastosowałem tym razem nieco nny tok myślenia i odeszłem od deklarowania tablicy. Program oczywiście wykonuje to co powinno pojawić się na wyjściu, ale na SPOJ'u tym razem wyskakuje mi błąd SIGABRT. Już nieco czytałem że to może być związane z wyciekiem pamięci, albo że nie zwolniono pamięci. Tyle że tutaj raczej takiego problemu nie widzę. Proszę o pomoc.

#include <iostream>
#include <string.h>

using namespace std;

string odwrocLiczbeBinarna(string liczbaBinarna)
{
    int len = liczbaBinarna.length();
    int n = len-1;
    for(int i=0; i<(len/2); i++)
    {
        swap(liczbaBinarna[i],liczbaBinarna[n]);
        n = n-1;
    }
    return liczbaBinarna;
}

int czarodziejskieLusterko (unsigned long long int n)
{
    string r;
    while(n!=0)
    {
        r=(n%2==0 ?"0":"1")+r;
        n/=2;
    }
    r = odwrocLiczbeBinarna(r);
    unsigned long long int dec = stoi(r,nullptr,2);
    return dec;
}

int main()
{
    unsigned long long int liczba;
    while (cin >> liczba)
    {
        cout << czarodziejskieLusterko(liczba) << endl;
    }
    return 0;
}

 

---

Z tego co na szybko spojrzałem to w 18 linii powinien być unsigned long long, no i stoi zwóci Ci zwykłego inta. Zamiast niego spróbuj stoull(). Dodatkowo stringa możesz odwrócić za pomocą reverse(), tak będzie szybciej.

---

Ok teraz przynajmniej już ogarnąłem szybszą opcję na odwracanie stringa :) . Tylko, że po zastosowaniu tych zmian o których wspomniałeś to nadal jest ten sam błąd. Wszędzie praktycznie powinien być long long int i jest. Już powoli wymiękam ...

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

unsigned long long int czarodziejskieLusterko (unsigned long long int n)
{
    string r;
    while(n!=0)
    {
        r=(n%2==0 ?"0":"1")+r;
        n/=2;
    }
    reverse(r.begin(),r.end());
    unsigned long long int dec = stoull(r,nullptr,2);
    return dec;
}

int main()
{
    unsigned long long int liczba;
    while (cin >> liczba)
    {
        cout << czarodziejskieLusterko(liczba) << endl;
    }
    return 0;
}

 

---

Jak chcesz to mogę Ci dać poprawioną wersję Twojego pierwszego kodu.

 #include <iostream>
#include <math.h>
 
using namespace std;
 
unsigned long long czarodziejskieLusterko (unsigned long long int n)
{
    int bin[70];
    int i,j;
    
    for(i=0; n>0; i++)
    {
        bin[i]=n%2;
        n= n/2;
    }
    j=0;
    unsigned long long power_of_two = 1;
    unsigned long long int liczbaDziesietna=0;
    for(i=i-1 ; i >= 0 ; i--)
    {
        liczbaDziesietna += bin[i]*power_of_two;
        power_of_two *= 2;
        j++;
    }
    return liczbaDziesietna;
}
 
int main()
{
    unsigned long long int liczba;
    while (cin >> liczba)
    {
        cout << czarodziejskieLusterko(liczba) << endl;
    }
    return 0;
}

To powinno działać. Jutro mogę Ci jeszcze ewentualnie sprawdzić dlaczego ten ostatni kod nie wchodzi

---

Okej, bardzo Ci dziękuję za pomoc. Tylko prosiłbym Cię o wytłumaczenie paru kwestii, tak żebym mógł zrozumieć w czym tkwił błąd :)

Czy dobrze rozumiem że zastosowanie w pętli takiego zapisu

liczbaDziesietna += bin[i]*(pow(2,j)); zamiast bin[i]*power_of_two

mogło spowodować błąd SIGABRT, czy ogólnie błędną odpowiedź ?

A druga rzecz to raczej z czystej ciekawości : 

Czy unsigned long long int jest równoznaczne z unsigned long long ?

Apropo drugiego mojego kodu, z chęcią poczekam i dowiem się co tam jest nie tak :)
Wiem, żę może utrudniłem sobie robotę tworząc coś zupełnie innego zamiast wziąć twój kod na początku. Ale był on zbyt zaawansowany co do składni i nie umiałem go zrozumieć :/

 

---

Unsigned long long int to w zasadzie to samo co unsigned long long. Funkcji pow() lepiej w takich zadaniach nie używać, bo ona zwraca double, więc przy konwersji z double do unsigned long long może dojść do błędów w zaokrąglaniu. Jutro sprawdzę Ci w takim razie ten Twój kod. A i ten kod co jest na górze to nie jest mój :(

---

@Noseczek12, przynaję że nie wiem co jest nie tak z tym kodem. Przetestowałem go na wszystkie możliwe sposoby, ale nie mogę znaleźć błędu. SPOJ jest niestety nieprzyjazną platformą i nie pokazuje jakie błędy dokładnie zrobiliśmy, ani na jakich testach. Dlatego bardziej wolę Codeforces albo Szkopula