Здравствуйте, уважаемые программисты. Помогите, пожалуйста, решить задачу на Python

Question

Пытаюсь решить задачу, но получается максимум на 78 баллов, а нужно довести до 100. Помогите, пожалуйста, разобраться, где в коде ошибка.

Задача

Покупатель хочет купить K товаров в определенном порядке. Рассчитайте, какую сумму денег потратит покупатель (считается, что каждый товар он будет оформлять отдельным заказом, поэтому к моменту следующей покупки на нее будет распространяться самая большая возможная скидка.

Входные данные:

Сначала вводится число N (натуральное, не превышает 10) – общее количество скидок. Затем вводится N пар чисел: величина скидки ai (натуральное, не превышает 100) и сумма, которую надо превысить чтобы получить такую скидку xi (натуральное, не превышает 100000). Далее вводится число K – количество товаров, которые хочет приобрести покупатель (натуральное, не более 100). Затем следует K чисел – цена каждого товара (натуральное, не более 1000). Гарантируется, что каждая следующая скидка дается после большей суммы, чем предыдущая, также гарантируется что величина каждой следующей скидки больше предыдущей. Гарантируется, что все цены в интернет-магазине кратны 100.

Выходные данные: Выведите единственное число – сколько денег потратит покупатель при заданном порядке покупок.

ПРИМЕР 1

Исходные данные:

Результат: 198 (обратите внимание, что скидка начисляется только после превышения суммы, поэтому после первой покупки скидка равна не 4, а 2%)

ПРИМЕР 2

Исходные данные:

Результат: 1000 (скидка начисляется только после совершения покупки)

МОЙ КОД:

n = int(input())
a, x = [0] * n, [0] * n
for i in range(n):
    a[i], x[i] = map(int, input().split())
    a[i] = 1 - (a[i] / 100)

k = int(input())

prices = [int(input()) for _ in range(k)]
s = 0
j = 0

x.append(0)
for i in range(k):
    if s > x[j]:
        s += prices[i] * a[j]
        if s > x[j + 1]:
            j += 1
    else:
        s += prices[i]
print(int(s))

Answer 1

В задаче есть одна тонкость, не знаю, нашли ли её авторы тестов, проверьте, что ли... Если считать цену со скидкой по формуле s += prices[i] * (1 - a[j] / 100), то будет ошибка на тестовом наборе

1

32 100

2

200

1000

Это связано с конечным представлением точности дробных чисел, потому что 1-32/100 вовсе не 0.68, а на самом деле 0.6799999999999999. Так что можно подобрать тест, который "сломает" вычисление.

n = int(input())
# В начало списков добавляем элементы для подсчета без скидки.
# Пишем именно скидку, а не коэффициент, смотри комментарий при подсчете
a, x = [0] * (n + 1), [0] * (n + 1)
for i in range(1, n + 1):
    a[i], x[i] = map(int, input().split())

k = int(input())

prices = [int(input()) for _ in range(k)]
s = 0
j = 0

x.append(100 * 1000 + 1)  # Добавляем сумму, которая больше максимальной
for i in range(k):
    while s > x[j + 1]:  # Чтобы пройти через несколько скидок до максимальной
       j += 1
    # Цена со скидкой, но чтобы оставаться в рамках целых чисел
    s += prices[i] - prices[i] * a[j] // 100

print(s)

БЛОГ НА HUSL

Здравствуйте, уважаемые программисты. Помогите, пожалуйста, решить задачу на Python

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