DjangoBB LoFi version

Полная версия: Задача с acmp №317 - Подарки Деда Мороза

Начало » Python для новичков » Задача с acmp №317 - Подарки Деда Мороза

Enfoire

Май 30, 2017 18:06:27

Никак не могу сдать. Время у задачи 0.5 - у меня 0.55 - 0.6. Подскажите, как ускорить?

Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм.
Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз.

Входные данные:
четыре целых числа X, Y, Z и W (1 ≤ X, Y, Z ≤ 100, 1 ≤ W ≤ 1000)

Выходные данные:
целое число – количество вариантов подарков

 x, y, z, w = map(int, input().split())
count = 0
    
for i in range(0, w // x + 1):
    for j in range(0 , (w - (x * i)) // y + 1):
        if (w - (x * i + y * j)) % z == 0:
            count += 1
  
print(count)

FishHook

Май 30, 2017 19:03:48

Ваш алгоритм можно опимизировать, если вынести повторяющуюся математику из цикла и убрать дублирование кода

  x, y, z, w = map(int, input().split())
count = 0
    
for i in range(0, w // x + 1):
    rest = w - x * i
    for j in range(0 , rest // y + 1):
        if (rest - y * j) % z == 0:
            count += 1
  
print(count)

Enfoire

Май 30, 2017 19:21:41

FishHook
Ваш алгоритм можно опимизировать, если вынести повторяющуюся математику из цикла и убрать дублирование кода

Укажите, пожалуйста, где именно повторяющиеся моменты и дублирование?

FishHook

Май 30, 2017 19:32:11

Enfoire
Укажите, пожалуйста, где именно повторяющиеся моменты и дублирование?

 for i in range(0, w // x + 1):
    for j in range(0 , (w - (x * i)) // y + 1):  #  w - x * i
        if (w - (x * i + y * j)) % z == 0:          # w - x * i  те же самые расчеты в цикле!

собственно, я же вам дал исправленный код выше

Enfoire

Май 30, 2017 19:36:33

FishHook

Прошу прощения, глаз замылился уже. Спасибо!