|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Egorov Pavel 2:5080/169.35 22 Oct 2001 00:02:50
To : Michael Sedov
Subject : Задачка!
--------------------------------------------------------------------------------
On Friday October 19 2001 you wrote to All:
MS> Заaeачка такого плана. ужно посчитатue количество счастливых
MS> билетов, ну в смысле таких, у которых сумма первой половины
MS> чисел равна сумме второй. Полный перебор не приемлим. Вхоaeные
MS> aeанные: n - кол-во oeифер в кажaeой половине, k - система счисления.
MS> n <= 127, k <= 127. При полном переборе, на пример, aeля n = 4 и k = 50
MS> считает мой комп около 25 минут. По этому нужно приaeуматue что-нибуaeue
MS> оригиналueное.
Hу! Стандартная задачка на динпрог.
Вообще нам такую задачку для 6 хначных билетов в с.с по основанию 10 давали в
школе на контрольной - не решил никто. Зато препод на разборе задач весь урок
потратил чтобы рассказать как она решается! (Что то было про цифру 27 :)
А динпрогом она решается запросто!
За O(n*n*k*k)
Вообщем:
P(n,s) - количество различных левых частей из n цифр с суммой s
Тогда очевидно
P(n,s) = Sum(i=0..9){P(n-1,s-i)}
где s<0 => P(n,s) = 0
s=0..9 => P(1,s) = 1
P(1,s) - знаем
P(n+1,s) - считаем по вышепредложенной формуле.
А ответом очевидно будет являться Sum(s=0..N*9){P(n,s)*P(n,s)}
Реализацию я из принципа не дам (читай - писать лень :) - сам трудись!
MS> Заранее спасибо.
Пожалуйста!
Hу, Все! Пока Michael.
--- GoldED/386 3.00.Alpha3+
* Origin: 2+2=4 это не тождество, а выражение равное TRUE (2:5080/169.35)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
