Задания для олимпиады по информатике

Задания для олимпиады по информатике

для студентов 1 курса ВолгГТУ (мах 100 баллов)

№	Задание	Баллы
	Последовательность Фибоначчи Fn задается следующим образом: F0=1 F1=1 Fn=Fn-1+Fn-2. Начало ряда Фибоначчи выглядит так: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Программа должна по данному n, 0≤n≤40 вычиcлить Fn.
	Дано множество из некоторого количества элементов. Построить все возможные перестановки его элементов.
	Задан массив, состоящий из n неотрицательных чисел. Найдите в нем индекс элемента, для которого сумма элементов, стоящих до него, наименее отличается от суммы элементов, стоящих после него. Формат входных данных Программа получает на вход N – число элементов в массиве; значения элементов массива. Формат выходных данных Программа должна вывести индекс искомого элемента.
	Сжать массив, удалив из него все элементы, величина которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями. Формат входных данных Вводится размер массива Вводятся элементы массива Вводится интервал для удаления элементов Формат выходных данных Программа должна вывести измененный массив.
	Изменить последовательность столбцов матрицы так, чтобы элементы их первой строки были отсортированы по возрастанию. Формат входных данных Ввод N, M –размеров матрицы Ввод элементов матрицы Формат выходных данных Вывод измененной матрицы
	Дана матрица A размером NxN, заполненная неотрицательными целыми числами. Расстояние между двумя элементами Ai j и Ap q определено как \|i - p\| + \|j - q\|. Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен. Ограничения: 1 <= N <= 200, 0 <= Ai j <= 1 000 000. Формат входных данных В первой строке содержится число N. Затем идут N строк по N чисел, разделённых пробелами и представляющих собой матрицу. Формат выходных данных Выводится N строк по N чисел, разделённых пробелами, - модифицированная матрица.
	В прямоугольной таблице nxm (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути). Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол. Формат входных данных Во входных данных задано два числа n и m - размеры таблицы (1?n?20, 1?m?20). Затем идет n строк по m чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (числа от 0 до 100). Формат выходных данных В выходные данные запишите минимальную сумму, потратив которую можно попасть в правый нижний угол.
	По некоторому каналу связи передается сообщение, состоящее из 0 и 1. Из-за помех возможны ошибки при передаче сигнала. Поэтому было решено передавать каждый сигнал трижды, теперь вместо 1 передается 111, а вместо 0 - 000. При передаче данных все равно случаются помехи, поэтому при расшифровке сообщения берут тот символ, который встречается в группе из 3-х символов чаще. Примечание. Исходные данные записаны в массив, длина которого кратна 3. Расшифрованный текст записать в другой массив.
	Задан массив натуральных чисел, причем элементы массива могут принимать значения 1 до 10000 и некоторые из них могут совпадать. Требуется написать программу, которая упорядочивает массив по возрастанию, используя лишь два оператора: цикл с параметром и оператор присваивания. Примечание. При сортировке нельзя использовать операции сравнения и условные операторы, но можно использовать дополнительный массив.
	Петя и Ваня играют в очень простую игру. Перед ними куча из N камней. Каждый из них во время своего хода может взять из этой кучи любое количество камней, равное неотрицательной степени числа 2, т.е. 1, 2, 4, 8,… . Начинает игру либо Петя, либо Ваня. Затем игроки ходят по очереди. Тот, кто возьмет последний камень, тот и выигрывает. Требуется написать программу, которая при заданных исходных данных определяет победителя в этой игре. При этом следует учитывать, что игроки играют оптимально. Примечание. При выводе результатов указать цифру «1», если выиграет тот, кто ходит первым, или цифру «2» – в противном случае. Если игру выиграл тот, кто ходил первым, также указать минимальное число камней, которое должен взять игрок, выполнявший ход первым, чтобы гарантировать свою победу.