База знаний гимназии 1 им. Барсукова

Это старая версия документа.

1. Разложение (Муниципальный этап, 2011)

Ограничения: время – 1s/Java 2s, память – 32MiB

Альберт хочет представить некоторое целое положительное число N в виде сумме квадратов двух целых положительных чисел P и Q (0 < P ≤ Q). Это не всегда возможно. Если точного разложения не существует, Альберту нужно подобрать такие P и Q, чтобы значение выражения |N−P²−Q²| было минимальным. Если существует несколько вариантов разложения, минимизирующих значение указанного выражения, то вывести вариант с меньшим Q.

Напишите программу, которая вводит с клавиатуры целое число N (1 ≤ N ≤ 10⁶) и выводит на экран целые значения P и Q.