Разбор задачи D. Соревнования
Тема: полный перебор
Сложность: ниже среднего
Перебираем все варианты количества человек в первой команде
A от
N до 1. Для количества гномов
B есть два ограничения: 1)
B ; 2)
B*A\ ≤\ N, т.е.
B\ ≤\ N/A. Поэтому нужно рассматривать варианты количества гномов в диапазоне от
min(A,N/A) до 1

. Количество троллей
C для выбранных
A и
B определяется однозначно из формулы
A*B\ +\ A*C\ +\ B*C\ =\ N:
C\ =\ (N\ -\ A*B)/(A+B), при этом 1)
C должно быть целым числом и 2)
C\ ≤\ B.
Оценка времени работы алгоритмы равна
O(N*sqrt(N)).
var a,b,c,bn,n:longint;
begin
read(n);
for a:=n downto 1 do
begin
bn:=n div a;
if bn>a then bn:=a;
for b:=bn downto 1 do
begin
c:=(n-b*a) div (a+b);
if (c<=b) and (a*b+b*c+a*c=n) then
writeln(a,' ',b,' ',c);
end;
end;
end.