“Олимпиадные задачи”. Сборник-3
Задача 1 “Уравнение для 5 класса” (20 баллов)
Уравнение для пятиклассников представляет собой строку длиной 5 символов.
Второй символ строки является либо знаком ‘+’ (плюс) либо ‘-‘ (минус), четвёртый символ – знак ‘=’ (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один – буквой x,обозначающей неизвестное.
Требуется написать программу, которая решить данное уравнение относительно x.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение времени: 1 секунда на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой записано уравнение.
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести единственное целое число – значение x.
—————————————————————————————————————————–
Задача 2 “Счастливый билет” (20 баллов)
Билет называется счастливым, если его можно разрезать прямой линией на две части таким
образом, что оказавшиеся на них числа имеют одинаковые цифровые корни. Чтобы вычислить
цифровой корень числа, его цифры складывают, если в результате получится число большее или
равное 10, то цифры складывают снова и так далее, пока не получится число от 0 до 9 – это и
есть цифровой корень. Например, билет с номером 0015420 является счастливым, так как разрезав
его на части с числами 0015 и 420 имеем у этих чисел одинаковые цифровые корни.
Требуется написать программу, которая определит является ли счастливым билет с заданным номером.
Технические требования:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит номер счастливого билета. Номер
может начитаться с нулей и содержит не более 100 цифр.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать 1, если билет счастливый и 0 иначе.
—————————————————————————————————————————–
Задача 3 “Наибольшее произведение” (20 баллов)
Дана последовательность из N целых чисел.
Требуется написать программу, которая найдет из них три такие числа, произведение которых максимально.
Технические требования:
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в начале число N – количество чисел в
последовательности (3PdNPd1000000). Далее записана сама
последовательность: N целых чисел, по модулю не превышающих 30000.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать три искомых числа в любом порядке. Если
существует несколько различных троек чисел, дающих максимальное произведение, то вывести любую
из них.
—————————————————————————————————————————–
Задача 4 “А у магазина” (20 баллов)
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении.
Требуется написать программу, которая определит сколькими способами А может попасть в магазин,
пройдя ровно k шагов.
Технические требования:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в числа n и k, записанные через пробел. Известно,
что 1 Pd n Pd k Pd 37.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать одно число – количество способов попадания
в магазин.
—————————————————————————————————————————–
Задача 5 “Разложение числа” (20 баллов)
Любое натуральное число можно представить в виде суммы нескольких
последовательных натуральных чисел. Например, число 25 можно представить в виде суммы из
одного (25), двух (12+13) или пяти (3+4+5+6+7) чисел.
Требуется написать программу, которая определит максимальное количество чисел в таком
разложении. Технические требования:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит одно натуральное число n
(1 Pd n Pd 1000000000).
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать одно натуральное число – максимальное
количество чисел в разложении числа n на сумму
последовательных натуральных чисел.
—————————————————————————————————————————–
Задача 6 “Последовательность” (20 баллов)
Рассмотрим числовую последовательность, первоначально состоящую из двух
единиц: 1, 1. Далее на каждом последующем шаге будем вставлять между
соседними элементами их сумму. В примере добавляемые элементы выделены.
Требуется написать программу, которая подсчитает сумму членов
последовательности, построенной за K шагов.
Технические требования:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит одно натуральное число K
(0 Pd K Pd 100) – номер последнего шага.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать одно натуральное число – сумму элементов
последовательности, построенной за K шагов.
—————————————————————————————————————————–
Задача 7 “Земельный комитет” (20 баллов)
Земельный комитет города принял решение о сдаче в аренду части муниципальной территории, имеющей форму прямоугольника размером H на W километров. Стоимость аренды каждого квадратного участка 1 ‘ 1 км была определена с учётом локальных условий, и занесена в таблицу.
С целью организации открытого тендера на аренду, земельный комитет решил выставить на своём вебсайте карту территории, и предоставить посетителям возможность узнавать суммарную стоимость аренды для произвольной прямоугольной группы соседних участков.
Данное предложение вызвало большой интерес у населения и предпринимателей, и нагрузка на
сервер очень высока.
Требуется написать программу, позволяющую как можно более эффективно рассчитывать стоимость
аренды для N запросов. В каждом запросе требуется
определить общую стоимость участков внутри прямоугольной группы с
противоположными углами, расположенными в элементах таблицы (av(i), bv(i)) и (cv(i), dv(i))..
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Формат входных данных:
В первой строке входного файла находятся числа H, W, N (1 Pd H, W Pd 100,
1 Pd N Pd 1000000). В следующих H строках содержится по W чисел (стоимости участков находятся
в диапазоне от 0 до 10000). Далее идут N строк с числами av(i) bv(i) cv(i) dv(i) (1 Pd av(i)
Pd cv(i) Pd H, 1 Pd bv(i) Pd dv(i) Pd W).
Формат выходных данных:
Выходной файл должен содержать N чисел, по одному числу в строке.
—————————————————————————————————————————–
Задача 8 “Наилучший делитель” (20 баллов)
Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше 111, так как у них равны суммы цифр, но первое из них меньше.
Требуется найти такой делитель заданного числа, который лучше любого другого делителя.
Само число и единица считаются делителями числа.
Технические требования:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит заданное число N (1PdNPd100000).
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать наилучший делитель числа N.
—————————————————————————————————————————–
Задача 9 “Счастливая страница” (20 баллов)
В новом выпуске Большой Галактической Энциклопедии N страниц. Петя считает страницу счастливой, если произведение цифр, входящих в ее номер, равно K. Например, если N=100, то для K=42 есть счастливая страница (например, с номером 76), а для K=128 счастливой страницы нет.
Требуется написать программу, которая поможет Пете определить, есть ли счастливые страницы в
новом выпуске энциклопедии.
Технические требования:
Входной файл: INPUT.TXT,
Выходной файл: OUTPUT.TXT,
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит числа N (1PdNPd10^(9))и K
(1PdKPd10^(9)), записанные через пробел.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать 1, если счастливые страницы есть, и 0
иначе.
—————————————————————————————————————————–
Задача 10 “Ферзи” (3 уровень)
Рассмотрим шахматное поле n x n, на котором размещены n ферзей. Расположение ферзей называется допустимым, если они не атакуют друг друга. Написать программу построения всех полных допустимых расположений N ферзей, где 4<=N>=20.
Технические условия:
В файле “input.txt” содержиться единственное число – n из интервала [4..20]. Программа должна выводить в файл “output.txt” для каждого допустимого расположения ферзей ряд из n натуральных чисел, где порядковый номер каждого числа указывает на номер вертикали, а значение – на номер горизонтали в шахматном поле.
Примеры файлов:
Input.txt
4
Output.txt
2 4 1 3
3 1 4 2
Input.txt
5
Output.txt
1 3 5 2 4
1 4 2 5 3
2 4 1 3 5
2 5 3 1 4
3 1 4 2 5
3 5 2 4 1
4 1 3 5 2
4 2 5 3 1
5 2 4 1 3
5 3 1 4 2
—————————————————————————————————————————–
