Определите количество ―"почти счастливых билетов"

Question

Номер билета из n цифр, где n чѐтное, называется ―"почти счастливым", если в нем сумма первых n/2 цифр ровно на единицу отличается от суммы остальных цифр. Например, 123005 или 123700. Номер может начинаться с любого числа нулей. Определите количество ―"почти счастливых билетов" для следующих значений n:

1) n = 6

2) n = 10

3) n = 20

4) n = 100

Опишите, как именно вы получили соответствующие значения.

Мои догадки:

Значит я разобрался и вот что максимум понял это то,что например,если число 6-ти значное , то мы берем 6/2 и получаем 3, потом сумму трех первых цифр складываем и складываем сумму оставшихся цифр, и сравниваем эти две суммы, нужно чтобы между ними была разница в единицу и если такая присутствует,то этот билет "почти счастливый".

Answer 1

Исходя из Номер может начинаться с любого числа нулей к примеру 000001,001000 и так далее можно прийти к тому что числа растут 000001,001000,002001,002003,003002,003004,004003,004005,005004,005006...055054,055056,056055,056057...999998 разница между всеми этими числами
999,1001,2,999,2,999,2,999,2... и так будет далее возьмём максимальное значение 999998 9+9+9=27 соответственно тут уже закономерность и прогрессия которую ты учил в 9 классе.
Считай An (для каждого отдельно) то есть для q=2 и для q=999 и потом их сплюсуй а n=6 n=10 ты получишь исходя из результата An1 + An2 (не имееться ввиду 000001 как An1 и 001000 как An2) к примеру получиться n "почти счастливых" билетов это n*на 1,8 получишь количество счастливых билетов для n=10 так же потом делаешь и для n=50 и n=100 ты есть если бы было к примеру n=1000 ("счастливых билетов") *1,8 = 1800 для n=10 и 90000 для n = 50 соответственно 90000*2=180000 для n=100 На число 1001 не обращай внимание оно 1 раз только получилось

То есть у тебя есть:

d1=2  
d2=999
A(max)=999998  
A(min)=000001  
A(a)-?

Про q могу ошибиться это может d я уже не помню как там это подписуется q наверное геомертическая а d алгебраическая прогрессия но дело не в этом оно тебе особо не поможет тебе больше помогут формулы скорее всего это алгебраическая закономерность я бы считал по формуле A(n)
Сори за выделения просто сайт думал что это код
Я не гарантирую что это 100% правильное решение но я бы решал так

Answer 2

Ну, аналитическую формулу не выведу, но посчитать можно...

Рассмотрим D(k,l) - число k-значных чисел (с ведущими нулями в том числе) с суммой цифр l.

А теперь посмотрим общее число почти счастливых билетов (для k=n/2)...

Для суммы слева 0 справа годится D(k,1) чисел - итого D(k,0)*D(k,1)
Для суммы слева 1 справа годится D(k,0)+D(k,2) чисел - итого D(k,1)*D(k,0)+D(k,1)*D(k,2)
Для суммы слева 2 справа годится D(k,1)+D(k,3) чисел - итого D(k,2)*D(k,1)+D(k,2)*D(k,3)
...
Для суммы слева 9k справа годится D(k,9k-1) чисел - итого D(k,9k)*D(k,9k-1)

Суммируя, получаем общее количество как

Теперь как считать D(k,l) - простое динамическое программирование:

из того соображения, что к числу с k-1 цифрой приписываем цифры от 0 до 9. Начальные условия для D(0,l) очевидны - при l==0 получаем 1, для остальных - 0.

Собственно, все. Пишем программу. Мемоизацию (или ДП снизу вверх) дописывайте сами :)

long long int D(int k, int l)
{
    if (k==0) return (l==0);
    long long int sum = 0;
    for(int j=0; j<=9; ++j) sum += D(k-1,l-j);
    return sum;
}

long long int res(int k)
{
    long long int sum = 0;
    for(int l = 1; l <= 9*k; ++l)
        sum += D(k,l)*D(k,l-1);
    return 2*sum;
}

int main(int argc, const char * argv[])
{
    for(int n = 2; n <= 12; n+=2)
        cout << setw(2) << n << ":  " << res(n/2) << endl;
}

Результаты для небольших n:

 2:  18
 4:  1320
 6:  109494
 8:  9564720
10:  860000900
12:  78783456336
14:  7312306950130

Для очень больших n нужна длинная арифметика...

P.S. Не выдержал - переписал... См. тут.

Для n==100 - 277195334834500944669228740375357778944913131715952295846893641728073727377808583283711688841134000 почти счастливых билетов...

БЛОГ НА HUSL

Определите количество ―"почти счастливых билетов"

Ответы (2 шт):