Подразделы

Другие разделы

Дата и время

29/03/2024 17:31:19

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи D. Соревнования

Тема: полный перебор
Сложность: ниже среднего

Перебираем все варианты количества человек в первой команде `A` от `N` до 1. Для количества гномов `B` есть два ограничения: 1) `B\ ≤\ A`; 2) `B*A\ ≤\ N`, т.е. `B\ ≤\ N/A`. Поэтому нужно рассматривать варианты количества гномов в диапазоне от `min(A,N/A)` до 1smilies/remark.gif. Количество троллей `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.
loading