Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Загадка

(Время: 1 сек. Память: 16 Мб Сложность: 18%)

Эту задачу можно решить, составив систему из двух уравнений и двух неизвестных:

X+Y=S
X*Y=P

Выразив Х из первого уравнения и подставив во второе мы получим квадратное уравнение, из которого получим Х, а значит и Y. Но это решение не самое быстрое для реализации. Здесь можно использовать то, что компьютер способен выполнять миллионы простых операций в секунду. Поэтому можно реализовать полный перебор всех вариантов значений X и Y (очевидно, всевозможных значений получится не более миллиона). Причем, для удобства можно сразу положить что X<=Y. Таким образом, мы сократим перебор вариантов вдвое и сможем найти однозначное решение, которое без проблем возможно вывести в порядке неубывания. Следующий алгоритм реализует вышеописанные рассуждения:

read(s,p);
for x=1..1000{
  for y=x..1000{
    if(x+y==s и x*y==p) write(x,' ',y);
  }
}

Полезно уметь оценивать временную сложность задачи. Несмотря на то, что ЭВМ способна на многое, далеко не любая задача в случае неэффективного ее решения сможет уложиться в требуемые временные ограничения. Например, если бы дипазон чисел Х и Y был в диапазоне до 30000, то такое решение с полным перебором привело бы к провалу, т.к. в этом случае возможно потребовалось бы выполнение порядка миллиарда операций, что вполне сомнительно для ограничений в 1 секунду. Но и в этом случае перебор был бы возможен. Действительно, когда значение X определено, то не обязательно перебирать всевозможные значения Y, т.к. Y=S-X. Поэтому более короткий и быстрый алгоритм решения этой задачи может выглядеть следующим образом:

read(s,p);
for x=1..30000{
  y=s-x;
  if(x<=y и x*y==p) write(x,' ',y);
}

[Обсуждение] [Все попытки] [Задача]


Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru