“Олимпиадные задачи”. Сборник-5
Задача 1 “Арифметическая прогрессия” (20 баллов)
Задана последовательность натуральных чисел из диапазона [1, 2147483647]. Количество чисел в этой последовательности не превышает 100000. Необходимо определить, можно ли выстроить эти числа в отрезок арифметической прогрессии. При необходимости порядок чисел в последовательности можно изменять.
Требуется написать программу для решения этой задачи.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 5 секунд на тест
Формат входных данных:
Входной файл INPUT.TXT содержит заданную последовательность натуральных чисел. Числа в файле разделены пробелами или символами перехода на новую строку.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать либо 1 в случае положительного ответа, либо 0 в противоположном случае.
Пример файла входных данных:
80 50 10 30 70 40 20 60 90
Пример файла выходных данных (для приведенного выше входного файла):
1
—————————————————————————————————————————–
Задача 2 “Простая игра” (20 баллов)
Дед Мазай и заяц играют в очень простую игру. Перед ними огромная куча из N одинаковых морковок. Каждый из них во время своего хода может взять из этой кучи любое количество морковок, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8, . Начинает игру либо дед Мазай, либо заяц. Затем игроки ходят по очереди. Тот, кто возьмет последнюю морковку, тот и выигрывает.
Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит единственное целое положительное число N (N?10^(——–250)), задающее число морковок в начале игры.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать в первой строке цифру 1 , если выиграет тот, кто ходит первым, или цифру 2 в противном случае. Если игру выиграл тот, кто ходил первым, то во второй строке этого файла должно содержаться минимальное число морковок, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.
—————————————————————————————————————————–
Задача 3 “Коррозия металла” (20 баллов)
Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, , N) известно время его растворения жидкостью A av(i) и жидкостью B bv(i). Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа.
Требуется написать программу проектирования такой перегородки, время растворения которой было бы максимальным.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение времени: 10 секунд на тест.
Формат входных данных:
В первой строке входного файла записано число N (1PdNPd256). В каждой из последующих N строк содержатся два положительных вещественных числа av(i) и bv(i), разделенные пробелом.
Формат выходных данных:
В первую строку выходного файла записать время растворения перегородки с то чностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.
Пример файла входных данных:
4
1 2
1 2
0.5 1.5
7 3.5
Пример файла выходных данных (для приведенного выше входного файла):
6.000
4 2 1 3
—————————————————————————————————————————–
Задача 4 “Число в последовательности” (20 баллов)
Последовательность 011212201220200112 строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.
Требуется написать программу, которая по заданному натуральному числу n определяет, какое число стоит на n-ом месте.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит число n (1PdNPd2147483647).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно искомое число.
Пример файла входных данных:
10
Пример файла выходных данных (для приведенного выше входного файла):
2
—————————————————————————————————————————–
Задача 5 “Последовательности из 0 и 1” (20 баллов)
Рассмотрим последовательности длины N, состоящие из 0 и 1.
Требуется написать программу, которая по заданному натуральному числу N определяет количество тех из них, в которых никакие две единицы не стоят рядом.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит число n (1PdNPd100).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно искомое число.
Пример файла входных данных:
2
Пример файла выходных данных (для приведенного выше входного файла):
3
—————————————————————————————————————————–
Задача 6 “Функция” (20 баллов)
Функция f(n) определена следующим образом: f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1)=f(n)+f(n+1).
Требуется написать программу, которая по заданному натуральному числу N определяет значение функции f(N).
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит число N (1PdNPd2147483647).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно искомое число.
Пример файла входных данных:
2
Пример файла выходных данных (для приведенного выше входного файла):
1
—————————————————————————————————————————–
Задача 7 “Закраска прямой” (20 баллов)
Определение. Интервал прямой с целочисленными координатами [a, b) содержит левую границу точку a и не содержит правую границу точку b. Интервал от 0 до 1000000000 выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый).
Требуется написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в первой строке число N (1PdNPd500) и затем N строк с границами интервалов (числа в диапазоне от 0 до 1000000000).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число длину самого большого белого интервала.
Пример файла входных данных:
4
20 50
10 35
40 90
100 1000000000
Пример файла выходных данных (для приведенного выше входного файла):
15
—————————————————————————————————————————–
Задача 8 “Числовая последовательность” (20 баллов)
Дана последовательность натуральных чисел 7, 11, 13, 14, 19, 21, 22, 25,.
Требуется написать программу, которая по заданному N находит N-ый член этой последовательности.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 1 секунда на тест.
Формат входных данных:
Входной файл INPUT.TXT содержит число N (1PdNPd2147483647).
Формат выходных данных:
В выходной файл OUTPUT.TXT записывается N-ый член последовательности.
Пример файла входных данных:
5
Пример файла выходных данных (для приведенного выше входного файла):
19
—————————————————————————————————————————–
Задача 9 “Химическая тревога” (20 баллов)
Произошло радиоактивное заражение местности. Составлена карта зараженности. Она представляет собой прямоугольную таблицу N*M, в клетках которой записана зараженность соответствующего участка.
Требуется написать программу, которая найдет путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в первой строке числа N и M, а в следующих N строках по M чисел карта зараженности местности. Числа в строках разделяются одним пробелом. 1PdNPd30, 1PdMPd30, зараженность участка целое число от 0 до 100.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число суммарную долю радиации.
Пример файла входных данных:
3 5
2 100 0 100 100
1 100 0 0 0
1 0 3 100 2
Пример файла выходных данных (для приведенного выше входного файла):
9
—————————————————————————————————————————–
Задача 10 “Факториал” (20 баллов)
Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно – N! = 1*X2*X3*X *XN.
Требуется написать программу, которая определит каким количеством цифр ?0? заканчивается запись числа N! в K-ричной системе счисления.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение времени: 5 секунд на тест.
Формат входных данных:
Во входном файла содержится два числа: N и K (1PdNPd2*X10^(9), 2PdKPd5000). Оба числа записаны в десятичной системе счисления.
Формат выходных данных:
В выходной файл вывести количество нулей, которыми в K-ричной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.
Пример файла входных данных:
10000 10
Пример файла выходных данных (для приведенного выше входного файла):
2499
