Как оптимизировать перебор?

На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K–1). Ведущие нули в числах допускаются.
В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают AM рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t–1, t–2 и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.
Напишите программу, которая по известным ставкам, сделанным телезрителями, находит число, которое должна назвать телеведущая, чтобы фирма-организатор розыгрыша выплатила в качестве выигрышей минимальную сумму. Для вашего удобства ставки, сделанные игроками, уже упорядочены по неубыванию.
Входные данные

В первой строке входного файла INPUT.TXT задаются числа N (количество телезрителей, сделавших свои ставки, 1<=N<=100000), M (длина чисел 1<=M<=10) и K (основание системы счисления 2<=K<=10). В следующей строке записаны M чисел A1, A2, …, AM, задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (1<=A1<=A2<=…<=AM<=100000). В каждой из следующих N строк либо в одной строке через пробел записано по одному M-значному K-ичному числу. Числа идут в порядке неубывания.
Выходные данные

В выходной файл OUTPUT.TXT выведите наименьшую сумму, которую придется выплатить в качестве выигрыша.


Развиваю попытку решить с BFS, очень проигрываю по скорости. Есть идеи более оптимального метода?
  • Вопрос задан
  • 3691 просмотр
Пригласить эксперта
Ответы на вопрос 2
jcmvbkbc
@jcmvbkbc
"I'm here to consult you" © Dogbert
Эту задачу можно решить без перебора, в один проход.
Если мы при просмотре чисел в каждый момент знаем, какова минимальная сумма Si по совпадениям длиннее i цифр для чисел, совпадающих с текущим в i первых цифрах, и каково число Ki этих совпадений для этой суммы, мы можем узнать эти характиристики и для i-1, а именно: при каждой смене i-1й цифры, если следующая цифра отличается от предыдущей больше чем на 1, Si-1 = Ki-1 = 0 (т.к. можно загадать число с пропущенным префиксом); иначе, Si-1 = min(Si) + (Li - Kmin(Si)) * Ai, где Li -- текущее количество чисел, совпадающих до i-го знака.
Ответ написан
Entii
@Entii Автор вопроса
#include <fstream>

using namespace std;

typedef long long x;
x N,M,K,j,I,A[11];

char p[2<<17][10];

x z(x i, x l, x r)
{
x m=x(2)<<35,t;
if (i>=M || l>=r)
m=0;
else
{
x L=l,R;
for (x c=48;c<K;c++)
{
for (R=L;R<r && p[R][i]==c; R++)
;
if (t=z(i+1,L,R), t<m)
m=t;
L=R;
}
}
return m+A[i]*(r-l);
}

int main()
{
fstream i("input.txt"),o("output.txt");
i>>N>>M>>K;
K+=48;
for (;I<M;I++)
i>>A[I+1];
for (;I>1;I--)
A[I]-=A[I-1];
for (;j<N;j++)
i>>p[j];
o<<z(0,0,N);
}

Моё решение. Справилось с самым худшим раскладом довольно шустро, используется разумный перебор вариантов.
P.S. для рекорда требовалось написать самое короткое решение, поэтому код такой.
P.S.S. в некоторых компиляторах требуется изменить o("output.txt") на o("output.txt",2)
Если кому-то будет интересно, могу рассказать принцип работы в комментариях.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы