Ekstremalnie długie liczby całkowite

pytanie zadane 27 lutego 2016 w C i C++ przez LordOfTheStrings Obywatel (1,610 p.)
edycja 27 lutego 2016 przez LordOfTheStrings

Witam wszystkich,

Zwracam się do was z bardzo elementarnym problemem. Chodzi o operowanie na 251 cyfrowej liczbie całkowitej. Rozwiązuje zadanie (https://zadania.oig.edu.pl/OIG/stored_files/pdfPreview/179596). Wydaje się ono proste, jednak mój program otrzymuje 50% punktów.

#include <iostream>

using namespace std;

unsigned long long int K;

int main()
{
    cin >> K;
    K = 3 * K + 8;
    cout << K;
    return 0;
}

Jestem pewien, że skrajne wartości po prostu nie mieszczą się w zmiennej. Czy ktoś mógłby pomóc mi rozwiązać mój problem?

5 odpowiedzi

odpowiedź 27 lutego 2016 przez Colossus Mądrala (6,410 p.)
wybrane 18 lutego 2017 przez LordOfTheStrings

Najlepsza

Myślę, że ten link powinien pomóc: http://main.edu.pl/pl/user.phtml?op=lesson&n=32

komentarz 27 lutego 2016 przez LordOfTheStrings Obywatel (1,610 p.)

Oczywiście, takie rozwiązanie jest jednym z pierwszych nasuwających się na myśl, jednak w warunkach konkursowych, gdzie liczy się każda minuta, implementacja go może być dość trudna. Istnieje szybszy sposób?

komentarz 27 lutego 2016 przez Colossus Mądrala (6,410 p.)

Akurat to zadanie jest dosyć łatwe, ponieważ mnożysz jakąś dużą liczbę przez liczbę jednocyfrową, czyli 3, a potem dodajesz 8. Gorzej by było gdyby trzeba było pomnożyć przez dwu lub trzy-cyfrową :)

komentarz 27 lutego 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Oczywiście, takie rozwiązanie jest jednym z pierwszych nasuwających się na myśl, jednak w warunkach konkursowych, gdzie liczy się każda minuta, implementacja go może być dość trudna. Istnieje szybszy sposób?

Wiesz jak działa OIG, ale nie wiesz, że w C++/C nie masz dostępu do bibliotek z big numami ?Przy okazji sumowanie bignumów to jakieś 50-60lini. Jak ktoś takie coś już naklepał z 2 razy to będzie dla niego już 5-10min roboty. Gdzie na konkursie masz 2h i z 15min to jest w miarę szybko

odpowiedź 27 lutego 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Wrzuć tego PDF na google drive lub coś bo OIG odmawia dostępu. Z tego co napisałeś, to zadanie nie jest proste bo musisz stworzyć swój typ danych operujący na wielkich liczbach.

komentarz 28 lutego 2016 przez LordOfTheStrings Obywatel (1,610 p.)

Proszę bardzo: https://www.dropbox.com/s/ibn7hnyt1zdzy12/kafelki.pdf?dl=0

odpowiedź 28 lutego 2016 przez criss Mędrzec (172,590 p.)

odpowiedź 28 lutego 2016 przez LordOfTheStrings Obywatel (1,610 p.)

Treść zadania wrzuciłem tutaj: https://www.dropbox.com/s/ibn7hnyt1zdzy12/kafelki.pdf?dl=0

Jak widać doprowadziłem to do postaci 3*k+8, z K+(√K-2)^2+(√K+2)^2. To pewnie było podstawą do rozwiązania tego zadania. W pierwotnej postaci implementacja była by bardzo trudna. Jednak drużynowe OIG rządzi się swoimi prawami. Jest do rozwiązania z 8 zadań, a niestety drużynę, którą udało mi się skrzyknąć stanowią, głównie uczestniczki w wieku do 14 lat, które dają nam 60% premii. Nie jestem też specjalistą od C++, skupiam się głównie na algorytmach. Piszę płynnie, jednak wyjadaczem bym siebie nie nazwał.

komentarz 28 lutego 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

Oj OIG jest praktycznie niczym do OI

komentarz 28 lutego 2016 przez LordOfTheStrings Obywatel (1,610 p.)

Poziom OI jest oczywiści nieporównywalnie wyższy. Zauważ też, że ty patrzysz na te zadania pewnie z perspektywy co najmniej szkoły średniej.

odpowiedź 28 lutego 2016 przez LordOfTheStrings Obywatel (1,610 p.)

Miałem chwilkę i napisałem to, tak jak radziliście. Poszło nawet szybciej niż myślałem i otrzymałem 100% punktów.

#include <iostream>
#include <string>

using namespace std;

string K, wynik;
short int reszta = 8, a, suma;
char cyfra, dopisanie;

int main()
{
    cin >> K;
    for(a = K.length()-1; a>=0; a--)
    {
        suma = static_cast<int>(K[a]-48) *3 + reszta;

        if(suma >0)
        {
            reszta = (suma - (suma % 10))/10;
            suma = suma - reszta*10;
        }
        else
        {
            reszta = 0;
        }

        dopisanie = static_cast<char>(suma%10+48);
        wynik = dopisanie + wynik;
    }

    if(reszta>0)
    {
        dopisanie = static_cast<char>(reszta%10+48);
        wynik = dopisanie + wynik;
    }

    cout << wynik;

    return 0;
}

Największym problemem była konwersja int'ów na char'y i vice versa. Jeżeli, ktoś zna prostszy sposób lub ma pomysł na ulepszenie mojego kodu, pozostaje otwarty na sugestie. Bardzo wszystkim dziękuję.