“Олимпиадные задачи”. Сборник-4
Задача 1 “Площадь треугольника” (3 уровень)
Три непараллельные прямые заданы коэффициентами a, b и c. Коэффициенты а и b
не могут быть одновременно равны нулю. Определить площадь треугольника, образованного
этими прямыми с точностью до трёх знаков после запятой.
Технические условия:
В файле “input.txt” находятся коэффициенты a, b и c для трёх прямых – по три
в каждой строке. В файл “output.txt” нужно вывести единственное число – значение
площади образованного треугольника.
—————————————————————————————————————————–
Задача 2 “Стрелки часов” (2 уровень)
Циферблат механических часов имеет 12 часовых делений и 60 минутных. Вычислить
угол между часовой и минутной стрелками часов, показывающих заданное время. Стрелки
всегда показывают точно на деления циферблата, часовая стрелка передвигается
на следующее деление через каждые 12 минут.
Технические условия:
Файл “input.txt” содержит время суток в виде hh:mm, где hh – часы, mm – минуты.
Он не содерджит пробелов и пустых строк, часты и минуты задаются двумя десятичными
знаками. Вывести в файл “output.txt” величину наименьшего угла между стрелками
часов в градусах.
—————————————————————————————————————————–
Задача 3 “Крестики-нолики” (20 баллов)
Игра в крестики-нолики ведётся на квадратном поле 3х3. Играют двое. Начинают “крестики”. Каждый из игроков, поочерёдно, ставит свой значок, крестик или нолик, на свободную клетку. Выигрывает тот, кто первым поставит три своих значка вряд по вертикали, горизонтали или диагонали.
Задаётся последовательность ходов. Определить, кто выиграл, “крестики” или “нолики”?
Техническое задание:
Последовательность ходов задаётся 9-значным числом. Цифра числа обозначает номер клетки хода, а порядковый номер цифры – номер хода.
Клетки пронумерованы, как показано на рисунке:
7 8 9 4 5 6 1 2 3 В примере приведён один из вариантов. Очевидно, что последние два хода лишние, но они нужны для девятизначности кода позиции. Написать программу, которая читает файл INPUT.TXT, содержащий одну строку – последовательность ходов и выводит в текстовый файл OUTPUT.TXT символ “X” (большая латинская буква), если выиграли “крестики”, символ “0” (цифра), если выиграли “нолики” или слово “DRAW” (ничья по-английски), если игра закончилась вничью.
Правильность кода позиции проверять не надо.
—————————————————————————————————————————–
Задача 4 “Перестановки” (20 баллов)
Даны n чисел в произвольном порядке. Вывести на экран всевозможные их перестановки.
—————————————————————————————————————————–
Задача 5 “Ёжик” (3 уровень)
План прямоугольного сада размером mxn состоит из квадратных зон. В каждой
зоне растёт по дереву. С каждого дерева любой зоны могут упасть несколько
яблок. В левом верхнем квадратике находится ёжик, который должен дойти до правого
нижнего квадратика. В саду существуют ограничения относительно способа
передвижения: ёжик может двигаться из текущего квадратика только в один из
двух соседних правый либо нижний.
Составьте программу, которая вычисляет максимальное количество яблок,
которое может собрать ёжик, передвигаясь к нужному квадратику.
Технические условия:
План сада задан таблицей apples содержащей m строк и n столбиков. Элемент
apples[i,j] таблицы указывает количество яблок, упавших с дерева в зону с
координатами i,j.
Текстовый файл “input.txt” содержит в первой строке числа m,n разделённые
пробелом. В каждой из следующих m строк содержится по n чисел apples[i,j]
разделённых пробелами.
Файл “output.txt” должен содержать одно натуральное число.
—————————————————————————————————————————–
Задача 6 “Последовательность” (2 уровень)
Дана последовательность целых чисел. Известно, что все числа в ней встреч аются четное количество раз, кроме одного, которое встречается нечетное число раз. Требуется написать программу, которая определяет это число.
Технические требования:
Ограничение по времени тестирования: по 2 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит заданную последовательность. Каждое из чисел последовательности больше -2147483649 и меньше 2147483648. В каждой строке файла записано по одному числу. Общее количество чисел в файле не превышает 500001.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденное число.
—————————————————————————————————————————–
Задача 7 “Ограда” (3 уровень)
Рабочие хотят огородить площадку для проведения строительных работ. Для этого они должны использовать K секций забора. Длина каждой секции забора не превышает 1000 метров. Необходимо определить, какую максимальную площадь можно огородить имеющимися секциями.
Технические условия:
Первая строка входного файла input.txt содержит K (K <= 100). Вторая строка содержит K целых чисел -длины имеющихся секций забора. Выходной файл output.txt должен содержать одно число – максимальную площадь, которую можно огородить (с точностью 3 знака после запятой).
—————————————————————————————————————————–
Задача 8 “Простые гири” (3 уровень)
Имеются гири с массами: 1 г, 2 г, …, N г (N<=500000). Написать программу,
распределяющую эти гири на максимально возможное количество пар так, чтобы
суммарный вес гирь в каждой паре выражался простым числом.
Технические требования:
Входной файл INPUT.TXT содержит число N. Входные данные корректны. В
выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в
выходном файле разделяются пробелами и (или) символами перевода строки.
—————————————————————————————————————————–
Задача 9 “Шахматный номер” (3 уровень)
Телефонный номер называется <<шахматным>>, если его цифры набираются на
телефонном кнопочном номеронабирателе ходом шахматного коня. Написать
программу, подсчитывающую, сколько можно набрать различных семизначных <<
шахматных>> номеров, начинающихся с заданной цифры.
Технические требования:
Входной файл INPUT.TXT содержит число N [0..9]. Выходной файл OUTPUT.TXT
должен содержать единственное число – решение задачи.
—————————————————————————————————————————–
Задача 10 “Дерево” (4 уровень)
Дерево из N вершин можно представить следующим образом: сначала все вершины нумеруются числами от 1 до N. Затем выкидывается лист с наименьшим номером и выписывается номер его предка. Такая операция повторяется до тех пор, пока не останется одна вершина. В результате получается последовательность из (n-1) числа. Требуется написать программу, которая по последовательности восстанавливает само дерево.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени: 2 секунды на тест.
Входные данные:
Во входном файле на первой строке (N-1) (2<=N<=7500) число.
Выходные данные:
Выходной файл должен содержать N строк. В i-й строке должен быть список
вершин, с которыми соединена i-я вершина в порядке возрастания.
—————————————————————————————————————————–
Задача 11 “Следующее слово” (3 уровень)
Задаётся некоторое слово, длина которого не превышает 80 символов, например GOTO. Из всех его букв составляются все возможные другие слова, может быть бессмысленные, например, GOOT, GOTO, GTOO, …, TOOG. Каждая буква входит в образованное слово ровно столько же раз, сколько раз она встречается в исходном слове.
Требуется написать программу, которая по заданному слову строит непосредственно следующее за ним по алфавиту слово в соответствии с описанным правилом.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени: 5 секунд на один тест.
Входной файл INPUT.TXT содержит одно слово, состоящее не более чем из 80 заглавных английских букв. Выходной файл OUTPUT.TXТ содержит одно слово, непосредственно следующее в алфавитном порядке за заданным, или фразу “no words”, написанную малыми английскими буквами, если нужного слова найти не удаётся.
—————————————————————————————————————————–
Задача 12 “Последовательность” (3 уровень)
Дана последовательность натуральных чисел (значение каждого числа от 1 до 1000). Последовательность может быть не отсортирована. Надо найти вариант самой большой (по количеству элементов) неубывающей последовательности, составленной из чисел этого ряда. Порядок включения чисел в неубывающую последовательность должен соответствовать порядку следования чисел в первоначальной последовательности. Иными словами, числа с большими номерам и в новой последовательности размещаются правее чисел с меньшими номерами.
Технические требования:
Файл INPUT.TXT в 1-й строке содержит количество чисел в последовательности – N (1<=N<=100). Со 2-й строки и далее указан ряд чисел, каждое число размещается на новой строке. Поиск ошибок в файле не требуется, входные данные корректны.
В файле OUTPUT.TXT помещаются выходные данные. 1-я строка содержит длину максимальной неубывающей последовательности. 2-я строка и далее – пример такой последовательности, каждое число в порядке следования размещается на новой строке.
—————————————————————————————————————————–
Задача 13 “Равные элементы” (3 уровень)
Задан целочисленный массив N*M (N – количество строк, M – столбцов, N*M<=30000). Каждая строка массива упорядочена по возрастанию. Требуется написать программу, которая находит число, встречающееся во всех строках.
Технические требования:
Ограничение по времени тестирования: по 2 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке числа N, M, разделенные пробелами. В каждой из следующих N строк записано через пробел по M чисел.
Формат выходных данных:
В выходной файл OUTPUT.TXT записывается найденное число или “NO”, если
такого числа не существует.
—————————————————————————————————————————–
Задача 14 “Произведение длинных чисел” (3 уровень)
Даны два n-значных числа, где n<=200. Вычислить их произведение.
Технические требования:
Ограничение по времени тестирования: по 5 секунд на один тест.
—————————————————————————————————————————–
Задача 15 “Длинный массив”
Составить двумерный массив размером 500*500 и присвоить каждому элементу значение “1”.
—————————————————————————————————————————–
Задача 16 “Забавный конфуз” (2 уровень)
Пусть A массив, состоящий из N элементов A1,…,AN. Обозначим его максимальное и минимальное значение как max(A) и min(A) соответственно. Вычислим сумму элементов S, S=A1+A2+…+AN. Заменим каждый элемент массива на разницу S и этого элемента: Ai:=S-Ai, 1<=i<=N. Такое преобразование массива A назовем операцией Confuse.
Напишите программу CONFUSE, которая по массиву B, полученному в результате K кратного применения операции Confuse к некоторому массиву A, вычислит разность max(A)-min(A).
Техническое условие:
Первая строка входного файла CONFUSE.DAT содержит целые числа N и K, где N количество элементов массива B (2<=N<=10000), а K – количество применений операции Confuse к начальному массиву A, 1<=K<=100. Вторая строка файла содержит N элементов массива B. Элементы массива B целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.
Единственная строка выходного файла CONFUSE.SOL должна содержать целое число, которое есть разностью max(A) и min(A).
—————————————————————————————————————————–
Задача 17 “Сапер” – 3 уровень
На прямоугольном поле размером 2 на N (N<=10000) в нижней строке случайным образом расставлено некоторое количество мин, не видимых саперу, а в верхней строке в каждой клетке написаны числа от 0 до 3, которые совпадают с количеством мин в полях нижней строки, соседних с этой клеткой (расположены слева, под ней и справа). Требуется написать программу, которая находит все возможные расположения мин.
Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число N, а во второй – числа из верхней строки, записанные через пробел.
Формат выходных данных:
В первую строку выходного файла OUTPUT.TXT вывести количество возможных расположений мин (0, если такое невозможно). В следующих строках записать по одному найденному расположению мин (1 есть мина, 0 нет, числа разделить одним пробелом).
—————————————————————————————————————————–
