Массивы и векторы

Упражнения

A: Ближайшее число

Дан массив целых чисел и некоторое число. Найдите в данном массиве элемент, ближайший к заданному.

В первой строке заданы элементы массива (целые числа, не превосходящие по модулю 1000).

Во второй строке дано одно целое число \(x\), не превосходящее по модулю 1000.

Выведите значение элемента массива, ближайшее к \(x\). Если таких чисел несколько, выведите последнее из них.

Ввод Вывод
5
3 8 4 7 9
5
4
5
1 2 4 5 6
3
4
3
1 2 3
2
2

B: Шеренга

Петя перешёл в другую школу. На уроке физкультуры ему понадобилось определить своё место в строю. Помогите ему это сделать.

Программа получает на вход число N – количество человек в классе. Затем невозрастающая последовательность из N чисел, означающих рост каждого человека в строю. После этого вводится число X – рост Пети. Все числа во входных данных натуральные и не превышают 200.

Выведите номер, под которым Петя должен встать в строй. Если в строю есть люди с одинаковым ростом, таким же, как у Пети, то он должен встать после них.

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

Ввод Вывод
8
165 163 160 160 157 157 155 154
162
3
8
165 163 160 160 157 157 155 154
160
5

C: Соседи одного знака

Дан массив. Если в нем есть два соседних элемента одного знака, выведите эти числа. Если соседних элементов одного знака нет - не выводите ничего. Если таких пар соседей несколько - выведите первую пару.

Примечание. В этой задаче нужно реализовать алгоритм линейного поиска: найти такую первую пару элементов, удовлетворяющую заданному условию. Алгоритм линейного поиска пишется при помощи цикла while, а не при помощи цикла for.

Ввод Вывод
5
-1 2 3 -1 -2
2 3

D: Переставить соседние

Переставьте соседние элементы массива (A[0] c A[1], A[2] c A[3] и т.д.). Если элементов нечетное число, то последний элемент остается на своем месте.

Ввод Вывод
5
1 2 3 4 5
2 1 4 3 5

E: Циклический сдвиг вправо

Циклически сдвиньте элементы массива вправо (A[0] переходит на место A[1], A[1] на место A[2], ..., последний элемент переходит на место A[0]).

Используйте минимально возможное количество операций присваивания.

Ввод Вывод
5
1 2 3 4 5
5 1 2 3 4

F: Количество совпадающих пар

Дан массив. Посчитайте, сколько в нем пар элементов, равных друг другу. Считается, что любые два элемента, равные друг другу образуют одну пару, которую необходимо посчитать.

Ввод Вывод
5
1 2 3 2 3
2
5
1 1 1 1 1
10

G: Два ближайших

Дан массив целых чисел. Найдите в нем два ближайших элемента (то есть два элемента с минимальной абсолютной разностью).

Программа получает на вход число \(N\), в следующей строке заданы \(N\) элементов массива через пробел.

Выведите два числа: индексы двух элементов массива, абсолютная величина разности которых минимальна.

Ввод Вывод
6
7 0 4 2 5 9
2 4

H: Количество различных элементов - 2

Дан массив. Посчитайте, сколько в нем различных элементов, не изменяя самого массива.

Указание. Будем считать те элементы, которые встретились нам впервые. Чтобы проверить, встретился ли нам элемент A[i] впервые, необходимо проверить, встречается ли значение A[i] среди элементов с индексами, меньшими i. А это — линейный поиск, он пишется при помощи цикла while.

Ввод Вывод
5
3 2 1 2 3
3

I: Медиана

В массиве — нечетное число элементов, при этом все элементы различны. Найдите медиану массива: элемент, который стоял бы ровно посередине массива, если массив упорядочить.

При решении этой задачи нельзя модифицировать данный массив (в том числе и сортировать его), использовать вспомогательные массивы.

Программа получает на вход нечетное число \(N\), в следующей строке заданы \(N\) элементов массива через пробел.

Программа должна вывести единственное число — значение медианного элемента в массиве.

Ввод Вывод
7
6 1 9 2 3 4 8
4

J: Уникальные элементы

Дан массив. Выведите те его элементы, которые встречаются в массиве только один раз. Элементы нужно выводить в том порядке, в котором они встречаются в массиве.

Указание. Элемент является уникальным, если он больше нигде не встречается в массиве. Это тоже — линейный поиск.

Ввод Вывод
6
1 2 2 3 3 3
1

K: Самое частое число

Дан массив. Не изменяя массива и не заводя дополнительного массива определите, какое число в этом массиве встречается чаще всего.

Если таких чисел несколько, выведите любое из них.

Ввод Вывод
6
1 2 3 2 3 3
3

L: Числа \(k\)-боначчи

Назовем последовательность чисел последовательностью \(k\)-боначчи, если каждый элемент этой последовательности является суммой \(k\) предыдущих членов последовательности. В частности, последовательность \(2\)-боначчи является последовательностью Фибоначчи.

Более формально, \(i-й\) элемент последовательности \(k_i\) равен 1, если \(0\le i\le k - 1\) и равен сумме \(k\) предыдущих членов последовательности \(k_{i-1} + k_{i-2} + ... + k_{i-k}\) при \(i\ge k\).

Даны два числа \(k\) и \(n\) (\(k\ge 2\), \(n\ge0\)). Вычислите \(n\)-й член последовательности \(k\)-боначчи \(k_n\).

Ввод Вывод
3 6
17
100 0
1

M: Кузнечики

\(N\) кузнечиков стоят в ряд. Для каждого кузнечика задана числовая характеристика — длина его прыжка. Если длина прыжка кузнечика равна \(l\), то он за один прыжок перепрыгивает через \(l\) других кузнечиков.

Каждую секунду последний кузнечик прыгает к началу ряда, перепрыгивает через столько кузнечиков, чему равна длина его прыжка, и становится между двумя другими кузнечиками.

В первой строке входных данных содержится количество кузнечиков \(N\). Во второй строке содержатся \(N\) натуральных чисел — расстановка кузнечиков (длины их прыжков). В третьей строке входных данных задано число секунд \(t\). Опеределите и выведите на экран расстановку кузнечиков через \(t\) секунд. Все длины прыжков — натуральные числа, меньшие, чем число кузнечиков в ряду.

В этой задаче нельзя использовать методы, изменяющие количество элементов в массиве.

Ввод Вывод
5
1 2 3 4 2
2
4 1 2 2 3

N: Ферзи

Известно, что на доске 8×8 можно расставить 8 ферзей так, чтобы они не били друг друга. Вам дана расстановка 8 ферзей на доске, определите, есть ли среди них пара бьющих друг друга.

Программа получает на вход восемь пар чисел, каждое число от 1 до 8 - координаты 8 ферзей. Если ферзи не бьют друг друга, выведите слово NO, иначе выведите YES.

Ввод Вывод
1 7
2 4
3 2
4 8
5 6
6 1
7 3
8 5
NO
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
YES

O: Большой сдвиг

Дан массив из \(N\) (\(1 \le N \le 100000\)) целых чисел и число \(K\) (\(|K| < 100000 \)). Циклически сдвиньте массив на \(|K|\) элементов вправо, если \(K\) – положительное и влево, если отрицательное число.

Программа получает на вход массив из \(N\) элементов, затем число \(K\).

Решение должно иметь сложность \(O(N)\), то есть не должно зависеть от \(K\). Дополнительным массивом пользоваться нельзя (и увеличивать размер массива тоже нельзя).

Ввод Вывод
5
5 3 7 4 6
3
7 4 6 5 3

P: Сжатие массива

Массив заполнен целыми числами. Требуется “сжать” его, переместив все ненулевые элементы в левую часть массива, не меняя их порядок, а все нули  в правую часть. Порядок ненулевых элементов изменять нельзя, дополнительный массив использовать нельзя, задачу нужно выполнить за один проход по массиву. Распечатайте полученный массив.

Ввод Вывод
8
4 0 5 0 3 0 0 5
4 5 3 5 0 0 0 0