На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо 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, очень проигрываю по скорости. Есть идеи более оптимального метода?
Эту задачу можно решить без перебора, в один проход.
Если мы при просмотре чисел в каждый момент знаем, какова минимальная сумма Si по совпадениям длиннее i цифр для чисел, совпадающих с текущим в i первых цифрах, и каково число Ki этих совпадений для этой суммы, мы можем узнать эти характиристики и для i-1, а именно: при каждой смене i-1й цифры, если следующая цифра отличается от предыдущей больше чем на 1, Si-1 = Ki-1 = 0 (т.к. можно загадать число с пропущенным префиксом); иначе, Si-1 = min(Si) + (Li - Kmin(Si)) * Ai, где Li -- текущее количество чисел, совпадающих до i-го знака.
Потому что это динамическое программирование: чтобы найти оптимальное решение задачи, нужно найти оптимальное решение её подзадачи (а размер задачи уменьшается с ростом длины совпадения).
Ааа, видимо я понял, вы имеете ввиду динамику сверху-вниз? Либо я вовсе не понял решения. Чтобы узнать S1, мне нужно узнать S2, да? И так спускаться ресурсивно вниз, до максимальной длины числа?
Не уверен, что рекурсия здесь поможет. Но -- да, чтобы узнать S1 нужно сначала узнать минимальный S2 для фиксированной первой цифры, либо найти пропущенную вторую цифру (и тогда S2 равен 0). Я сегодня-завтра постараюсь накидать код решения, потому что словами как-то сложно объяснить.
#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)
Если кому-то будет интересно, могу рассказать принцип работы в комментариях.
Простой
