Это старая версия документа.
1. Разложение (Муниципальный этап, 2011)
Ограничения: время – 1s/Java 2s, память – 32MiB
Альберт хочет представить некоторое целое положительное число N в виде сумме квадратов двух целых положительных чисел P и Q (0 < P ≤ Q). Это не всегда возможно. Если точного разложения не существует, Альберту нужно подобрать такие P и Q, чтобы значение выражения |N−P2−Q2| было минимальным. Если существует несколько вариантов разложения, минимизирующих значение указанного выражения, то вывести вариант с меньшим Q.
Напишите программу, которая вводит с клавиатуры целое число N (1 ≤ N ≤ 106) и выводит на экран целые значения P и Q.
Пример ввода | Пример вывода |
---|---|
14 | 2 3 |
2. Cортировка (Муниципальный этап, 2011)
Ограничения: время – 1s/Java 2s, память – 32MiB
Напишите программу, которая вводит строку длиной от 1 до 25 символов, состоящую из прописных латинских букв, и выводит минимальное количество обменов, которые необходимо сделать в этой строке, чтобы отсортировать буквы строки в алфавитном порядке. Обмен – это перестановка двух букв. Например, чтобы отсортировать буквы строки BAZAR, нужно сделать 3 обмена. Сначала можно поменять местами 3-ю и 5-ю букву (BARAZ), затем 3-ю и 4-ю буквы (BAARZ), и, наконец, 1-ю и 3-ю буквы (AABRZ).
Пример ввода | Пример вывода |
---|---|
BAZAR | 3 |