Матч 45, Решение уравнения (SolvingEquation)

Рассмотрим уравнение ax + by + cz = w, где x, y, z – неизвестные целые переменные, не меньшие 0. Необходимо найти наименьшее значение суммы x + y + z среди всех решений (x, y, z) уравнения. Если уравнение решений не имеет, вернуть -1.

Класс: SolvingEquation

Метод: int solve(int a, int b, int c, int w)

Ограничения: 1 £ a, b, c, w £ 100.

Вход. Целые числа a, b, c и w.

Выход. Наименьшее возможное значение суммы x + y + z, где (x, y, z) – решение уравнения. Если уравнение решений не имеет, вернуть -1.

Пример входа

a	b	c	w
1	2	3	5
1	2	3	10
3	3	5	7

Пример выхода

2

4

-1

РЕШЕНИЕ

перебор

Перебираем все возможные значения 1 £ i, j, k £ 100, проверяем выполнение равенства i * a + j * b + k * c = w. Среди всех троек (i, j, k), для которых имеет место равенство, в переменной res подсчитываем наименьшее значение сумм i + j + k. Если уравнение не имеет ни одного решения (i, j, k), возвращаем -1.

ПРОГРАММА

#include <stdio.h>

class SolvingEquation

{

public:

int solve(int a, int b, int c, int w)

{

int x, y, z, res = 1000;

for(x = 0; x <= 100; x++)

for(y = 0; y <= 100; y++)

for(z = 0; z <= 100; z++)

if (a*x + b*y + c*z == w)

if (x + y + z < res) res = x + y + z;

return (res == 1000) ? -1 : res;

}

};