Комплект заданий для проведения 1 (школьного) этапа Республиканской олимпиады по информатике

Задача 1 Клавиатура

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Пример входных и выходных данных

Краткие методические рекомендации по решению задачи

Решение данной задачи заключается в следующем. В первую очередь необходимо для каждой клавиши на клавиатуре посчитать количество нажатий на нее и проверить, больше ли оно некоторого числа. Количество нажатий клавиш можно хранить в массиве и, считывая очередное нажатие, увеличивать счетчик для данной клавиши. После считывания всех нажатий для всех клавиш следует последовательно проверить выполнение указанного в описании задачи условие.

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

Таким образом, чтобы набрать полный балл, требуется реализовать простейшее линейное решение, в котором используются лишь базовые операции с массивами.

Возможные ошибки

Можно применить "лобовое" решение, т.е. создать два или  три массива, но на самом деле нужен только один размером 100 элементов. При лобовом решении необходим массив в 100000 элементов, а создать его в Turbo Pascal не удастся. Самое интересное, что лобовое решение проходит если использовать компилятор Free Pascal. При решении задачи надо обратить внимание, что в выходной файл данные надо выводит в нижнем регистре.

Задача 2. Сумма двух чисел

Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c.

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

Входной файл содержит три целых числа: a, b, c (0 a, b, c ⁹). Числа разделены пробелом.

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

Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом.

Примеры входных и выходных файлов

Комментарии к решению задачи.

Основная идея решения данной задачи основана на переборе всех перестановок цифр числа a. Чтобы это сделать, обозначим полученное число a_perm. Теперь, для того, чтобы найти число b_perm, которое необходимо получить перестановкой цифр числа b, достаточно вычесть из числа c число a_perm. Для проверки возможности перестановки цифр числа b таким образом, чтобы получилось число b_perm, предлагается проверить на равенство мультимножества цифр указанных чисел. Это можно сделать, например, посчитав количество нулей, единиц, двоек … девяток в каждом из сравниваемых чисел.

Задача 3 «Забавный конфуз»

Тема : Алгоритмы поиска и сортировки

Банкир использовал для шифровки кодов от сейфа – следующий алгоритм:

На листике он случайным образом записивал ряд чисел А, состоящий из N элементов А1….Аn. Далее находил его максимальное и минимальное значение (max_a и min_a соответственно). После чего находил сумму элементов ряда S и заменял каждый элемент ряда на разницу суммы S и этого элемента Аi=S-Ai, 1≤N≤N. Кодом являлась разница максимального и минимального элемента в ряду, преобразованом К число раз.

Напишите программу, которая поможет банкиру быстро сгенирировать код.

Входные данные: Confuse.dat. Первая строка входного файла CONFUSE.DAT содержит целые числа N и K, где N - количество элементов в ряду чисел А (2

Выходные данные: Confuse.sol. Единственная строка выходного файла CONFUSE.SOL должна содержать целое число, которое есть разностью max_А и min_А.

{легкость решения состоит в том, что при таком изменении элементов массива, независимо от количества преобразований, разница между максимальным и минимальным элементом – остается неизменной. Решение задачи сводится к поиску максимального и минимального значения массива. Так же можно упростить задачу, считывая элементы массива из файла непосредственно}

Задача 4

Сортировка и поиск

Независимые судьи

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

Пусть n (n ≥ 3) судей выставили одному из спортсменов соответственно оценки: а₁, а₂, …, а_n. Определить, какая итоговая оценка пойдёт спортсмену в зачёт.

Во входном файле input.txt в первой строке дано количество судей n, во второй – баллы первого судьи, в третьей – баллы второго судьи и т. д., в n+1 строке – баллы n-го судьи. В выходном файле output.txt содержится одно число – итоговая оценка спортсмена.

Пример входного и выходного файлов