В статье представлены варианты использования вложенных списков для сортировки данных. Так же часть задач использует для ввода и вывода данных текстовые файлы.
Представлены задачи: Слияние списков, Пересечение множеств, Гражданская оборона, Средний балл по классам, Отсортировать список участников по алфавиту, Клавиатура, Максимальный балл по классам, Результаты олимпиады.
Слияние списков.
Даны два целочисленных списка A и B, они отсортированы по неубыванию. Нужно объединить их в один упорядоченный список С, в котором будет len(A)+len(B) элементов. Сложность алгоритма должна быть O(len(A)+len(B)), то есть можно только один раз перебрать элементы каждого списка. Функцию sorted и метод sort использовать нельзя.
Решение оформим с помощью функции merge, объединяющей два списка.
def merge(a, b):
....c = []
....ai = 0
....bi = 0
....for i in range(len(a)+len(b)):
........if bi == len(b):
............c.append(a[ai])
............ai += 1
........elif ai == len(a):
............c.append(b[bi])
............bi += 1
........elif a[ai] <= b[bi]:
............c.append(a[ai])
............ai += 1
........else:
............c.append(b[bi])
............bi += 1
....return c
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(*merge(a, b))
Чтобы пройти два списка по одному разу, нам понадобятся два счетчика 'ai' и 'bi'. Каждый счетчик отвечает за свой список. Если текущий элемент списка 'a' меньше или равен элемента из спика 'b', то добавляем к списку 'c' элемент из списка 'a': c.append(a[ai]), иначе добавляем из списка 'b': c.append(b[bi]). Когда один из списков закончится: bi == len(b) или ai == len(a), то добавляем к 'c' все элементы другого списка.
Пересечение множеств.
Заданы два списка, отсортированных по возрастанию (элементы каждого из списков различны).
Найдите пересечение множеств элементов этих списков, то есть нужно найти те числа, которые являются элементами обоих списков. Сложность алгоритма, конечно же, должна быть O(len(A)+len(B)). Программа должна вернуть список пересечения заданных списков по возрастанию элементов.
Решение оформим в виде функции Intersection(A, B).
def intersection(a, b):
....c = []
....ai = 0
....bi = 0
....for i in range(len(a)+len(b)):
........if bi < len(b) and ai < len(a):
............if a[ai] <= b[bi]:
................if a[ai] == b[bi]:
....................c.append(a[ai])
................ai += 1
............else:
................bi += 1
....return c
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(*intersection(a, b))
Задача очень похожа на предыдущую. Отличие в том, что здесь нужно добавлять к искомому списку 'c' только те элементы списков 'a' и 'b', которые равны.
Гражданская оборона.
Известно, что вдоль одной дороги расположены все n селений Тридесятой области. Естественно, что вдоль этой же дороги построили m бомбоубежищ, где в случае чего, могут укрыться жители селений.
Данные для ввода: n - количество селений (1 <= n <= 100000), во второй строке задаются n разных целых чисел, это расстояние от начала дороги до селения. Затем m - количество бомбоубежищ (1 <= m <= 100000). И в четвертой строке - m чисел, расстояний от начала до бомбоубежища.
Нужно для каждого селения найти ближайшее к нему бомбоубежище, то есть вывести для каждого из n селений номер ближайшего к нему бомбоубежища. Номер бомбоубежища - это порядковый номер из входных данных четвертой строки.
n = int(input())
sn = list(map(int, input().split()))
m = int(input())
sm = list(map(int, input().split()))
nl = []
ml = []
for i in range(n):
....nl.append((sn[i], i+1))
for i in range(m):
....ml.append((sm[i], i+1))
nl.sort()
ml.sort()
nomm = 0
ans = []
for i in range(n):
....mins = ''
....for ii in range(nomm, m):
........if mins == '' or mins > abs(nl[i][0] - ml[ii][0]):
............mins = abs(nl[i][0] - ml[ii][0])
............nomm = ii
........elif mins < abs(nl[i][0] - ml[ii][0]):
............break
....ans.append((nl[i][1], ml[nomm][1]))
ans.sort()
asr = []
for i in range(len(ans)):
....asr.append(ans[i][1])
print(*asr)
Для решения задачи нужно отсортировать данные расстояний для селений и бомбоубежищ, чтобы проще было искать ближайшее. Но при этом нужно запомнить порядковые номера селений и бомбоубежищ как они были во входных данных. Для этого создаем пустые списки nl (для селений) и ml (для бомбоубежищ). Каждый элемент списка будет содержать другой список из двух элементов: расстояние и номер по порядку.
for i in range(n):
....nl.append((sn[i], i+1))
for i in range(m):
....ml.append((sm[i], i+1))
Эти списки уже можно сортировать без боязни потерять порядковые номера. Списки по умолчанию отсортируются по расстояниям, то есть по первым элементам маленьких списков.
А дальше делаем цикл по селениям и ищем элемент списка 'ml', начиная с которого abs(nl[i][0] - ml[ii][0]) становится больше предыдущего, записанного в переменной mins. Тогда записываем пару: номер селения и номер бомбоубежища ans.append((nl[i][1], ml[nomm][1])) в список 'ans'.
Затем список 'ans' сортируем и делаем список 'anr' для вывода номеров бомбоубежищ.
Средний балл по классам.
В олимпиаде приняло участие несколько учеников 9-го, 10-го и 11-го классов. Найдите и выведите средние баллы участников для каждого класса.
Входные данные записаны в текстовом файле input.txt в кодировке utf-8 в формате: "Фамилия Имя НомерКласса Балл".
inFile = open('input.txt', 'r', encoding='utf8')
score1, score2, score3 = 0, 0, 0
q1, q2, q3 = 0, 0, 0
for line in inFile:
....line1 = line.split()
....if int(line1[2]) == 9:
........score1 = score1 + int(line1[3])
........q1 += 1
....elif int(line1[2]) == 10:
........score2 = score2 + int(line1[3])
........q2 += 1
....else:
........score3 = score3 + int(line1[3])
........q3 += 1
print(score1/q1, score2/q2, score3/q3)
Считываем построчно файл с помощью функции open, накапливаем в переменных суммы баллов по каждому классу и количества участников от каждого класса, затем выводим среднее арифметическое для каждого класса.
Отсортировать список участников по алфавиту.
Входные данные записаны в текстовом файле input.txt в кодировке utf-8 в формате: "Фамилия Имя НомерШколы Балл". Фамилии у всех разные.
Отсортируйте участников по алфавиту и запишите данные в файл output.txt в формате "Фамилия Имя Балл"
inFile = open('input.txt', 'r', encoding='utf8')
outFile = open('output.txt', 'w', encoding='utf8')
PartList = []
for line in inFile:
....line1 = line.split()
....PartList.append((line1[0], line1[1], line1[3]))
PartList.sort()
for line in PartList:
....print(*line, file=outFile)
inFile.close()
outFile.close()
Здесь всё просто: из каждой строки файла input.txt пишем в каждый элемент списка PartList другой список в формате (Фамилия, Имя, Балл). Затем сортируем, так как первый элемент в каждом маленьком списке "Фамилия", то сортируется по нему. Потом функцией print пишем в файл output.txt. Не забывайте в конце закрывать используемые файлы.
Клавиатура.
При изготовлении клавиатуры для каждой клавиши определяется число нажатий, которое ей необходимо выдерживать при пользовании клавиатурой. Зная эти величины и зная последовательности нажатых клавиш можно определить, какие клавиши сломаются в результате работы, а какие — нет. Определите какие клавиши выйдут из строя, а какие останутся в строю.
Входные данные: n (1≤n≤1000) - число клавиш на клавиатуре. Во второй строке n целых чисел - максимальное количество нажатий, которое может выдержать i-я клавиша. В третьей строке - число k (1≤k≤100000) сумма всех нажатий всех клавиш. Четвертая строка содержит последовательность нажатых клавиш.
Программе необходимо вывести для каждой i-й клавиши слово YES если клавиша сломается и NO если еще нет.
n = int(input())
maxLs = list(map(int, input().split()))
k = int(input())
tapLs = list(map(int, input().split()))
listKey = []
for i in range(n):
....listKey.append(maxLs[i])
for i in range(k):
....nomKey = tapLs[i] - 1
....listKey[nomKey] -= 1
for i in range(n):
....if listKey[i] < 0:
........print('YES')
....else:
........print('NO')
Для решения создадим пустой список listKey и запишем в него максимальные количества нажатий каждой клавиши. Индекс списка - это номер клавиши минус 1, а значение - максимальное количество нажатий.
Затем в диапазоне от 1 до k перебираем последовательность нажатий клавиш и для каждой клавиши находим элемент в списке listKey с индексом клавиши, вычитая из значения единицу.
В конце делаем цикл по listKey и если значение меньше 0, значит максимум был превышен (YES), а иначе (NO) все нормально и клавиша еще поработает.
Максимальный балл по классам.
Определите победителей олимпиады, набравших максимальное количество баллов для каждого из трех классов. Участники заданы в файле input.txt в формате: "Фамилия Имя Класс Балл". Классы - 9, 10, 11.
Выведите три числа: баллы победителей по классам.
inFile = open('input.txt', 'r', encoding='utf8')
score1, score2, score3 = 0, 0, 0
for line in inFile:
....line1 = line.split()
....if int(line1[2]) == 9 and score1 < int(line1[3]):
........score1 = int(line1[3])
....elif int(line1[2]) == 10 and score2 < int(line1[3]):
........score2 = int(line1[3])
....elif int(line1[2]) == 11 and score3 < int(line1[3]):
........score3 = int(line1[3])
inFile.close()
print(score1, score2, score3)
Результаты олимпиады.
В олимпиаде приняло участие N школьников. Каждый получил разное количество баллов. Необходимо отсортировать список участников олимпиады по убыванию набранных баллов. Данные участников задаются в формате: "Фамилия Балл".
n = int(input())
nameList = []
for i in range(n):
....line1 = list(input().split())
....nameList.append((line1[1], line1[0]))
nameList.sort(key=lambda x: -int(x[0]))
for i in nameList:
....print(i[1])
Здесь создаем список nameList, в котором для каждого участника записываем в свой маленький список в формате: (Балл, Фамилия). Для обратной сортировки по баллам используем функцию lambda, в которой добавляем минус перед количеством баллов.
