Здесь показаны различия между выбранной ревизией и текущей версией данной страницы.
подготовка_к_олимпиаде._тур_9 [2013/11/11 15:19] Пронин Роман создано |
подготовка_к_олимпиаде._тур_9 [2013/11/11 22:37] (текущий) Пронин Роман |
||
---|---|---|---|
Строка 1: | Строка 1: | ||
- | **1. Разложение** | + | **1. Разложение** (Муниципальный этап, 2011) |
- | Альберт хочет представить некоторое целое положительное число N в виде сумме квадратов двух целых положительных чисел P и Q (0 < P ≤ Q). Это не всегда возможно. Если точного разложения не существует, Альберту нужно подобрать такие P и Q, чтобы значение выражения |N−P2−Q2| было минимальным. Если существует несколько вариантов разложения, минимизирующих значение указанного выражения, то вывести вариант с меньшим Q. | + | Ограничения: время – 1s/Java 2s, память – 32MiB |
+ | |||
+ | Альберт хочет представить некоторое целое положительное число N в виде сумме квадратов двух целых положительных чисел P и Q (0 < P ≤ Q). Это не всегда возможно. Если точного разложения не существует, Альберту нужно подобрать такие P и Q, чтобы значение выражения |N−P<sup>2</sup>−Q<sup>2</sup>| было минимальным. Если существует несколько вариантов разложения, минимизирующих значение указанного выражения, то вывести вариант с меньшим Q. | ||
Напишите программу, которая вводит с клавиатуры целое число N (1 ≤ N ≤ 10<sup>6</sup>) и выводит на экран целые значения P и Q. | Напишите программу, которая вводит с клавиатуры целое число N (1 ≤ N ≤ 10<sup>6</sup>) и выводит на экран целые значения P и Q. | ||
Строка 8: | Строка 10: | ||
|14|2 3| | |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| | ||
+ | |||
+ | **3. Игра** (Муниципальный этап, 2011) | ||
+ | |||
+ | Ограничения: время – 1s/Java 2s, память – 32MiB | ||
+ | |||
+ | Двое играют в следующую игру. Сначала с помощью компьютера генерируется случайное целое число N<sub>0</sub>, состоящее из двух или более цифр. Затем игроки ходят по очереди, соблюдая следующие правила. Игрок, делающий i-ый ход, должен назвать новое число N<sub>i</sub>, строго меньшее числа N<sub>i-1</sub>, но большее или равное сумме цифр числа N<sub>i-1</sub>. Если игрок не может сделать ход по правилам, то он проигрывает. Например, пусть N<sub>0</sub>=98. Первый игрок должен назвать число от 17 до 97. Если он назовет 17, то второй игрок назовет 8 и выиграет. Если он назовет 19, то второй игрок должен будет выбрать число от 10 до 18, и какое бы число второй игрок не назвал, первый игрок сможет назвать 9 и выиграть. | ||
+ | |||
+ | Напишите программу, которая вводит натуральное число N<sub>0</sub> (10≤N<sub>0</sub><10<sup>101</sup>) и выводит число N<sub>1</sub> – ход, который позволит выиграть первому игроку при безошибочной игре противников. Если выигрышный ход не существует, то программа должна вывести 0. | ||
+ | |||
+ | ^Пример ввода^Пример вывода^ | ||
+ | |98|19| | ||
+ | |||
+ | |||
+ | **4. Водопой** (Муниципальный этап, 2011) | ||
+ | |||
+ | Ограничения: время – 1s/Java 2s, память – 32MiB | ||
+ | |||
+ | В шахматной стране кони пасутся на клеточном поле, размером NxM (2 ≤ N, M ≤ 250) На поле пасется Q (0 ≤ Q ≤ 10000) коней в различных клетках. На водопой кони собираются в одной из клеток поля, заранее известной. Кони перемещаются по полю шагами, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждого коня до водопоя определяется как количество шагов. Определить минимальное значение суммы длин путей коней до водопоя или, если собраться коням у водопоя невозможно, то сообщить об этом. Сбор невозможен, если хотя бы один из коней не может попасть к водопою. | ||
+ | |||
+ | //Входные данные:// В первой строке входного файла находится 5 чисел, разделенных пробелом: N, M, S, T, Q. | ||
+ | |||
+ | N, M – размеры поля (отсчет начинается с 1); S, T – координаты клетки - водопоя (номер строки и столбца соответственно), Q – количество коней на поле. И далее Q строк по два числа – координаты каждого коня. | ||
+ | |||
+ | //Выходные данные:// В выходной файл выводится одно число –минимальное значение суммы длин путей или –1, если сбор невозможен. | ||
+ | |||
+ | ^Пример ввода^Пример вывода^ | ||
+ | |4 4 1 1 3\\ 2 3\\ 3 2\\ 3 3 |6| | ||
+ | |5 5 3 4 0 |0| | ||
+ | |||
+ | |||
+ | **5. Анаграммы** (Муниципальный этап, 2010) | ||
+ | |||
+ | |||
+ | Ограничения: время – 1s/Java 2s, память – 32MiB | ||
+ | |||
+ | Напишите программу, которая вводит слово длиной не более 14 букв и выводит количество различных анаграмм, которые могут получиться из этого слова. Анаграммой слова называется любая перестановка всех букв слова. Например, из слова СОЛО можно получить 12 анаграмм: СОЛО, ЛОСО, ОСЛО, ОЛСО, ОСОЛ, ОЛОС, СЛОО, ЛСОО, ООЛС, ООСЛ, ЛООС, СООЛ. | ||
+ | |||
+ | ^Пример ввода^Пример вывода^ | ||
+ | |СОЛО|12| | ||