004. Подарки Деда Мороза

(Время - 1 сек., память - 16 Мб)

Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм

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

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

В единственной строке входного файла input.txt содержатся четыре числа X, Y, Z и W (1  X, Y,  100, 1  W  1000).

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

В единственную строку выходного файла output.txt нужно вывести одно целое число – количество вариантов подарков.

Пример

input.txt

output.txt

1

10 25 15 40

3

Примечание

В приведенном примере следующие варианты: 4 ириски, 1 мандарин и 1 пряник, 1 ириска и 2 пряника.

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 2-й тур

Тематика

Перебор

Примерная сложность

27%

Ссылки в Интернете

Условие, сдача решения – http://acmu.ru/index.asp?main=task&id_task=317

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  А.В. Алексеев, 25.04.2012

 

Разбор

Математически задача сводится к нахождению количества неотрицательных решений (a, b, c) уравнения a*x+b*y+c*z=w. Если организовать тройной цикл и проверять выполнение уравнения, то, например, при x=y=z=1 и w=1000 понадобится 109 проверок. Организуем двойной цикл, например, по переменным a и b и будем проверять разрешимость уравнения относительно c.

Программа на Паскале

{Автор программы - А.В.Алексеев,  дата написания - 25.04.2012}

var

  x, y, z, w, a, b, v : integer;

  k : longint;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(x,y,z,w);

  k:=0;

  for a:=0 to w div x do

    for b:=0 to w div y do

    begin

      v:=w-a*x-b*y;

      if (v>=0) and (v mod z=0) then k:=k+1

    end;

  write(k)

end.

Программа на С