Динам. программирование?

← →
ЧимбаБумба (2004-02-12 19:50) [0]

Здравствуйте!
Помогите разобраться(не решить) задачу, дайте намек на то, как ршеть
задача с acm.timus.ru
(хотя можно и с примерами :) )
Lucky tickets.
Ограничение времени: 2.0 секунды
Ограничение памяти: 1 000 КБ

Вступление
You are given a number 1<=N<=50. Every ticket has its 2N-digit number. We call a ticket lucky, if the sum of its first N digits is equal to the sum of its last N digits. You are also given the sum of ALL digits in the number.

Задача
Необходимо посчитать количество "счастливых" билетов с заданной суммой цифр, среди тех, номер которых состоит из 2*N разрядов. "Счастливым" является билет, у которого сумма первых N цифр равна сумме N последних цифр.

Исходные данные
Во входном файле находятся два числа разделенных пробелом: первое - N (1<=N<=50); второе - сумма цифр интересующих нас билетов (неотрицательное число не превосходящее 1000).

Результат
В качестве ответа необходимо вывести найденное число "счастливых" билетов.

Пример исходных данных
2 2
Пример результата
4

Подсказка
В примере условию удовлетворяют билеты: 0101, 0110, 1001, 1010

← →
Defunct (2004-02-13 02:40) [1]

простой перебор не подходит из-за ограничений по времени.

N - число цифр в числе
FullSum - сумма всех цифр в числе.

1. тогда так, нечетная FullSum или N - сразу результат 0.
2. делим сумму цифр пополам, S2 := FullSum div 2;

3. Ищем все числа с количесвом цифр N/2 у которых сумма цифр равна S2.
4. Возводим в квадрат полученное число.

(Пункт 3 нужно разбить на подпункты для сокращения времени поиска), перебор опять же не подходит, потому что 10 в 26-ой степени вычислений (при N=50), за 2 секунды не справится ни один из известных копьютеров на сегодня.

← →
Defunct (2004-02-13 02:51) [2]

Вариант ускорения пункта три:

Делим искомое число на две равных части (число цифр M=N/4)
последовательно для одной части ищем все комбинации цифр для которых S14 (сумма всех цифр):
1. S14_0 = 0
2. S14_1 = 1
..
M. S14_M = M

Сумма цифр S2 будет вычисляться как:
S2:= (S14_0 + S14_M) + (S14_1 + S14_M-1) + .. + (S14_M + S14_0)

Так мы сократим число операций уже до 10 в 13-ой степени.

нужно разбить число, до тех пор пока мы не получим ~10 в 8-ой степени вычислений, т.е. еще один раз.

Удачи в решении.

← →
Defunct (2004-02-13 02:57) [3]

> Сумма цифр S2 будет вычисляться как:
> S2:= (S14_0 + S14_M) + (S14_1 + S14_M-1) + .. + (S14_M + S14_0)

Тут имелось ввиду число элементов для каждой суммы цифр.

Res2 := (F(S14_0) + F(S14_M)) + (F(S14_1) + F(S14_M)) + .. + (F(S14_M) + F(S14_0))

Res2 - количество чисел, которые удовлетворяют условиям:
число цифр = N/2, сумма цифр = FullSum/2;

Функция F(S14_ X) - возвращает количество чисел, которые удовлетворяют условиям:
число цифр = N/4
сумма цифр = X

← →
Defunct (2004-02-13 03:07) [4]

> M. S14_M = M

M = S2

может же быть и такой вариант
входные данные:
24 12

одно из возможных решений:
930000000000|000000| 000084

Мы перебираем только выделенную часть
ее в свою очередь можно разбить еще раз:
930000000000|000000|000| 084

и т.д.

Динам. программирование? Найти похожие ветки