Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

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);
}

[Все попытки] [Задача]


 
     
Югорский НИИ ИТ, Югорский ФМЛ