Загрузка [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Подразделы

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

Дата и время

12/04/2025 13:21:46

Авторизация

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

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

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

Перебираем все варианты количества человек в первой команде A от N до 1. Для количества гномов B есть два ограничения: 1) B ; 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