Задача про продажу билетов и сдачу

Question

Помогите, я с этим примитивом уже второй день сижу.
Задача звучит так:

Продавец хочет продать билеты по 25 руб. за штуку. Первоначально у него нет денег. Сможет ли он дать сдачу каждому человеку, продавая строго в порядке очереди? Предположим, что люди в очереди могут иметь только 25, 50 и 100 рублёвые купюры. Пример:
25 25 50 (да)
25 100 (нет)
25 25 50 50 100 (нет)<

Вот код:

sum2 = 0
error = 0
i = 0
n = 0
a = [ ]
n = int(input())
while n:
    a.append(n)
    n = input()
    i+=1
j = 0
while(j!=i):
    if(a[j]==25):
        sum1+=1
    elif(a[j]==50):
        if(sum1>0):
            sum1-=1
            sum2+=1
        else:
            error+=1
            break
    else:
        if(sum1>0 and sum2>0):
            sum1-=1
            sum2-=1
        elif(sum1>2):
            sum1-=3
        else:
            error+=1
            break
    j+=1
if(error>0):
    print("Нет")
else:
    print("Да")

Answer 1

при условии, что продавец не знает изначально как ему будут платить в очереди (это важно) и платит сдачу сразу, тогда:

алгоритм такой:

собираем от покупателей купюры и раскладываем их по стопкам в зависимости от номинала
сдачу выплачиваем сначала более крупными купюрами, затем более мелкими

код:

# получить от пользователя взносы покупателей
orders = list(map(int, input().split()))

success = True

# обнулить счётчики купюр (у продавца нет сдачи)
bank = {25: 0, 50: 0, 100: 0}

for order in orders:

    # увеличить счётчик соответствующих купюр
    bank[order] += 1

    # вычислить сдачу
    change = order - 25

    # выплатить сдачу начала крупными купюрами, затем более мелкими
    while change >= 100 and bank[100] > 0:
        change -= 100
        bank[100] -= 1

    while change >= 50 and bank[50] > 0:
        change -= 50
        bank[50] -= 1

    while change >= 25 and bank[25] > 0:
        change -= 25
        bank[25] -= 1

    # если сдача после выплаты доступными купюрами не нулевая - значит выплата неудачная
    if change != 0:
        success = False
        break

# вывести результат
print("можно" if success else "нельзя")

кучу while можно заменить на более универсальный код:

# выплатить сдачу начала крупными купюрами, затем более мелкими
for banknote in sorted(list(bank.keys()), reverse=True):
    while change >= banknote and bank[banknote] > 0:
        change -= banknote
        bank[banknote] -= 1

БЛОГ НА HUSL

Задача про продажу билетов и сдачу

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