Задачка по теории алгоритмов.

Балансировка камней.

Вам даны рычажные весы. На левой чаше весов лежит один камень с весом W<2N. У вас есть

свое множество камней: 1, 2, 4, … , 2N-1.

Определите сколькими способами можно расположить некоторые из этих камней на чашах весов

так, чтобы уравновесить их. Выведите это значение по модулю D.

Входные данные (input.txt):

В первой строке записаны три числа: N, L, D. (1<=L<=N<=1000000, 1<=D<=100).

Далее во второй строке ровно L символов – двоичная запись числа W.

Выходные данные (output.txt):

Единственное число – количество способов, взятое по модулю D.

Input.txt
6 4 6
1000

Output.txt
3

Input.txt
6 6 100
100110

Output.txt
5

Вот мой код:
#include <windows.h>
#include <fstream>
#include <string>

using namespace std;

//variables
int N;
int L;
int D;
string s;

//arrays
byte* host; //weight of the stone lying on the side
byte* weight; //sum weight of all stones placed on one side
byte* incl; //if the stones included on either side
int all;

//procedures
int add(byte x);
int sub(byte x);
int check();
int process();

int add(byte x)
{
boolean carry = false;
if (weight[N - x] == 0)
weight[N - x] = 1;
else {
weight[N - x] = 0;
carry = true;
int q = 1;
while (carry)
if (weight[N - x - q] == 0) {
weight[N - x - q] = 1;
carry = false;
}
else {
weight[N - x - q] = 0;
q++;
}
}
return 0;
}

int sub(byte x)
{
boolean carry = false;
if (weight[N - x] == 1)
weight[N - x] = 0;
else {
weight[N - x] = 1;
carry = true;
int q = 1;
while (carry)
if (weight[N - x - q] == 1) {
weight[N - x - q] = 0;
carry = false;
}
else {
weight[N - x - q] = 1;
q++;
}
}
return 0;
}

int check()
{
boolean yes = true;
for (int i = 0; i < N + 1; i++)
if (weight[i + 1] == 1)
if (incl[N - i - 1] == 1) {
yes = false;
break;
}
if (yes) {
all++;
all = all % D;
}
return 0;
}

int process(byte x)
{
if (x == N)
return 0;
add(x);
incl[x] = true;
if (!weight[0]) {
check();
process(x + 1);
}
sub(x);
incl[x] = false;
process(x + 1);
return 0;
}

int main()
{
//open
ifstream ifs("input.txt");
ifs >> N >> L >> D;
getline(ifs, s);
getline(ifs, s);
ifs.close();
//init
host = new byte[L];
weight = new byte[N + 1];
incl = new byte[N];
memset(host, 0, sizeof(host));
memset(weight, 0, sizeof(weight));
memset(incl, 0, sizeof(incl));
//process
for (int i = 0; i < L; i++)
host[i] = s[i] - '0';
int q = s.length();
q--;
while (q >= 0)
weight[N - 1 - q] = s[L - 1 - q--] - '0';
check();
process(0);
//free
delete[] host;
delete[] weight;
delete[] incl;
//close
ofstream ofs("output.txt");
ofs << all;
ofs.close();
return 0;
}

Как можно ускорить процесс? В системе acm-test проходит один тест из 14, на остальные пишет либо ошибка времени выполнения, либо нарушен предел времени.

Приводите ссылку на источник задачи.

Думаю, эту задачу можно решить динамическим программированием

#include <windows.h>

Да за это compile errror полагается!!!

Ссылка:

acm-test.bsu.by ->
Задания ->
Теория алгоритмов ->
Рекуррентные

, только вы не сможете зайти без регистрации.

Хм, почему за "#include <windows.h>" полагается compile error, если всё замечательно не только компилируется, но и линкуется?
Скажите, пожалуйста, если есть какие предложения по задаче.

Имеется в виду 2 в степени N, а не 2*N. Всё степени, не умножение.

Ну, вот как я бы это решил на питоне:

N=6
W=[0,0,1,0,0,0]   # двоичная запись числа W, дополненная нулями слева до длины N

f = [1, 0]
for i in reversed(range(N)):  # i=N-1, N-2, ..., 0
    g = [0, 0]
    for x in [0, 1]:
        for y in [0, 1]:
            if x + y == 2: continue
            for c in [0, 1]:
                if (x + W[i] + c) % 2 == y:
                    g[(x + W[i] + c) / 2] += f[c]
    f = g

print f[0]

Хм, почему за "#include <windows.h>" полагается compile error, если всё замечательно не только компилируется, но и линкуется?

Да потому что не все в мире пользуются твоей виндовс, you insensitive clod!

Спасибо большое за алгоритм, хоть Вы и обзываетесь ))) 13 из 14 тестов прошли, в 14ом нарушен предел времени, но это уже не такая большая проблема! Идея у меня была правильная, вот только реализовать всё можно было гораздо быстрее, как здесь. Ещё раз спасибо!

Идея у меня была правильная,

А бы ни близко е назвал ваш рекурсивный перебор (бэктрэк) в данном случае правильное идеей. Для совсем маленьких чисел, скажем N<=20, он бы еще работал, но до миллиона вы бы его никак не заоптимизировали.

Я не о рекурсии, а о рекуррентном соотношении. Его можно по-разному запрограммировать, я сделал рекурсией - и экспоненциальное время дало о себе знать. Опыта в подобных задачах у меня почти нет, так что буду учиться!

В вашем алгоритме не рекуррентного соотношения.
Есть рекурсия, да, но рекуррентного соотношения - основы динамического программирования - нет и в помине.

Ну да, действительно. Я почитал кое-что об этом, Вы правы. Буду учиться.