Алгоритм определения количества "счастливых" чисел

← →
V-Isa © (2004-03-19 17:19) [0]

"Счастливым" считается число, сумма цифр в котором слева до середины равна сумме цифр справа до середины. Так, 123006 - "счастливое", т.к. 1+2+3=0+0+6, а 12306 - нет, т.к. 1+2<>0+6!
Необходим алгоритм определения количества "счастливых" чисел в заданном диапазоне. Например, необходимо определить сколько таких чисел встречается от 1234 до 56789 и т.п. Обычный перебор не подходит, так как количество разрядов в исходных данных может достигать 20 и более, а это длительный процесс.

← →
WebErr © (2004-03-19 17:25) [1]

Это олимпиадная задачка по комбинаторике, клёво, что она здесь появилась! Сейчас попробую решить! ... :))))

← →
WebErr © (2004-03-19 17:26) [2]

> Обычный перебор не подходит, так как количество разрядов
> в исходных данных может достигать 20 и более, а это длительный
> процесс.

Какой к чертям перебор!!! :))))

← →
V-Isa © (2004-03-19 17:28) [3]

Вот именно, просто я уже неделю пытаюсь ответ получить, а мне только говорят - попробуйте перебором!

← →
WebErr © (2004-03-19 17:30) [4]

Эта задачка эквивалентна другой:
сколько пар чисел, одно от А до В, другое от C до D, таких, что сумма цифр одного равна сумме цифр другого...

← →
WebErr © (2004-03-19 17:32) [5]

<A>acm.timus.ru</A>

← →
WebErr © (2004-03-19 17:37) [6]

Надо разложить каждую цифру одного числа (из двух) на единицы и посмотреть, сколькими способами можно расставить между единицами n-1 перегородку, где n - количество цифр числа = длина строки div 2 (или shr 1)... Но меня смущают граничные диапазоны... :))))

← →
WebErr © (2004-03-19 17:38) [7]

← →
WebErr © (2004-03-19 17:44) [8]

Например числа от 12345 до 76543210 это можно представить в виде пар чисел от (0012, 0045) до (7654, 3210)... Но может быть и от 12345 до 13000, тогда от (12, 00) до (13, 45) - упорядочиваем поэлементно пары! :))))

← →
Goida © (2004-03-19 17:44) [9]

Переведи в строку и обрабатывай её. Наилегчайший способ :) Думаю, и рациональный. Это ведь лаба? Не так ли? Если так, то кодить за тебя здесь ни кто не будет.

← →
V-Isa © (2004-03-19 17:44) [10]

Что значит перегородку. Не могли бы более подробнее? Буду признателен, если ответ вышлете на мыло. Очень надо решение!

← →
WebErr © (2004-03-19 17:45) [11]

Вот я и подвёл котёнка к молоку!!! Дальше техническая часть - сам попробуй! :))))

← →
V-Isa © (2004-03-19 17:48) [12]

Это не лаба, просто столкнулся с желанием любимой девушки подсчитать, сколько же...?

← →
WebErr © (2004-03-19 17:50) [13]

> Что значит перегородку

Это значит, что сумму цифр числа 123 - это 1+2+3 я представляю как 1+1+1+1+1+1 6 раз! Теперь расставляем "перегородки" (1+1+1)+(1+1)+(1) разбивая n-1 перегородкой число на n частей n=3. На мыло код слать не буду - самому тоже надо что-то сделать - это я не про себя... :))))

← →
WebErr © (2004-03-19 17:56) [14]

> Это не лаба, просто столкнулся с желанием любимой девушки
> подсчитать, сколько же...?

СВЯТОЕ! Ну тогда сам бог велел тебе немного подумать головой! Напрягись ради любимой! :))))

← →
V-Isa © (2004-03-19 17:56) [15]

А как быть с числами до 10? Забивать вручную?

← →
WebErr © (2004-03-19 17:57) [16]

> А как быть с числами до 10? Забивать вручную?

???

Например, диапазон от 10 до 15... Разбили: (1,0) до (1,5)... и что? Или я чего-то не понял, сбросьте на мыло, а то уже убегаю, заранее огромное спасибо! Мастера Дельфи есть мастера, хоть намекнули, не то, что математики :-) //шутя...

А разве есть что-то, что можно поставить в какое-то соответствие сумму цифр одной части числа другой??? Помоему в математике такого нет. Эта задачька как раз и нужна для того, что тот кто её делает научился выделять значения десятичных разрядов... Решается только перебором. Моим способом гораздо легче.

← →
Chcnger (2004-03-19 18:05) [19]

Решается с помощью динамического программирования.
Разбор етсь тут g6prog.narod.ru

Интересно как найти билеты, если их разряд 2N, где 1<N<50

← →
Chcnger (2004-03-19 18:09) [20]

Мое решение задачи 1044 с acm.timus.ru (про счастливые билеты, решается при помощи дин. программирования)
{1044} var I,K,RES,N,luck,sum,spec:longint; a:array[0..100]of longint; s:string; begin res:=0; fillchar(a,sizeof(a),0); readln(n); k:= n div 2; s:=""; for i:=1 to k do S:=s+"9"; val(s,k,res); res:=0; for i:=1 to k do begin sum:=0; luck:=i; for spec:=1 to n div 2 do begin Sum:=sum+Luck mod 10; Luck:=Luck div 10; end; inc(a[sum]); end; for i:=1 to length(s)*9 do begin res:=res+ a[i]*a[i]; end; Writeln(res+1); end.

> Chcnger (19.03.04 18:09) [20]
> Мое решение задачи 1044 с acm.timus.ru (про счастливые билеты,
> решается при помощи дин. программирования)

О! Точно, №1044! :)))) Если не трудно скинь код ему на мыло! 8*)

> Интересно как найти билеты, если их разряд 2N, где 1<N<50

А чем случай 2N отличается от 2N+1?! Можно ведь просто выкинуть "лишнюю" среднюю цифру! :))))

>V-Isa
ты каждый месяц теперь будешь этот вопрос задавать? уже на Валентинов день обсуждали :))

Алгоритм определения количества "счастливых" чисел Найти похожие ветки