|
Загадка
(Время: 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);
}
| |
