Практика 13-2. Словники

Розв'язати всі завдання (8) у розділі Dictionaries

Обов'язково виконувати завдання під акаунтом для Кіта.

Для першої реєстрації на сайті snakify використовуйте запрошувальне посилання https://snakify.org/join_class/roman.yatsenko/hneu.net/

Базовий рівень

Задача 1. Номер появи слова

У єдиному рядку записаний текст. Для кожного слова з цього тексту підрахуйте, скільки разів воно зустрічалося раніше.

Словом вважається послідовність непробільних символів, що йдуть поспіль, слова розділені одним або більшим числом пробілів або символами кінця рядка.

Підказка

Задача 2. Словник синонімів

Вам дано словник, який складається з пар слів. Кожне слово є синонімом до парного слова. Усі слова у словнику різні.

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

Підказка

Задача 3. Вибори у США

Як відомо, у США президент обирається не прямим голосуванням, а шляхом дворівневого голосування. Спочатку проводяться вибори у кожному штаті та визначається переможець виборів у даному штаті. Потім проводяться державні вибори: на цих виборах кожен штат має певну кількість голосів — кількість виборців від цього штату. На практиці всі виборці від штату голосують відповідно до результатів голосування всередині штату, тобто на заключній стадії виборів у голосуванні беруть участь штати, які мають різну кількість голосів.

У першому рядку дано кількість записів. Далі, кожен запис містить прізвище кандидата та кількість голосів, відданих за нього в одному зі штатів. Підбіть підсумки виборів: для кожного з учасників голосування визначте кількість відданих за нього голосів. Учасників слід виводити в алфавітному порядку.

Підказка

Задача 4. Найчастіше слово

Даний текст: у першому рядку задано число рядків, далі йдуть рядки. Виведіть слово, яке найчастіше зустрічається в цьому тексті. Якщо таких слів кілька, виведіть те, що менше у лексикографічному (алфавітному) порядку.

Підказка

Середній рівень

Задача 5. Права доступа

У файлову систему одного суперкомп'ютера проник вірус, який зламав контроль за правами доступу до файлів. Для кожного файлу відомо, з якими діями можна звертатися до нього:

• запис W,
• читання R,
• запуск X.

У першому рядку міститься число N - кількість файлів, що містяться в даній файловій системі. У наступних N рядках містяться імена файлів і допустимих з ними операцій, розділені пробілами. Далі вказано число M - кількість запитів до файлів. В останніх M рядках вказаний запит виду "Операція Файл". До того самого файлу може бути застосована будь-яка кількість запитів.

Вам потрібно відновити контроль над правами доступу до файлів (ваша програма для кожного запиту повинна буде повертати OK, якщо над файлом виконується допустима операція, або Access denied, якщо операція неприпустима).

Підказка

Задача 6. Країни та міста

Наведено список країн і міст кожної країни. Потім дано назви міст. Для кожного міста вкажіть, в якій країні воно знаходиться.

Підказка

Задача 7. Частотний аналіз

Даний текст: у першому рядку записано кількість рядків у тексті, а потім самі рядки. Виведіть усі слова, що зустрічаються в тексті, по одному на кожен рядок. Слова мають бути відсортовані за зменшенням їхньої кількості появи в тексті, а при однаковій частоті появи — у лексикографічному порядку.

Вказівка. Після того, як ви створите словник всіх слів, вам захочеться відсортувати його за частотою слова. Бажаного можна домогтися, якщо створити список, елементами якого будуть кортежі з двох елементів: частота слова і саме слово. Наприклад, [(2, 'hi'), (1, 'what'), (3, 'is')]. Тоді стандартне сортування сортуватиме список кортежів, при цьому кортежі порівнюються за першим елементом, а якщо вони рівні — то за другим. Це майже те, що потрібно для завдання.

Підказка

Задача 8. Англо-латинський словник

Якось, розбираючи старі книги на горищі, школяр Вася знайшов англо-латинський словник. Англійську він на той час знав досконало, і його мрією було вивчити латину. Тому словник, що попався, був якраз до речі.

На жаль, для повноцінного вивчення мови недостатньо лише одного словника: крім англо-латинського необхідний ще й латинсько-англійській. Через брак кращого він вирішив зробити другий словник з першого.

Як відомо, словник складається з слів, що перекладаються, до кожного з яких наводиться кілька слів-перекладів. Для кожного латинського слова, що зустрічається десь у словнику, Вася пропонує знайти всі його переклади (тобто всі англійські слова, для яких наше латинське зустрічалося в його списку перекладів), і вважати їх і лише їх перекладами цього латинського слова.

Допоможіть Васі виконати роботу зі створення латинсько-англійського словника з англо-латинського.

У першому рядку міститься єдине ціле число N - кількість англійських слів у словнику. Далі слідує N описів. Кожен опис міститься в окремому рядку, в якому записано спочатку англійське слово, потім відокремлений пробілами дефіс, потім розділені комами з пробілами переклади цього англійського слова на латинську. Усі слова складаються лише з маленьких латинських літер. Переклади відсортовані у лексикографічному порядку. Порядок проходження англійських слів у словнику також лексикографічний.

Виведіть відповідний даному латинсько-англійський словник, точно дотримуючись формату вхідних даних. Зокрема, першим має йти переклад лексикографічно мінімального латинського слова, далі другого в цьому порядку і т.д. Всередині перекладу англійські слова також мають бути відсортовані лексикографічно.

Підказка

Підвищений рівень

Задача 9. Контрольна за наголосами

Вчителька задала Петі домашнє завдання - у заданому тексті розставити наголоси в словах, після чого доручила Васі перевірити це домашнє завдання. Вася дуже погано знайомий з цією темою, тому він знайшов словник, в якому зазначено, як ставляться наголоси в словах. На жаль, у цьому словнику присутні не всі слова. Вася вирішив, що в словах, яких немає в словнику, він вважатиме, що Петя поставив наголос правильно, якщо в цьому слові Петей поставлено рівно один наголос.

Виявилося, що в деяких словах наголос може бути поставлений більше ніж одним способом. Вася вирішив, що у разі якщо те, як Петя поставив наголос, відповідає одному з наведених у словнику варіантів, він буде зараховувати це як правильну розстановку наголосу, а якщо не відповідає, то як помилку.

Вам дано словник, яким користувався Вася та домашнє завдання, здане Петею. Ваше завдання – визначити кількість помилок, яку в цьому завданні нарахує Вася.

Вводиться спочатку число N - кількість слів у словнику.

Далі йде N рядків зі словами зі словника. Кожне слово складається не більше ніж із 30 символів. Усі слова складаються з малих і великих латинських букв. У кожному слові велика рівно одна літера - та, на яку потрапляє наголос. Слова у словнику розташовані в алфавітному порядку. Якщо є кілька можливостей розміщення наголосу в тому самому слові, то ці варіанти в словнику йдуть у довільному порядку.

Далі йде вправа, виконана Петею. Вправа є рядком тексту, сумарним обсягом не більше 300000 символів. Рядок складається зі слів, які розділяються між собою рівно одним пробілом. Довжина кожного слова не перевищує 30 символів. Усі слова складаються з малих і великих латинських букв (великими позначені ті букви, для яких Петя поставив наголос). Петя міг помилково в якомусь слові поставити більше одного наголосу або не поставити наголосу зовсім.

Виведіть кількість помилок у Петиному тексті, які знайде Вася.

Підказка

Задача 10. Продажі

Дана база даних о продажах деякого інтернет-магазину. Кожен рядок вхідного файлу є запис виду Покупець товар кількість, де Покупець - ім'я покупця (рядок без пробілів), товар - назва товару (рядок без пробілів), кількість - кількість придбаних одиниць товару.

Створіть список всіх покупців, а кожного покупця підрахуйте кількість придбаних їм одиниць кожного виду товарів. Список покупців, а також список товарів для кожного покупця потрібно виводити у лексикографічному порядку.

Підказка

Задача 11. Родовід: підрахунок рівнів

У генеалогічному дереві в кожної людини, крім родоначальника, є один батько.

Кожному елементу дерева зіставляється ціле невід'ємне число, яке називається висотою. У родоначальника висота дорівнює 0, будь-якого іншого елемента висота на 1 більше, ніж у його батька.

Вам дано генеалогічне дерево, визначте висоту його елементів.

Програма отримує на вхід кількість елементів у генеалогічному дереві N. Далі слідує N-1 рядок, що задають батька для кожного елемента дерева, крім родоначальника. Кожен рядок має вигляд ім'я_нащадок ім'я_батька.

Програма має вивести список усіх елементів дерева у лексикографічному порядку. Після виведення імені кожного елемента потрібно вивести його висоту.

Підказка

Задача 12. Родовід: предки та нащадки

Дано два елементи в дереві. Визначте, чи є один із них нащадком іншого.

У вхідних даних записано дерево в тому ж форматі, що і в попередній задачі. Далі йде число запитів K. У кожному з наступних K рядків містяться імена двох елементів дерева.

Для кожного такого запиту виведіть одне з трьох чисел: 1, якщо перший елемент є предком другого, 2, якщо другий є предком першого або 0, якщо жоден з них не є предком іншого.

Підказка

Задача 13. Родовід: LCA

У генеалогічному дереві визначте для двох елементів найменшого загального предка (Lowest Common Ancestor). Найменшим загальним предком елементів A і B є такий елемент C, що С є предком A, C є предком B, при цьому глибина C є найбільшою з можливих. При цьому елемент вважається своїм предком.

Формат вхідних даних аналогічний попередньому завданню.

Для кожного запиту виведіть найменший загальний предок даних елементів.

---

© Яценко Р.М., 2018-2025

Навчальний центр комп'ютерних технологій "Кит"