Списки

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

Раньше мы сталкивались с задачей обработки элементов последовательности, например, вычисляя наибольший элемент последовательности. Но при этом мы не сохраняли всю последовательность в памяти компьютера, однако, во многих задачах нужно именно сохранять всю последовательность, например, если бы нам требовалось вывести все элементы последовательности в возрастающем порядке (“отсортировать последовательность”).

Для хранения таких данных можно использовать структуру данных, называемую в Питоне список (в большинстве же языков программирования используется другой термин “массив”). Список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, список можно задать так:

Primes = [2, 3, 5, 7, 11, 13]
Rainbow = ['Red', 'Orange', 'Yellow', 'Green', 'Blue', 'Indigo', 'Violet']

В списке Primes — 6 элементов, а именно, Primes[0] == 2, Primes[1] == 3, Primes[2] == 5, Primes[3] == 7, Primes[4] == 11, Primes[5] == 13. Список Rainbow состоит из 7 элементов, каждый из которых является строкой.

Также как и символы строки, элементы списка можно индексировать отрицательными числами с конца, например, Primes[-1] == 13, Primes[-6] == 2.

Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len, например, len(A) == 6.

Рассмотрим несколько способов создания и считывания списков. Прежде всего можно создать пустой список (не содержащий элементов, длины 0), в конец списка можно добавлять элементы при помощи метода append. Например, если программа получает на вход количество элементов в списке n, а потом n элементов списка по одному в отдельной строке, то организовать считывание списка можно так:

A = []
for i in range(int(input())):
    A.append(int(input()))

В этом примере создается пустой список, далее считывается количество элементов в списке, затем по одному считываются элементы списка и добавляются в его конец.

Для списков целиком определены следующие операции: конкатенация списков (добавление одного списка в конец другого) и повторение списков (умножение списка на число). Например:

A = [1, 2, 3]
B = [4, 5]
C = A + B
D = B * 3

В результате список C будет равен [1, 2, 3, 4, 5], а список D будет равен [4, 5, 4, 5, 4, 5]. Это позволяет по-другому организовать процесс считывания списков: сначала считать размер списка и создать список из нужного числа элементов, затем организовать цикл по переменной i начиная с числа 0 и внутри цикла считывается i-й элемент списка:

A = [0] * int(input())
for i in range(len(A)):
    A[i] = int(input())

Вывести элементы списка A можно одной инструкцией print(A), при этом будут выведены квадратные скобки вокруг элементов списка и запятые между элементами списка. Такой вывод неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному элементу в строке. Приведем два примера, также отличающиеся организацией цикла:

for i in range(len(A)):
    print(A[i])

Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.

for elem in A:
    print(elem, end = ' ')

В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в цикле меняется не индекс элемента списка, а само значение переменной (например, в цикле for elem in ['red', 'green', 'blue'] переменная elem будет последовательно принимать значения 'red', 'green', 'blue'.

Методы `split` и `join`

Элементы списка могут вводиться по одному в строке, в этом случае строку можно считать функцией input(). После этого можно использовать метод строки split, возвращающий список строк, разрезав исходную строку на части по пробелам. Пример:

A = input().split()

Если при запуске этой программы ввести строку 1 2 3, то список A будет равен ['1', '2', '3']. Обратите внимание, что список будет состоять из строк, а не из чисел. Если хочется получить список именно из чисел, то можно затем элементы списка по одному преобразовать в числа:

for i in range(len(A)):
    A[i] = int(A[i])

Используя функции языка map и list то же самое можно сделать в одну строку:

A = list(map(int, input().split()))

Объяснений, как работает этот код, пока не будет. Если нужно считать список действительных чисел, то нужно заменить тип int на тип float.

У метода split есть необязательный параметр, который определяет, какая строка будет использоваться в качестве разделителя между элементами списка. Например, метод split('.') вернет список, полученный разрезанием исходной строки по символам '.'.

Используя “обратные” методы можно вывести список при помощи однострочной команды. Для этого используется метод строки join. У этого метода один параметр: список строк. В результате получается строка, полученная соединением элементов списка (которые переданы в качестве параметра) в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Например программа

A = ['red', 'green', 'blue']
print(' '.join(A))
print(''.join(A))
print('***'.join(A))

выведет строки 'red green blue', redgreenblue и red***green***blue.

Если же список состоит из чисел, то придется использовать еще и функцию map. То есть вывести элементы списка чисел, разделяя их пробелами, можно так:

print(' '.join(map(str, A)))

Упражнения

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

A: Четные индексы

Выведите все элементы списка с четными индексами (то есть A[0], A[2], A[4], ...).

Программа должна быть эффективной и не выполнять лишних действий!

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

B: Четные элементы

Выведите все четные элементы списка.

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

C: Количество положительных

Найдите количество положительных элементов в данном списке.

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

D: Больше предыдущего

Дан список чисел. Выведите все элементы списка, которые больше предыдущего элемента.

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

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

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

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

F: Больше своих соседей

Дан список чисел. Определите, сколько в этом списке элементов, которые больше двух своих соседей и выведите количество таких элементов.

Ввод	Вывод
1 0 1 0 1	1

G: Наибольший элемент

Дан список чисел. Выведите значение наибольшего элемента в списке, а затем индекс этого элемента в списке. Если наибольших элементов несколько, выведите индекс первого из них.

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

H: Наименьший положительный

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

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

I: Наименьший нечетный

Выведите значение наименьшего нечетного элемента списка, а если в списке нет нечетных элементов - выведите число 0.

Ввод	Вывод
0 1 2 3 4	1
2 4 6 8 10	0

J: Шеренга

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

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

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

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

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

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

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

L: Вывести в обратном порядке

Выведите элементы данного списка в обратном порядке, не изменяя сам список.

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

M: Переставить в обратном порядке

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

Эта задача отличается от предыдущей тем, что вам нужно изменить значения элементов самого списка, поменяв местами A[0] c A[n-1], A[1] с A[n-2], а затем вывести элементы списка подряд.

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

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

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

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

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

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

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

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

P: Переставить min и max

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

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

Q: Удалить элемент

Дан список из чисел и индекс элемента в списке k. Удалите из списка элемент с индексом k, сдвинув влево все элементы, стоящие правее элемента с индексом k.

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

Программа должна осуществлять сдвиг непосредственно в списке, а не делать это при выводе элементов. Также нельзя использовать дополнительный список.

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

R: Вставить элемент

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

W: Сжатие списка

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

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

X: Кегельбан

\(N\) кеглей выставили в один ряд, занумеровав их слева направо числами от \(1\) до \(N\). Затем по этому ряду бросили \(K\) шаров, при этом \(i\)-й шар сбил все кегли с номерами от \(l_i\) до \(r_i\) включительно. Определите, какие кегли остались стоять на месте.

Программа получает на вход количество кеглей \(N\) и количество бросков \(K\). Далее идет \(K\) пар чисел \(l_i\), \(r_i\), при этом \(1\le l_i\le r_i\le N\).

Программа должна вывести последовательность из \(N\) символов, где \(j\)-й символ есть “I”, если \(j\)-я кегля осталась стоять, или “.”, если \(j\)-я кегля была сбита.

Ввод	Вывод
10 3 8 10 2 5 3 6	I.....I...

Y: Ферзи

Известно, что на доске 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

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

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

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

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

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