База знаний гимназии 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.

2. Cортировка (Муниципальный этап, 2011)

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

Напишите программу, которая вводит строку длиной от 1 до 25 символов, состоящую из прописных латинских букв, и выводит минимальное количество обменов, которые необходимо сделать в этой строке, чтобы отсортировать буквы строки в алфавитном порядке. Обмен – это перестановка двух букв. Например, чтобы отсортировать буквы строки BAZAR, нужно сделать 3 обмена. Сначала можно поменять местами 3-ю и 5-ю букву (BARAZ), затем 3-ю и 4-ю буквы (BAARZ), и, наконец, 1-ю и 3-ю буквы (AABRZ).

3. Игра (Муниципальный этап, 2011)

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

Двое играют в следующую игру. Сначала с помощью компьютера генерируется случайное целое число N₀, состоящее из двух или более цифр. Затем игроки ходят по очереди, соблюдая следующие правила. Игрок, делающий i-ый ход, должен назвать новое число N_i, строго меньшее числа N_i-1, но большее или равное сумме цифр числа N_i-1. Если игрок не может сделать ход по правилам, то он проигрывает. Например, пусть N₀=98. Первый игрок должен назвать число от 17 до 97. Если он назовет 17, то второй игрок назовет 8 и выиграет. Если он назовет 19, то второй игрок должен будет выбрать число от 10 до 18, и какое бы число второй игрок не назвал, первый игрок сможет назвать 9 и выиграть.

Напишите программу, которая вводит натуральное число N₀ (10≤N₀<10¹⁰¹) и выводит число N₁ – ход, который позволит выиграть первому игроку при безошибочной игре противников. Если выигрышный ход не существует, то программа должна вывести 0.