Задачи районно-городского личного первенства 2003

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

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

14

2 3

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

Напишите программу, которая вводит натуральное число `N_0\ (10≤N_0<10^101)` и выводит число `N_1` – ход, который позволит выиграть первому игроку при безошибочной игре противников. Если выигрышный ход не существует, то программа должна вывести 0.

98

19

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

BAZAR

3

Напишите программу, которая вводит строку длиной от 1 до 80 символов, содержащую арифметическое выражение, и выводит его структуру "графически" в виде дерева.

Арифметическое выражение состоит из переменных (обозначаемых одной прописной латинской буквой), знаков арифметических действий (+, -, *, /), и круглых скобок. Приоритет операций * и / выше, чем у операций + и -. Все операции являются левоассоциативными, т.е. выражение A+B+C интерпретируется как (A+B)+C, а не A+(B+C). Скобки изменяют порядок вычислений. Операция смены знака не используется. Арифметическое выражение корректно и не содержит никаких других символов, кроме указанных, в том числе пробелов. При выводе структуры выражения используется схема на рисунке. Для изображения вертикальных линий используется символ '|' (вертикальная черта), а для горизонтальных – символ '_' (подчеркивание).

A+B-C*D

-
|_+
| |_A
| |_B
|_*
  |_C
  |_D