среда, 24 сентября 2008 г.

Project Euler 201 - не выходит

Почему вообще заинтересовала эта проблема? Во первый мне показалось что итеративный подход намного красивее и понятнее функционального.
А во вторых...написав в принципе правильный алгоритм я получил неправильный результат. И довольно долго не мог понять в чем собственно дело.
Задача:
Пусть у нас есть массив S={1*1,2*2,...100*100}
Найти сумму чисел которые являются уникальной ссуммой 50-элементного подмассыва S.
Более подробно на сайте...

Код (неправильный)

    char* total = new char[300000*50];

    memset(total,0,300000*50);

 

    for(int i=1;i<=100;++i){

        for(int j=299999;j>0;--j)

            for(int p=0;p<49;++p)

                if(total[j*50+p])

                    if(total[j*50+p])

                        total[(j+i*i)*50 + p + 1] += total[j*50+p];

        total[i*i*50]=1;

    }

 

    LONGLONG res = 0;

    for(int j=49;j<300000*50;j+=50)

        if(total[j]==1)

            res+=(j-49)/50;

    delete total;

    return res;

Комментариев нет: