В 1996 році ізраїльська компанія Mirabilis запустила програму миттєвого обміну повідомленнями на ім’я ICQ. В наших краях цю неймовірну для свого часу штуку звали аською. Після кількох перекупів, останній власник виключив ICQ у 2024 році.
Але поки все працювало, у кожного користувача ICQ був свій ідентифікатор, так званий UIN (Universal Identification Number), що складався з 5-9 цифр. У кого був менший номер, той, іноді, дійсно вважав себе крутішим. У різних часів різні дефекти )
Для свого часу аська була неймовірна штука, бо зручне миттєве спілкування в XX столітті на кожному кроці не валялося.
А після преамбули ми розглянемо задачу на ім’я ICQ:
https://www.eolymp.com/uk/problems/443
Умова:
У деякій школі у кожного школяра є свій особистий номер ICQ. У школі поширена думка, що чим менше значення номера ICQ, тим більш «продвинутим» є школяр. Відомо список всіх школярів з номерами ICQ. Потрібно вивести список K самих «продвинутих» школярів.
Вхідні дані
У першому рядку міститься кількість учнів у школі N (1 ≤ N ≤ 100) і число K (1 ≤ K ≤ N). Далі йде N рядків, у кожному рядку міститься прізвище школяра (без пропусків, містить не більше 20 рядкових латинських букв) і через пропуск номер ICQ (1 ≤ ICQ ≤ 10^9). Номера ICQ і прізвища у школярів різні.
Вихідні дані
Вивести прізвища K самих «продвинутих» школярів у лексикографічному порядку (за алфавітом). Кожне прізвище виводиться в окремому рядку.
Приклади
Вхідні дані #1
1 1
d 1
Відповідь #1
d
Обмеження на час виконання: 0,5 секунди
Обмеження на використання пам'яті: 64 мегабайти
Нам буде зручно використати структурований список даних, елементом якого буде запис, в якому буде прізвище користувача та номер ICQ. Двовимірний список в Python нам може стати у пригоді. Для пояснення ми використаємо свій приклад. Наприклад, у нас буде 8 учнів, у кожного буде свій номер, а обирати ми будемо трьох самих «продвинутих», тобто тих, у кого найменші номери ICQ. Не забуваємо, що прізвища цих трьох нам буде треба відсортувати у лексикографічному порядку, тобто за алфавітом.
Наш приклад:
8 3
umkin 92654
dudkin 22654
mamkin 12754
papkin 82654
bubkin 92654
memkin 87054
titkin 222454
babaikina 12254
Після введення даних в кожному записі у нас першим параметром буде прізвище, а другим – номер ICQ. Гарний спосіб відсортувати дані за номером ICQ (перший параметр) надає Python за допомогою функції itemgetter модуля operator. Так просто:
data.sort(key = operator.itemgetter(1))
Після сортування списку ми можемо обрати лише потрібну кількість записів (k).
Дискусійним може бути питання, чи краще коригувати вже існуючий список:
data = data[:k]
мінус такого рішення: ми назавжди губимо повний список учнів і їх номерів ICQ (хоча для даної задачі, після сортування нам цей список більше не потрібний)
чи заводити новий список:
data_result = data[:k]
мінус такого рішення: для нового списку ми використовуємо пам’ять, яку могли б не використовувати.
Як правильно і як краще для цієї задачі – чудова тема для обговорення з вчителем, університетським викладачем або практикуючим розробником (це можуть бути дуже різні люди)
Отже, повний лістинг такого підходу:
import operator
data = []
n, k = map(int, input().split())
for _ in range(n):
name, icq = input().split()
data.append([name, int(icq)])
data.sort(key = operator.itemgetter(1))
data_ = data[:k]
data.sort(key = operator.itemgetter(0))
for x in range(k):
print(data[x][0])
Ось результат роботи програми:
babaikina
bubkin
dudkin
Але можна відсортувати наші дані без використання функції «itemgetter». Для цього можна використати лямбда-функцію. Наприклад, так:
data = []
n, k = map(int, input().split())
for _ in range(n):
name, icq = input().split()
data.append([name, int(icq)])
data.sort(key = lambda x: x[1])
data = data[:k]
data.sort(key = lambda x: x[0])
for x in range(k):
print(data[x][0])
Можете порівняти ці різні варіанти сортування. Обидва коди здають задачу на 100%.
Обирайте, пробуйте, успіхів!