Suma prefiksowa

Question

Witam.

Rozwiązuje zadanie o treści

Zrobiłem to na sumie prefiksowej, ponieważ tak było w podpowiedzi (gdy robiłem normalnie, wyskakiwało przekroczony limit pamięci).

Moje rozwiązanie:

#include <iostream>

using namespace std;

int main()
{
   long  ile,liczba;
   cin >> ile;
   long *tab=new long [ile];
   long *sumy_prefiksowe=new long [ile+1];
   sumy_prefiksowe[0]=0;
   for(int i=0;i<ile;i++)
   {
       cin >> liczba;
       tab[i]=liczba;
       sumy_prefiksowe[i+1]=sumy_prefiksowe[i]+tab[i];
   }
   cout << sumy_prefiksowe[ile];
   delete [] tab;
   delete [] sumy_prefiksowe;
    return 0;
}

Proszę o wskazówki, rady :) 

Być może to nawet nie jest poprawna implementacja sum prefiksowych...

Answer 1

Metodą sumy prefiksowej tego zadania nie rozwiążesz. Zaimplementuj dodawanie liczb o nieznanej długości. Nawet naiwne przetworzenie na string i sumowanie liczb w reprezentacji string,  pozwoli rozwiązać to zadanie. Tablica zbieranych liczb (prefix'owa bądź inna), także nie jest potrzebna.

Comments

Dziękuję za odpowiedź :)

W takim razie, szkoda, że wskazówki jest nieprzydatna.