Дано: число знаков в трамвайном билете, четное число n
Найти: Сколько номеров счастливых билетов возможно с таким количеством знаков

Нужно написать программу на том ЯП, который знаете.
Я написал на JS, вроде работает. Правда говнокод, но это не важно. Главное что быстро.

Что такое счастливый билет, надеюсь, не нужно объяснять.

(1) Пощади, не объясняй... Пусть будет интрига.

Ещё одна задача: почему эта задача в секции Админ?

Нет четкого определение счастливых номеров и чисел. У всех народов свои.

(3) Вроде эта секция ближе всего к программированию.

(4) Будем решать задачу для русского народа.

Перебором небось делал?

Лет в 12 писал программку (джаваскриптов тогда не было, поэтому на паскале) по вычислению такой херни, но мне было интересно распределение счастливых билетов.
P.S. как и ожидалось распределяются хаотично.

https://ru.wikipedia.org/wiki/Счастливый_билет#Явные_формулы

(6) Минимум 2 системы.

Вот поэтому надо сначала читать документацию, а потом бросаться говнокодить и публиковать "задачки". Хотя тебе, Пашенько, это не понять.

Интереснее задача - отрывается от ленты билет и надо определить по его номеру сколько ещё следует оторвать билетов, чтобы добраться до счастливого

(11) Сколько минимум или сколько вообще? Вообще ответ 1000

a = [f"{x:3}{y:3}" for x in range(1000) for y in range(1000) if (x // 100 + x // 10 % 10 + x % 10) == (y // 100 + y // 10 % 10 + y % 10)]

не благодари

(12) от конкретного билета зависит

(1) Это суеверия.

(15) "Девять миллиардов имён Бога", Артур Кларк =)

Число счастливых билетов (6 цифр) равно числу решения уравнения: X1+...+X6 = 27.
Для этого уравнения производящей функцией (число решений) будет F(z) = (1+z+z^2+...+z^9)^6 (в F(z) коэффициент при z^K - число решений с правой частью = K).
Осталось раскрыть скобки и привести подобные члены. Примерно 55262.
Формулы в (9) означают, по сути, то же самое.

почему X1+...+X6 = 27 ?
билет 100001 счастливый. сумма равна 2

(18) Каждому билету (X1,...,X6) соответствует ((X1,X2,X3,9-X4,9-X5,9-X6). Для счастливого у соответствующего сумма цифр = 27.
(11) Если уметь считать лексикографическое расстояние от точки до плоскости, наверное, можно.

(0) ограничение для N какое?

(20) n=2k, где k - натуральное (без нуля)

(17) Как будет выглядеть конечная формула?

(20) Чем больше, тем лучше.

Я сначала сделал рекурсивно, тупить комп начинал при n=20.
Добавил кеширование, при n=600 результат готов за секунду.
Сейчас думаю переделать без рекурсии, на циклах. Должно быть быстрее, но менее красиво.

Переделал без рекурсии. Неплохо получилось, довольно быстро

На 1000 знаках считат за секунду примерно

43915377631485458833479195230066153719286944334482728752374053320838115549858215565208114024962581615271402777015308860811212191792925923420969245129026328855876283838950018847412261224256990261761381820882172258736944579430682988506846775667343870902385081283670699609193547885848109732716362746796153011795708348022666029193500283564418807759271551081373779123257867610692495382036284602470373148913167119989269217875645654027776769033062343309789310407588134130712945050743818476141567323017123825020605494271348234384993864889467972164682730612464880147233546856797400639562612752002615437076311121391023596317082847329014317458804619697148653887797581910156879691294695939406480408606191910521233273911227547281809981945968861084523355380408980835668951165580638949544820954513675253429624139383129988263577066141033310554019420957933562781195853828346312316335609433523730382740220073818131409728591308797936951756784792808940315669316877274638709352719988179534188996183873338261211951586180

Вот такой ответ для 1000-значных чисел.

https://www.youtube.com/watch?v=wg77OW18jjk

(n => {
    const cache = [[1n]];
    for (let n2 = 1; n2 < n / 2 + 1; n2++) {
        cache[n2] = [];
        for (let i = 0; i < n2 * 9 + 1; i++) {
            cache[n2][i] = 0n;

            for (let i2 = i; i2 >= 0 && i2 > i - 10; i2--) {
                cache[n2][i] += cache[n2 - 1][i2] || 0n;
            }
        }
    }

    let sum = 0n;
    for (let i = 0; i < n * 9 / 2 + 1; i++) {
        sum += cache[n / 2][i] ** 2n;
    }

    return sum;
})(1000)

(29) Это мой код, можно запускать прямо в консоли браузера.

Думаю, можно оптимизировать если использовать математические формулы.
Михаил Козлов, как там твое уравнение решается?

(26) Вот это быстродействие. 1С тоже самое будет считать годами............

(31) зачем это считать на 1с?

(31) Что есть, то есть. Удобная штука, когда нужно что-то по быстрому просчитать. И браузер есть на любом компе, просто пишешь в консоли скрипт, запускаешь, и получаешь что хотел, без установки всяких платформ 1С или интерпретаторов питонов или джава-машин.

(30) Раскрываешь скобки, приводя подобные члены. Получится число решений для любой правой части. Трудоемкость линейная по N.

(34) Должна быть функция от n, а в твоем выражении нет нигде n. Не понятно куда ее ставить. Покажи пример.

Писал для 2N=6. В общем случае F(z) = (1+z+z^2+...+z^9)^2N.
Всего членов в F(z) после раскрытия скобок и приведения подобных (это будет полином) = 1+9*2N.
Это и будет трудоемкость.
Для 1 уравнения A1*X1+...+Ak*Xk = B, 0<=Xk<=Pk, Xk - целое, F(z) = (1+z+z^2+...+z^P1)*(1+z+z^2+...+z^P2)*...*(1+z+z^2+...+z^Pk) - производящая функция числа решений уравнения.
В этом случае трудоемкость примерно P1+P2+...+Pk.
Можно производящую функцию написать и для нескольких уравнений. Трудоемкость будет примерно ПРОИЗВЕДЕНИЕ (по уравнениям) СУММ коэффициентов уравнения.

(36) У меня трудоемкость где-то n^2 получилась.

(37) При раскрытии скобок если считать промежуточные операции, наверное, n^2.

(38) Козлов молодец, хоть без программы, остальным по двойке.

>>вроде работает. Правда говнокод, но это не важно. Главное что быстро

Это прям девиз Г1Сов

(40) Тут критично быстродействие. Если переделывать покрасивше, без циклов, без переменных, то получится в разы медленнее. Поэтому из двух зол выбираем меньшее, это мой девиз.

(41) ерунда. Нормальный код не угроза производительности

(41) и собсно, быстродействие критично для кого? Преждевременная оптимизация, да ещё и с угроблением сопровождаемости кода... ой-вэй, вот же кому-то работничек достанется

(42) Как же нет если да

(43) Ты с чем-то перепутал, наверное. Какая же она преждевременная, если конечная? И какое нафиг сопровождение, если оно не требуется? Ты наверное так и работаешь, прочитал что-то где-то, не понял как применять, и применяешь где надо и где не надо. Головой думай в первую очередь

как-то так. для 6 цифр

[m=[], [...Array(1000)].forEach((_, i) => [...Array(i+1)].map((_, j)=>j).filter((j)=>((Math.floor(i/100) + Math.floor(i/10)%10 + i%10) == (Math.floor(j/100) + Math.floor(j/10)%10 + j%10))).forEach((j) => {if (i+j>0) { m.push(i*1000+j); if (j!=i) m.push(j*1000+i);}}))][0]

(46) Вот это высший класс!
На 20 цифрах долго выполняется?

(45) подрастешь и поймёшь, что такое бездумная оптимизация и почему её стоит избегать. Про код, который не требует сопровождения, бабушкам будешь рассказывать. С вероятностью 95% в говнокоде сидит труднодиагностируемая ошибка. В говнокоде всегда есть место ошибкам, они ходят рука об руку. Со временем ошибка обнаружится. Уже другой человек, насилуя свой мозг и с трудом здерживая рвотный рефлекс, полезет исправлять эту ошибку. Но не тут-то было, следом вылезет другой сюрприз говнокода - исправление в одном месте ведёт к поломкам в другом месте

(48) просто надо писать без ошибок. сразу и в гранит!

(48) сижу ковыряю упп... Переписанное не так чтобы в хлам, но дописок 3 вагона... По комментам не менее 6 чел писало... Ух и жесть местами... И ведь и мой код кто-то будет хаять.
PS кому-то рекурсия норм - кто-то всегда ее низводит до цикла... Кого-то будет бесить одно - кого-то другое... Дело вкуса.

Полный перебор не интересен, да

(49) ну, это не про любителей овнокода. Они пишут до первого "вроде заработало" и потом смело в продакшн

(50) свой код всегда кажется лучше и понятнее

(52) >>свой код всегда кажется лучше и понятнее
пока ему не исполнится пару лет )))

https://ru.wikipedia.org/wiki/Счастливый_билет
"Счастливым считается полученный в общественном транспорте билет, в шестизначном номере которого сумма первых трёх цифр совпадает с суммой трёх последних"

И да там по ссылке формулы есть

(9) сорри лень было все читать

(53) ну и это тоже)

вообще, задача сводится к нахождению для каждого N от 0 до P^(K/2) множества наборов (x[1], x[2] .. x[K/2]): ∑(x[i]) = N, x[1] <= x[2] <= ... <=x[K/2].
потом дополняем множество наборов перестановками с сохранением уникальности, и делаем декартово произведение.
где:
P - система счисления,
К - количество цифр: K % 2 == 0

(57) Основная часть это эффективный генератор перестановок. В свое время это давали на олимпиадах городского уровня.

(48) Твои теории тут совсем не к месту. Понятно что ты это только что узнал и хочешь всем рассказать. Но не тут тему выбрал для этого.

(58) Да, и там как раз фигурирует факториал

(59) уже много лет в разработке, мне не в первой сталкиваться с говнокодом и его последствиями. Так что я знаю, о чём говорю

И все-таки где определение счастливого билета?

(61) Молодец, раз много лет в разработке, то знаешь говнокод. Мы это уже поняли, можешь не повторять. Оффтоп потому что.

(62) В Википедии, писали выше: https://ru.wikipedia.org/wiki/Счастливый_билет

Но счастливый - это мелочи. Мне один раз попался несчастливый, причем пятизначный, на междугороднем автобусе. Там был номер 66613. Еще бы место попалось 13, я бы вообще офигел.