Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.03.2009, 17:45
гость

 
Сообщений: n/a

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

Вам даны рычажные весы. На левой чаше весов лежит один камень с весом 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, на остальные пишет либо ошибка времени выполнения, либо нарушен предел времени.
  #2  
Старый 08.03.2009, 17:56
гость

 
Сообщений: n/a

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

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

Цитата:
#include <windows.h>
Да за это compile errror полагается!!!
  #3  
Старый 08.03.2009, 23:36
гость

 
Сообщений: n/a

Ссылка:

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

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

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

 
Сообщений: n/a

Имеется в виду 2 в степени N, а не 2*N. Всё степени, не умножение.
  #5  
Старый 09.03.2009, 02:26
гость

 
Сообщений: n/a

Ну, вот как я бы это решил на питоне:
Код:
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!
  #6  
Старый 09.03.2009, 19:44
гость

 
Сообщений: n/a

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

 
Сообщений: n/a

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

 
Сообщений: n/a

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

 
Сообщений: n/a

В вашем алгоритме не рекуррентного соотношения.
Есть рекурсия, да, но рекуррентного соотношения - основы динамического программирования - нет и в помине.
  #10  
Старый 10.03.2009, 22:31
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Эффективность алгоритмов сортировки Andrey K Сортировка и поиск 10 12.12.2009 18:50
Помогите решить задачи по теории графов! Срочно надо=( nefaktor Графы 0 09.12.2008 03:02
Объединение стохастических алгоритмов see Математические алгоритмы (другое) 0 29.08.2008 16:07
Российский конкурс алгоритмов Gribok Участие 0 15.12.2007 13:28
задачи по теории графов. кто силен? незарегистрированный Графы 1 03.12.2006 02:15