10344. 23 из 5
Можно ли так расставить 5 заданных
чисел и знаки арифметических операций (+, -, *), чтобы получилось выражение,
значение которого равно 23? Считать, что все три указанные операции имеют
одинаковый приоритет и выполняются последовательно слева направо.
Вход. Каждая строка содержит пять натуральных чисел от 1 до 50.
Последняя строка содержит пять нулей и не обрабатывается.
Выход. Для каждого
теста вывести в отдельной строке слово ‘Possible’, если можно так расставить
числа и знаки указанных арифметических операций, чтобы получилось выражение со
значением 23. Если этого сделать не возможно, то вывести ‘Impossible’.
|
Пример
входа |
Пример
выхода |
|
1 1 1 1 1 1 2 3 4 5 2 3 5 7 11 0 0 0 0 0 |
Impossible Possible Possible |
комбинаторика – перебор вариантов
Генерируем все
перестановки входных чисел. Для каждой перестановки между числами расставляем
все возможные знаки арифметических операций и вычисляем полученные выражения.
Если хотя бы одно выражение имеет значение 23, то устанавливаем переменную -
флаг Found в 1 и заканчиваем
обработку текущего теста.
Входную пятерку
чисел храним в целочисленном массиве a. Переменная Found принимает значение 1, если найдено выражение со значением 23,
иначе Found = 0.
int a[5], Found;
Функция RunSum
вычисляет значение выражения, операнды которого находятся в массиве a. Между
операндами вставляются знаки всевозможных операций и вычисляются полученные
выражения при помощи техники бектрекинга. Если значение одного из выражений
равно 23, то функция возвращает 1, иначе 0.
int RunSum(int
Sum, int index)
{
if (index ==
5)
if (Sum ==
23) return 1; else
return 0;
if
(RunSum(Sum+a[index],index+1)) return 1;
if
(RunSum(Sum-a[index],index+1)) return 1;
if
(RunSum(Sum*a[index],index+1)) return 1;
return 0;
}
Основной цикл
программы. Читаем пятерку чисел в массив a. Запускаем процедуру генерации всех
перестановок. Поскольку функция next_permutation генерирует перестановки в
лексикографическом порядке, то первой должна быть наименьшая перестановка.
Наименьшей будет перестановка, у которой числа образуют неубывающую
последовательность. То есть перед генерацией перестановок числа в массиве а
следует отсортировать по неубыванию (если этого не сделать, то могут быть
рассмотрены не все перестановки).
while(scanf("%d %d %d %d %d",
&a[0],&a[1],&a[2],&a[3],&a[4]),a[0]+a[1]+a[2]+a[3]+a[4])
{
sort(a,a+5); Found = 0;
do{
Для каждой
перестановки запускаем функцию RunSum, которая выясняет, можно ли между числами
этой перестановки расставить знаки операций так, чтобы получить значение 23.
if (Found =
RunSum(a[0],1)) break;
} while(next_permutation(a,a+5));
Если переменная Found установилась в 1, то выводим
‘Possible’, иначе ‘Impossible’.
if (Found)
printf("Possible\n"); else printf("Impossible\n");
memset(a,0,sizeof(a));
}