Тексты задач для тренировочных интернет-туров по информатике для размещения на сайте school-collection. edu. ru (стр. 1 )

Тексты задач для тренировочных интернет-туров по информатике
для размещения на сайте school-collection. edu. ru

Москва 2014

1.  Описание заданий для первого интернет-тура

На первом туре было предложено 4 задачи: задача A «Гармонические тройки», задача B «Матрица», задача C «Мин и Макс» и задача D «Точки красные и синие». Тексты задач тура представлены ниже.

Задача A. Гармонические тройки

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Тройка чисел (a, b, с) называется гармонической, если выполнено одно из следующих условий:

•  НОД(a, b) = 1, НОД(a, c) = 1, НОД(b, c) = 1.

•  НОД(a, b) > 1, НОД(a, c) > 1, НОД(b, c) > 1.

Здесь под НОД(a, b) подразумевается наибольший общий делитель чисел а и b.

Например, тройка (2,3,4) не является гармонической, а тройки (3,4,5) и (6,8,10) – являются.

Напишите программу, которая вычисляет количество гармонических троек (а,b,с), для которых 1≤a<b<c≤N.

Формат входных данных

Единственная строка ввода содержит целое число N (1 ≤ N ≤ 500 000).

Формат выходных данных

Необходимо вывести целое число, равное искомому количеству гармонических троек.

Подзадача 1

Дополнительные упрощения: N ≤ 500.

Решение оценивается в 25 баллов.

Подзадача 2

Дополнительные упрощения: N ≤ 5 000.

Решение оценивается в 25 баллов.

Подзадача 3

Дополнительные упрощения отсутствуют.

Решение оценивается в 50 баллов.

Пример

Задача B. Матрица

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Отображение результатов: полное

Матрица — это прямоугольная таблица символов. Квадратной матрицей называется матрица с равным количеством строк и столбцов. Квадратная матрица называется симметричной, если её символы симметричны относительно главной диагонали (то есть Mij = Mji для любых i и j).

По данному множеству используемых символов вам необходимо вывести подмножество столбцов минимальной лексикографически симметричной матрицы, которая может быть сформирована, используя все данные символы. Если такой матрицы не существует, то необходимо вывести «IMPOSSIBLE».

Чтобы определить, какая матрица лексикографически меньше, необходимо сравнить их элементы в порядке возрастания номеров рядов (как если бы вы их сравнивали конкатенации их рядов). Меньше та матрица, у которой первый элемент, где нашлось отличие, меньше.

Формат входных данных

На первой строке стандартного ввода будут заданы числа N и К (1 ≤ N ≤ 30 000, 1 ≤ К ≤ 26) — соответственно, размер матрицы и количество различных букв, которые встречаются. Далее каждая из К строк содержит заглавную латинскую букву и целое положительное число, разделённые пробелом. Число означает, сколько раз эта буква должна быть использована. Например, если сказано «A 3», это означает, что буква А должна появиться в матрице ровно три раза. Общее количество букв будет ровно N2. Ни одна буква не появится во входном файле дважды.

Следующая строка содержит целое число Р (1 ≤ Р ≤ 50) – количество столбцов, которые необходимо вывести. В следующей строке даны сами номера столбцов. Они находятся между 1 и N включительно, заданы в возрастающем порядке и без повторений.

Формат выходных данных

Если возможно построить симметричную матрицу из заданного набора букв, то необходимо вывести требуемые столбцы на N строках по Р символов без пробелов. Иначе необходимо вывести слово «IMPOSSIBLE» (без кавычек).

Примеры

Система оценки

Тесты, в которых N не будет превышать 300, будут оценены исходя из 60 баллов. Тесты, в которых N не будет превышать 3000, будут оценены исходя из 80 баллов.

Задача C. Мин и Макс

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Отображение результатов: полное

Два котёнка, Мин и Макс, записали на листе бумаги последовательность целых чисел и начали играть в следующую игру. Каждым ходом котёнок может взять два соседних числа и оставить из них либо минимальное, либо максимальное. Ходы делаются по очереди. Игра продолжается до тех пор, пока не останется ровно одно число. Котёнок Мин хочет добиться, чтобы это число было минимально возможным, котёнок Макс – чтобы это число было максимально возможным.

Считая, что оба котёнка достаточно умны и действуют оптимально, требуется написать программу, которая выводит число, оставшееся на листе бумаги.

Формат входных данных

В первой строке ввода находится одно целое число п — количество чисел, записанных котятами (1 ≤ п ≤ 5·107). Во второй строке находится имя котёнка, который ходит первым: «Min», если первым ходит котёнок Мин, и «Max», если первым ходит котёнок Макс. Так как последовательность может быть очень длинной, вам даны числа 0 ≤ с1, а, b < 232, а каждый элемент последовательности получается из предыдущего по формуле ci = (ci·a+b) mod 232.

Формат выходных данных

Необходимо вывести единственное число — то, которое останется на листе бумаги в конце игры.

Примеры

Задача D. Точки красные и синие

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 10 секунд

Ограничение по памяти: 256 мебибайт

На плоскости нарисовано N красных и N синих точек. Никакие три точки не лежат на одной прямой. Необходимо соединить их отрезками по следующим правилам:

•  каждая красная точка соединена отрезком ровно с одной синей;

•  каждая синяя точка соединена отрезком ровно с одной красной;

•  никакие два отрезка не пересекаются.

Если существует несколько решений, достаточно найти любое из них.

Требуется написать программу, позволяющую решить поставленную задачу.

Формат входных данных

В первой строке входных данных записано число N (1 ≤ N ≤ 100 000) — количество точек каждого из цветов. Каждая из следующих N строк содержит два целых числа хиу(1 ≤х, у ≤ 1 000 000) — координаты одной красной точки. Далее следует ещё N строк, в каждой из которых записано два целых числа х и у (1 ≤ х, у ≤ 1 000 000) — координаты одной синей точки.

Формат выходных данных

Необходимо вывести N различных целых чисел от 1 до N, по одному числу в строке. Число в i-й строке — это номер синей точки, с которой необходимо соединить отрезком
i-ю красную точку. Точки каждого цвета нумеруются от 1 до N в том порядке, в котором они заданы во вводных данных.

Подзадача 1

Ограничения: N ≤ 10.

Решение этой подзадачи оценивается в 10 баллов.

Подзадача 2

Ограничения: N ≤ 100.

Решение этой подзадачи оценивается в 15 баллов.

Подзадача 3

Ограничения: N ≤ 1 000.

Решение этой подзадачи оценивается в 20 баллов.

Подзадача 4

Ограничения: N ≤ 10 000.

Решение этой подзадачи оценивается в 25 баллов.

Подзадача 5

Ограничения: N ≤ 100 000.

Решение этой подзадачи оценивается в 30 баллов.

Пример

2.  Описание заданий для второго интернет-тура

На втором туре было предложено 4 задачи: задача A «Функция Аккермана», задача B «Как разрушить свой мозг», задача C «Снег» и задача D «Сумма не без разнообразия». Тексты задач тура представлены ниже.

Задача A. Функция Аккермана

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мебибайт

Функция Аккермана хорошо известна всем специалистам в области вычислений. Это функция двух положительных аргументов, определенная следующим образом:

Это функция, не является примитивно рекурсивной, более того, A(i, i) растет быстрее, чем любая примитивно рекурсивная функция. В этой задаче, необходимо посчитать

для данного t и нескольких пар n и m. Запись “х mod у” означает остаток от целочисленного деления х на у — такое r, что 0 ≤ r < у и существует целое q, такое что х = qy + r.

Формат входных данных

В первой строке дано число t (1 ≤ t ≤ 100).