Несчастливые билеты

[Аватар]

Там для N=100 и K=3 вообще немыслимое количество возможных чисел - 3^100. Так что перебор вообще нереален и только хитрый алгоритм ))

[ViktorR]

Номер билета является счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся, к примеру: билет с номером 561743 счастливый, так как 5+1+4+3=6+7.

Но вопрос о поиске несчастливого билета. Т.е. есть ли варианты получить счастливый билет. Если нет то и ...
Как вариант:
1. Формируем массив из 10 элементов. Выделяем цифры числа и инкрементируем соответствующий элемент массива и считаем сумму цифр.
2. Если сумма нечетная - это несчастливый билет.
3. Если сумма четная, то просматриваем элементы массива. Те элементы, в которых число цифр четное инициируем нулем, а те, в которых число цифр нечетное - инициируем единицей.
4. Ищем сумму оставшихся цифр. Если сумма нечетная - это несчастливый билет.
5. Если сумма четная, то перебираем варианты. Тут вроде и о рюкзаке можно подумать.
6. Поскольку набор оставшихся цифр ограничен и известна сумма, которую надо получить, то решение может быть найдено достаточно быстро. Любой вариант, когда сумма складывается, дает счастливый билет.
PS: Поправьте, если что не так. Такой алгоритм только что в голову стукнул и некогда попробовать.

Как-то так, ...

[FPaul]

Мне кажется, что здесь расширение обычных "счастливых билетов".
Те ведь как искались (например, для N=6):
- для группы из 3 (6/2=3) цифр искались все возможные суммы цифр перебором.
- получался массив S[0...27], каждый элемент которого был равен количеству чисел из 3 цифр, сумма которых равна данному индексу массива.
- в цикле перемножали S[i]*S[i] и суммировали произведения. Итоговая сумма была ответом.

Так может и здесь требуется получить матрицу S[i,j], элемент которой равен количеству чисел длиной j, сумма цифр которых равна i.
Далее перемножая S[i,j]*S[i,N-j] и суммируя произведения получим Количество счастливых билетов. После вычитания из 10^N этого количества получим ответ.
Матрица для N=100 будет достаточно значительной S[0..9*100, 1..99] ~90тыс элементов и ещё и по форме - треугольной, заполненной наполовину.
Её элементы, возможно, будут длинными числами. Но это всё равно будет быстрее, чем простой перебор.
Осталось сообразить, как заполнять матрицу на основе ранее заполненных ячеек.

[Kef1r]

Нашел код на Phyton'e. Его вообще не изучал. Мб кто-то может переделать под C#/C++?

+# Требуется написать программу, которая определит количество несчастливых N-значных номеров(номером 561743 счастливый,
# так как 5+1+4+3=6+7), которые можно составить, используя цифры от 0 до K. В номерах допускается любое количество ведущих нулей.
# Входные данные: два целых числа N и K (1 <= N <= 100, 1 <= K <= 9, N*K <= 300).
# Выходные данные: количество несчастливых номеров для заданных N и K.

import time

luckysum = 0

#Подсчет всех счастливых подмножеств
def LuckyNumGen(n, mi, fk, num,farr,isum,N,K):
    
    if n == N:
        if fk & 1:
            return
        for i in range(0,(fk + 1)):
            isum[i] = 0 
        isum[0] = 1
        s = 0
        for i in range (0,N):
            if isum[fk // 2]:
                break
            for j in range (s,-1,-1):
                if isum[j]:
                    isum[j + num[i]] = 1
            s += num[i]
        if isum[fk // 2]:
            tmp = 1
            rest = N
            for i in  range (0,(K + 1)):
                for j in range (0,farr[i]):
                    tmp = tmp * rest
                    rest-=1
                    tmp //= j + 1
            global luckysum
            luckysum += tmp
        return
    for i in range(mi,K + 1):
        num[n] = i
        farr[i] += 1 
        LuckyNumGen(n + 1, i, fk + i,num,farr,isum,N,K)
        farr[i] -= 1

#Проверка корректности ввода
def InputCheck():
    while 1:
        tmp = input()
        try:
            tmp = int(tmp)
            break
        except ValueError:
            print ("\nВы ошиблись! Попробуйте снова.\n")
    return tmp

def main():
    t1 = time.time()
    N = 0
    K = 0
    MAXN = 100
    MAXK = 9
    MAXSUM = 1000
    num = [0 for i in range(MAXN)]
    farr = [0 for i in range(MAXK+1)]
    isum = [0 for i in range(MAXSUM)]
    while N*K > 300 or N*K == 0:
        print("Введите целые числа N и К, по условию 1<= N <=100  1<= K <=9  N*K<=300 \n")
        while (N < 1) or (N > 100):
            print("Введите целое число N 1<= N <=100: ")
            N = InputCheck()
        while (K < 1) or (K > 9):
            print ("Введите целое число K 1<= K <=9: ")
            K = InputCheck()
        if (N*K > 300):
            print("\nВы привысили диапозон. Повторите ввод\n")
            N = 0
            K = 0
    LuckyNumGen(0, 0, 0, num,farr,isum,N,K);
    comb = pow(K + 1, N)
    print("Число размещений с повторением из k по n: ", comb)
    print("Число счастливых сочетаний: ", luckysum)
    print("Число несчастливых сочетаний: ", comb - luckysum)
    print("Время выполнения программы: ", time.time() - t1)
if __name__ == "__main__": 
    main()