---
tags: Python
---

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

Розв'язати всі завдання (8) у розділі [Dictionaries](https://snakify.org/en/lessons/dictionaries_dicts/)

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

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

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

### [Задача 1. Номер появи слова](https://snakify.org/en/lessons/dictionaries_dicts/problems/number_of_occurrences_before/)

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

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


:::spoiler Підказка
[](https://mermaid.live/edit#pako:eNqNU8Fu2kAQ_ZXVnhIJCGCMwVLbQ9NjT-2pmIOFDVgCGxlbbWohJSDRHqIgVRGHXqr-AaVQCBT4hd0_6ts1uEAvRWLtmXnz5s3MOqI1z7KpTust732tafoBeXttuAQ_x8peVNg3tuWf2IT32ZatqpeHUK5yZVD2hU3ZnN8huCT8lo_YTKAI7AlhO4Ru8e8DtMXbUsLYEyA_2ZawDUD8DrAlTpEWc3cDnzwjjtsJg4vLTLfTcvA06FX1UDpfQeXv57Q7PoiFsCfBugbjFCWWCa_l1MAb9QyaMClRBMVrPiJsBfwv4GNtCcGEdAlb8PFfoSs-EBJ7vQNJIQJkysdshvoDKNjwRzjORCBLCHiRpKmiCzGuGYb7yH6LiZwnETaHOUdwDtY-lAiha_6AjcALbfGkF2KW0rcBboRI9qjLoqi0YD8gcc3v-WeI3Nc7ZT-tDV4IrnSr8aJyR4TafvfLo-3_J1dMgUYxkTGQQzla0QWwy1jVDkvdxnKP157Liuv4VaSh6pDfHy5jclvT6eeAyTMvTyVZtDQLycrSaVlyJd2qPLWjIISNpbN4GtLS_9DGfcSCCB_Kbtd8kI6R0Gy4NEXbtt82HQufWSRyDRo07bZtUB2vll03w1ZgUMPtAWqGgffmxq1RPfBDO0V9L2w0qV43W11YYccyA_vaMRu-2T7zvrKcwPMTpy3N1_HXLT_yFO2Y7jvPax-4G77QtK9ju5btv_RCN6B6WZNYqkf0A9UVtZBRVaVULmiFUimnpOgNnEqmrMDOq7liuVAsa70U_Si5s5mSpvb-AFGODu4)
<!--
-->
:::

### [Задача 2. Словник синонімів](https://snakify.org/en/lessons/dictionaries_dicts/problems/synonym_dictionary/)

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

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


:::spoiler Підказка
[](https://mermaid.live/edit#pako:eNqtU01vm0AQ_SurPSUScbABgzn00vTYU3uqyQGZtY1kFosPtSlCahIpvVStVEU99FL1H1goVlx_5S_M_qMOS6DUUW9FYmDmvZn3ll0yOgo9Rm06noVvR1M3SsjrM4cTvHxPPRrCD9iLj7AQV7CH9flxDXWHpw6Fr1DAUlwiuCLcoafnNdwbIvoT6wW2f4CVZMCDuK7I8IuIS9jgyAJ2mK4d2rRqWQYPJVJKNr2c4OsC7vO85unSQdFyMPajOFFIzEYh9wi6XmLPEu6Jz-dpcnTcieczH59to0Zp9A7l7nCNt7CFPYHiwBzBIRu8t3jvxBXBibCGjfhcSsC20iVoYYEQtixkfYfcL4hWdloL7P8HyXqN_9CUjlqS5pPditsfwXqEVy3CgYG_7UnVA0ftgV21PDrfxTekL8WN-FQfnOZknZw8Q5qMPRm1Zv9lqstoyNh_QoD1n9FE3EhLG3EteaaMViWgqg6nCg1YFLi-h8c8K6c4NJmygDnUxlePjd10hl_L4TlS3TQJX13wEbWTKGUKjcJ0MqX22J3FmKVzz03Yme9OIjc4qL7w_CSMmiKT6cvq75I_mULnLn8ThkE9exKVnh51GPdY9DxMeUJtU5Ncamf0HbU1Q-8YhmYNdFO3rC5iF1jUOgMN857R7Q_0_sDMFfpezlY7lmnkvwERT8dB)
<!--

ввести n
создаем пустой словарь
повторить n раз:
    ввести first, second с помощью input().split()
    добавляем в словарь элемент с ключом first и значением second
    добавляем в словарь элемент с ключом second и значением first
ввести s
вывести элемент словаря с ключом s

-->
:::

### [Задача 3. Вибори у США](https://snakify.org/en/lessons/dictionaries_dicts/problems/usa_elections/)

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

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


:::spoiler Підказка
[](https://mermaid.live/edit#pako:eNqNVctu2lAQ_ZWrK0UNEnmAMQ8vumm67KpdNc7Cih1AAjtyjNrUQmoSKV2UNFIXWXRT9Q-oCw3hYX5h7h917hgbG0hSS1w873PPzIDPjx3T4ho_aTkfjhuG67F3B7rN8Gma-9uH8BNC8QX64hJCGB_lYlPhcE_n8B0CGIoLNI6YrfO9o9hcPETrL9QHGP4ZRuQBc3EVOcMDExcwwZQBzFAc6zwJVXwf5tIiSyaxNsPXPtx3u7FfiRAEKQTiDqYvxC2DMXrOYICJB4S8z-iAMXpMRE9-yxDRY_AHKyEOFO8gSN9AlTcYoDVKgehRYDBE7yFM8TOLEmeuIYvcy_oT8Q1ZQ8dNYOAeFX2yzzDN7RqKBETZ9wnFJLpVCH8xIpTuGy95xZC1OxggKGSOWhaQVwhTNGaxouLMcT3L3M7qczpfklxZkDxK0fwovQ8JtGd4ZtvrFDxHbC7dnMK-HM0fmGuGsK5FLx7MZHJ3dl6iG51FOpVkvkgs0amumQj7IikT11R7Iq7Ir0xnJXpPWvR0DCLVbd3e2mKZUY1Usk_IBLEoSYr3I0zvRx872YsyrKwFhsRroZGDfDJlEMp080JEfZQ9GckukH8ge5c0StZaZp3LkvAb8wSL0jBm4ibdtPSESdC3KC53IfyPXRjBcBOA5QL0cQEGjy8AThYGXibjP0LQ8QrQEmQAYrHVBSCuc2kyxdenJ19qhzGe5-hcmXt53SyF6bknCnM8z9uW2zaaJv5G-3LodO41rLalcw1fTevE6LQ8net2F12Njue8PbePuea5HSvPXadTb3DtxGidodQ5NQ3POmgadddor2hfm03PcROlReKb6K-B_iHy_NSw3ztOO85ddyWmRR3LNi33ldOxPa6pFfLlms8_ck1RS7uqqlRrpUqpWi0oeX6OSmW3pqBcVAvlWqlcq3Tz_BPl3t-tVtTuP83nqW4)
<!--

ввести n
создать пустой словарь
повторить n раз:
    ввести имя кандидата и количество голосов
    прибавить к элементу словаря с ключом кандидата значение голосов
для каждого кандидата в отсортированном словаре sorted(словарь):
    вывести кандидата и его количество голосов (значение элемента словаря)

-->
:::

### [Задача 4. Найчастіше слово](https://snakify.org/en/lessons/dictionaries_dicts/problems/most_frequent_word/)

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


:::spoiler Підказка
[](https://mermaid.live/edit#pako:eNqNVMtu2kAU_ZXRrEACgjEG24t20XTZVbtqHEUWNg8J25Gxm6QIKQQ1zQIFqapYdFP1DwiF8gz8wswf9c4MNg6porIYZu7j3HPP3HEbVzzLxjquNr2LSt30A_Th2HAR_BpWPnVCfpIN_UpG9IZsyPI0HbmkkyMDk29kTKa0C845cg18dBq5Cyfg_QX2MaRfkzmPIFvaE8FkgWiXrAByTB7huDRwnCq322TLPKxknOsi2I7IrNOJ4ooQNyErOkBkCeF_AGhDfpPNHnmEaA_BP3CEyCkPWIOJXtMBGJa0t0dTGOEZeaBDgOzTu4jyFLCmZM2y6c0BaSiwY5AoCa4RkhBwfeBcDjVYCJaJhkus9BgAZyyXi_0dKm6QY16eVbzQDZAIBdZLZkxZjUruk9kM7VYqnU4glQFpX5He73CYnECAawT9ce23wKfLrhRdeL7VKkSdMApkwUkAEB1yJb7wBiF1nCim_p_-TyVLSq61Yx9wnInZANpDIQHs-2AZJGQQI4BexxBSnmk3AYwJH9E5SkKO_9VoogNJDDGTfj_GQoDdjd-R6RPEmbjyDR_QteiX3iOn4aYEejr5CKQ8e0A_QLdHgL-l_ej5xO8rm30FYXwt8FWOXwE_FvmqiH08-NksCBmDInrLh3FFe88gXoor8bXMVzW-VH7UslnQYkSWgp-gqcX3BrgwR88SXyomSTuovOHiDHZs3zEbFnx22gzAwEHddmwD67C17KoZNgMDG24HQs0w8N5fuRWsB35oZ7DvhbU61qtmswWn8NwyA_u4YdZ80zmwvrUagefHRpsf34mvHf_oZfC56X70PCfCrvmM066O7Vq2_4bNHdZVhcdivY0vsS4rxZyiyKpWLBdVVZIz-AqMck6T4VxQpJJWLGnlTgZ_5tj5nFpWOn8Bz12mZA)
<!--

ввести n
создаем пустой словарь
повторить n раз:
    для каждого слова в введенной строке:
        увеличить элемент словаря для слова на 1, или создать его
определяем max_count как max(dic.values())
создаем пустой список words2 для наиболее частых слов
для каждого слова в словаре:
    если слово встречается max_count раз:
        добавить слово в список words2 
вывести наименьшее слово с помощью min(words2)

-->
:::

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

### [Задача 5. Права доступа](https://snakify.org/en/lessons/dictionaries_dicts/problems/permissions/)

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

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

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

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


::: spoiler Підказка
[](https://mermaid.live/edit#pako:eNqtVs1u00AQfpXVSiggpW3SJE3iAwgBJ1SQAAlE3IMVb9tIjYMcR_xYkWiL6AFoL6gHLrxCCJi6aZO-wu4bMTMbOxsnRUIiVd3M7M7fN_NNHfJmxxXc4tt7ndfNXccP2LP7tsfg03ILNxvyu5yoIzlQB3IiR1u3kqNiw-ZqH7RDOH-vjtVXeSknTF6hCFd_y7E6ledM7csLEIdyLGM5YvKXvFAnTH2QA3kOX0_l0OZbidP15U6X-5BXEGgghyhP0EodguqQaWdhzheOm7NY7kkuz3Kv_VYgUHqOkngjmj0tv8j1jQRKYYgVyCGWC-5j-BunAYfwE4EQQSIT-RPLPWNyBMlBGlDKAHNAK_aIUW5nWF-_n3gvN9a0D6oxhjvqBJOHmkAeIHgR2EUJAEn48yTaGC4BGFdwsE9m3bU09QpgR85-UbMo6yx0aG4gz6CSC_i9xIrUAQOdrgeQP0I96zYKW9PczjA6qcdw-QQOAWtwHENqF1iHOp3lNoKzbl5PwxFcQVP0GRNic1HJN4YeE7IjquySFUGlSwAVHKqPODaGf6NrG2EItf-Pvm0afbP5rHPVxhpEMHsHjnS3BpDZqTrWKCXo2nzWmFqYhTnbk-smOduNTEzA4-sCoQ6xLfMRUGF2_U5aVp0GMjbKevxwlnixsHB8t9kU3S5zhdcSrnkTN8U3amIEuX3GPWF7N24w6uYZzqSuAMoiVxNzNQyACJ-zleDJMhfLrZZCCND-yxrAYNkpMiKYU5TMkdpP5whwms6R-pTy3yKn-JknPiaIWxJ7g8OE2Ucg_9Bm0_ooeiQjMM7QfuYWGf9Dx9f3h1mETECZ-pIZxdmETRK-E0sNtse6dUPNdgDA4CFADDxP02Fsaqcpj4zNhKQNxuh8nu7JxgKfE6S7ueogzP_szubfu2PSDKIcY2opsVOLiGCOFxE1wL9-LrPAZ2KeMJ3NEloMsi3GfhgttoxmYGHq0xy9ZwXESYv_ajHHeM339O1gZeU2cJ-e6_Qspf9HSSzTs7JwpDe63hQM6yUoDuneRrrUSazSs5bu0pUVHCE5InV93gIO8aVDZ1VY8HZt1KlBwfZ4nreF33ZaLrwQhWhr82BXtIXNLfjqim2ntxfY3Pb6cNXpBZ2nb70mtwK_J_Lc7_R2drm17ex1Qeq9cp1A3G85O77TzmgfuK2g46dKQeKmfg-j17E8f-V4LzudduJ7x8ecpnGE5wr_XqfnBdwqlit0mVshf8OtUqW8WqmUavVytVyrFUt5_haUpdV6CeT1SnGjXt6oV_t5_o6cF1Zr1Ur_DwjxfxA)
<!--

создаем пустой словарь для файлов
создаем словарь для прав доступа {'read': 'R', 'write': 'W', 'execute': 'X'}
повторить для введенного с клавиатуры N раз:
    ввести строку и преобразовать ее в список s
    добавить в словарь файлов элемент с ключом s[0] и значением в виде списка s, 
      начиная с элемента с индексом 1 и до конца списка
повторить для введенного с клавиатуры M раз:
    ввести операцию и файл
    если элемент словаря прав доступа с ключом операция есть для файла в словаре файлов:
        вывести OK
    иначе:
        вывести Access denied

-->
:::

### [Задача 6. Країни та міста](https://snakify.org/en/lessons/dictionaries_dicts/problems/countries_and_cities/)

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


::: spoiler Підказка
[](https://mermaid.live/edit#pako:eNqFVctu2kAU_ZXRSJVaCRKMMQ8vumm67KpdFWdhBSdBCnbkGrUpQgpFSio1aXZZdNNfMAQXAoH8wp0_6p07tjEmTR1lmMd9nHvuGbvHD7yWw01-eOJ9Pji2_YB92LNchk-7VXrZhN-wEpcQim-wgvn-q-RIa-5aHMb4F4kBHs6Ya_Hd_eS43LQ47Y_R_RxmZAGPtFjBH1iKW7hnYgALXI5hCTOYM3gQt9LJ4mkcvdeTXjCW-dNALsNpCNN-P7GrNHc3wIhzcQMTCZnhOpSpI_SJ8oju0eQOVgwRhBLOIx4MpNu6FKPXw0onsBA3DOYKfeIVA5a-w7X7XAwLqthLrAsji59yxmDKIMKKI3jA_6UCNmVIxRLjR-gnUz8wzeLryqrIJExhhFYLcSW-J8g3AuWYlHEV4HQ_VCVqDHkbIfTt5sRUZMin1JLECfV_JoOunkgVs5DHpMKkHK3MDYKbpf1MqhqRvN3ptnvaDeJuZ1mpU79nmY7_l5AEJRI5lY1cUFfQI-FKCYg6ETd4LQKtJO_CL2pVJC7ElbwJlvvihcZylwD3yoxKJNbEFSpBDBUDWcmHKFE8u4uvhKR5LJ11lqcBzRLBm9KiwojXDbnjD4VB6TG6aVLsuB4pvzgjoYkgQueNXsiohoqa6jxEnU8Sna9Rhhu-c4gKJKxU6VJyTFznVI57dL6hciqmypKHso0w7zguWiX6N1u5NDIayz5r623loW3tKaKzeiN89Zhs8SNL9_XTWpMob7ZQDtZqW-XURowqjaXv3GLxNeqNxjKNevoypGWFRoPGqpqnr6piEelNNcrEBYl_IYZbgZ6zq9FYV_P0hj7vgxfEcnmBdxy_Y7db-EHpSU-LB8dOx7G4idOWc2h3TwKLW24fTe1u4L0_cw-4Gfhdp8B9r3t0zM1D--QTrrqnLTtw9tr2kW93crtvW-3A89NNh5bv1HeMPmcFfmq7Hz2vk8Q-8iWmOI_jthz_jdd1A25WNbLlZo9_4aZuVHYMQ683KrVKva7pBX6Gm_pOQ8d12dCqjUq1UesX-FeKXdqp14xS5tH6fwEqU-21)
<!--

ввести n
содать пустой словарь городов
повторить n раз:
    ввести строку и преобразовать ее в список
    для каждого города в списке, начиная с элемента с индексом 1:
        добавить в словарь городов элемент
            город: список[0]
повторить input раз:
    вывести элемент словаря городов с ключом для ввода

-->
:::

### [Задача 7. Частотний аналіз](https://snakify.org/en/lessons/dictionaries_dicts/problems/frequency_analysis/)

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

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


::: spoiler Підказка
[](https://mermaid.live/edit#pako:eNqVVs1u2kAQfpXVSpFAAsKfAfvQS9NjT-2pcQ4WNglSsFNjlKYIKQQpqVTa3HLopa_g0DgQCPQVdt-os7PYmL-EImGY3Z2Z75uZz3abVh3TohqtnTrn1RPD9cjHA90m8Kmb2cQh-81m_Ib5_IrN2PgoGW7lDnXKu7A6gP1LNoJ_I8L-ojFjj2zK79gT4V02AXPApmzExoQ9sAm_xVXYHuj0KAyXb7eFMxuIPIt48jz4D1gARgBxZuwPmxE2JGwMsX3wuBPoeE94EYA6wqQ-AdtnQ5Gn0wnTFA73ZTCEDscv-S3EBWYEbF8QCMAvWOX1FKadisBdOCaygNt-xKDYbus0BDyWNZh7RVUA397Cfcx7Ol1gU6CibMjuAfGE9_m3MHcAzgF7FuT51UpFBeRFTec5EGSOAPt7TL6FTKz6pV2bGfEm545rNvOxGOWd-As30TwcqS42W3x_kpprfRbVwX4-iCTQmyvphYGeZeli5GGh6bieZSYQTKbuWY1mIpmMF7VyiKBm8PUlq8EmHogYEwbskSTSAk0K95Ixiup2inF_wJWIBSDSfQdu0Vgs8covEcplcYRH8SEOqzJbTGMuK7T7C_JN4dw17wvl6vbeXo4g8aEsCO9Dm0E62Im4Xn1A2F-dLeGfJ6s6XZxb0umi-ZFSAfVcqfz7ulI1Eb4g4JNljcIPzqEoDM6lUCjY99JvjhdxBCxY7bCIWpRRo8750LmH9eGMe45ZgIAUEn54D9lNYPtmzpv_2KxNUb3brcpMAQsRZq0TAcoSkpZea9KaDsGp_DpBVF91RXwQEcUH7MVCNJ4jLLocURzSJX5Q6I3iw6JVwnpDk2TjJYv_1h7EUrfQinsBtSXF7UQl6vOK2jSCOsnOJ5F_3yg1KbToQZlOvwHR4TUfPdPQLOC1iFdF_o8eGek0DHUkUcKv8Z4-4b21QC-dK-G1HN2I0aysLb4UQpX4JQ01ut-97AT3GN2mKdqw3IZRN-Edoi08deqdWA1Lp1BIalo1o3Xq6VS3O3DUaHnOhwu7SjXPbVkp6jqt4xOq1YzTJlitM9PwrIO6cewajZXVd2bdc9xo0ULzvXx1wTeYFD0z7E-O0whjH7sC0zyPZZuW-9Zp2R7VSgqepVqbfqFaQSlmFKVQUYvlYqWSK6ToBSwWMmoB7LySK6nFklrupOhXjJ3NVMpK5x_fnftz)
<!--

создать пустой словарь для слов
повторить для введенного с клавиатуры числа раз:
    ввести строку и преобразовать ее в список
    для каждого слова в списке:
        увеличить элемент словаря для слова на 1, или создать его
создать пустой список words2
для каждого слова word c частотой freq в отсортированном словаре sorted(words.items()):
    добавить в список words2 кортеж (-freq, word)
для каждого кортежа (freq, word) в отсортированном списке sorted(words2): 
    вывести слово

-->
:::

### [Задача 8. Англо-латинський словник](https://snakify.org/en/lessons/dictionaries_dicts/problems/english_latin_dict/)

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

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

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

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

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

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


::: spoiler Підказка
[](https://mermaid.live/edit#pako:eNqlVs1u2kAQfpXVSpFaCQhgDNiH9tD02F7aU3EOVnASpGBH1KhNEVISpPRQJA6tcuilr0BdaBwI7ivsvkKfpDOz2Ji_RFEtxfHuzn7zzc-3S4cfeHWHm_zwxPtwcGy3fPZ2z3IZPI16_klN_BCR_CyG8lJEYrL_NF4q1CwuL2A2gPVzEcJXyMQfGkTit5jJa3HL5IWYwjAQMxGKicX34-3FTgeNRYC4yf7XDD6H4qbbje202i7sDsSYfIWwLgdihFQYjIeMvN2IEXibxiRuYeqXiBg4HTKAm8FomltwieZbL4BBCG8EgyUIURkBVrCbMC11OhYHl1M5YGKiYosdpDYRMoD2FrgT2bP4IhQdcdZ3ANpY3MH0t_nmVMJg4jlAxAjlGjGJ4G-oQh1hMEtbFCIOx-v8InNLPgaYz1Q-UpWqbHBKudgQSrCS1A2-UshVqm2Yqi75CSDDIfRPby2yRVGMxxYFGu0auuQCm41aOSBykbjbkPR01Qr52i64WuapFtfTy_6ef70vBdhZSf5msq8oW3wRWCGPmvsOhtAW8kr2UXGWu7NTYIR4o8og-6A12SM6UVpnQwivj_ZFtqov2BPry0QLjVEQS-qCf6Qo7DxSG1qDy7FSF7odY2NtVRaBbNEVmqDjknKcVG8I1Rttr166qyZiTNx1Fj_IHcmxLdKSl3OAJD9ziDJLP0TgJ1AJ4jiDlaTGsoo2CottURaFt6ItcL7wG2Iu4YBVpCoPkPo_6YGDKirhy7Lkpqtyw3gHaG08qkrQaJeJwkLqI6Uy0tmmGhTyqgWXGa0nN_tQcAtRQX-ipEhOyTWWzT4DadG7mNxANNToXaK3npzU2SzeEGJC02VlklrEy40mK8tLAAPKSaTL5BWdW1PZW3O91Q4Nq_Q2FGtF3khOvvt9wPlhuTzDm06raTfqcK93cKfF_WOn6VjchM-6c2i3T3yLW24XTO227705cw-46bfaToa3vPbRMTcP7ZP3MGqf1m3f2WvYRy27uTL7st7wvVYy6dDwlfo5Qb8qMvzUdt95XjPGPmohp7kfx607rRde2_W5aWhky80O_8hNTS_ldF2rGqVKqVotwNoZTGo5Q4NxUS-UjVLZqHQz_BNh53PVit79BzGXxts)
<!--

создать пустой словарь
повторить N раз:
    ввести строку и разделить ее на англ. слово и список лат. слов
    для каждого лат. слова в списке:
        если лат. слова нет в словаре:
            добавить в словарь новое лат. слово : англ. слово как список
        иначе:
            добавить для лат. слова в список англ. слово
вывести длину словаря
для каждого лат. слова в отсортированном словаре:
    вывести лат. слово - список англ. слов для него

-->
:::

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

### Задача 9. Контрольна за наголосами
<!-- ### [Задача 9. Контрольна за наголосами](http://pythontutor.ru/lessons/dicts/problems/english_latin_dict/) -->

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

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

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

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

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

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

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


::: spoiler Підказка
<!--
[](https://mermaid.live/edit#pako:eNqtVs1u2kAQfpWVpUqtlCgY8kM4tJf02F7aU-McrEAapAARBVUVQgpESiqVlEuUSr30FRwnLg4EeIXdN-o347-1oSmHcjDr2dmZb_4-b8c4bJQrRsk4Oml8Pjy2my3xfs-qC_yq5dzzfflLztSldFRfzuT44EW0Ze5bhupB6mL_TPpY-ULO-WUmf8upupEPQvXkBK-unEpfjvkVctcyDiI7-U6HTkmXHMSG3gosHTnqdiO9wv4GzLjSY6d-Ynm2Edva7BCmUO4IC3J1Ltg3ARpA_ggBTHvyTt2QJXWmblgRWp58RJzXQroZ3DjzyjJiKFsIXd5j-57TgrAf8HInZ4KkmbMhDjkSWE_Ud-QSflbDpYZBzubISo_Sr-VtOwtCXUhPy0qABQYnHJcHP31gWQ2cZsX9N04N1Q6hmnMZe9wZP4IEoeqw7eN_EKeUy_5IQgpN5DQzxU6Ho5uoISHjfgpTrNWXoPQBZcxAACPpll06P0arkcNxCHVAoThkhUxAhE6MmiQyi6xT4igsShJSci3MVPXN3GKXrZKlbJdpTpOUOPIWMYaaGtRgsqjzHahTSaeR3pwnxY2TO0ujNbki7MWD5lSdU0Vgahh2yCjxAx1qCXSSz_1wrpXEzJOhkbwNkqq-RiO_UNpMYXUbGGIYIazJIK9gIJlwM0eU9BMYkEh1oQZESFb92TNT8ISMgnGgUs8RaY9ZS6MhB5UYxK90MC-y9AOFiH5KpFEg1-Iv5EMKm4GCx1Jf71CtL4LB4p7g9Pdpzf2g-inGcWiDHW-J6MeDfhuUOYjOC_jGXQwtGWXkcAUEqHiWZeA7cOtTFxIpMJ7tJ_AAyJVONWlcwwVcyylmOUR1RcXJJH1H6DwTwsCRS0oo9xMP1IwalYaKGQbniiLhFQc-7xd5hYKJeSWMfTddYyYlLNhd-BXERHP3nfF0-mg7vTyeCOeUJtRkm2YuSej_bB7Bk-OLuI7BLwPPW84pi3wSYDWF_tPZBGTAbDJe4BKiuJBLpMNW8hESl79MlL9llUvVjQ8W4FJ9S43gEwfISXyHWV9_CeLgZz6-dfBrgZ-b8fVhfZ2TMWbxVvoENulOw8LtBWP8rQkpSeNP1tvhZ5Gfu_EHKuXLzGny2I2ZT2gvrR5EU9S3l53KC0iEplh8AimfLYRwgMdYM2qVZs2ulnE57JAFy2gdV2oVyyhhWa4c2e2TlmVY9S5U7Xar8e5L_dAotZrtyprRPi3brcpe1f7YtGtG6cg--RRLX5errUYzFp7a9Q-NRqJU4e03wa2UL6fdP_839Us)

создать пустой словарь слов
повторить N раз:
    ввести слово
    если слова в нижнем регистре нет в словаре:
        добавить его в словарь с ключом в нижнем регистре как список
    иначе:
        добавить в элемент словаря с ключом слово в нижнем регистре это слово
присвоить счетчику ошибок 0
для каждого слова в тексте:
    если количество ударений в слове равно 1:
        если слова в нижнем регистре нет в словаре или 
          ударение поставлено правильно:
            вернуться к заголовку цикла
    увеличить счетчик ошибок
вывести счетчик ошибок

-->
:::

### Задача 10. Продажі
<!-- ### [Задача 10. Продажі](http://pythontutor.ru/lessons/dicts/problems/sales/) -->

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

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


::: spoiler Підказка
<!--

from sys import stdin
создаем пустой словарь продаж
for line in stdin.readlines():
    ввести клиента, товар и количество
    если клиента нет в словаре продаж:
        добавить в словарь элемент с ключом клиент и значением словарь,
            в котором элемент товар: количество
    иначе: 
        увеличить количество проданного товара для клиента 
            или создать новый элемент в словаре клиента
для каждого клиента в отсортированном словаре продаж:
    вывести клиент:
    для каждого товара в отсортированном словаре продаж клиента:
        вывести товар, количесто продаж

-->
:::

### Задача 11. Родовід: підрахунок рівнів
<!-- ### [Задача 11. Родовід: підрахунок рівнів](http://pythontutor.ru/lessons/dicts/problems/genealogy_level_count/) -->

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

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

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

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

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

::: spoiler Підказка
<!--

функция высота(человек):
    если человека нет в дереве:
        вернуть 0
    иначе:
        вернуть 1 + высота(дерево[человек])
 
создать пустой словарь для дерева
создать пустой список для людей
повторить N - 1 раз:
    ввести потомка и родителя
    добавить в дерево элемент с ключом потомок и значением родитель
    если потомка нет в списке людей:
        добавить в список людей
    если родителя нет в списке людей:
        добавить в список людей
для каждого человека в отсортированном списке людей:
    вывести человека и значение функции высота для него

-->
:::

### Задача 12. Родовід: предки та нащадки
<!-- ### [Задача 12. Родовід: предки та нащадки](http://pythontutor.ru/lessons/dicts/problems/genealogy_ancestors_and_descendants/) -->

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

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

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

::: spoiler Підказка
<!--

функция предок(ребенок, родитель):
    если ребенок нет в словаре дерево:
        вернуть False
    иначе если родитель является прямым предком ребенка:
        вернуть True
    иначе:
        вернуть предок(родитель ребенка из дерева, родитель)
 
создать пустой словарь дерево
повторить N - 1 раз:
    ввести ребенка и родителя
    добавить в дерево элемент ребенок: родитель
повторить K раз:
    ввести человек_1, человек_2
    если предок(человек_2, человек_1):
        вывести 1
    иначе если предок(человек_1, человек_2):
        вывести 2
    иначе:
        вывести 0

-->
:::

### Задача 13. Родовід: LCA
<!-- ### [Задача 13. Родовід: LCA](http://pythontutor.ru/lessons/dicts/problems/genealogy_lca/) -->

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

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

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

---

(c) Яценко Р.М., 2018-2025

[Навчальний центр комп'ютерних технологій "Кит"](http://kit.kh.ua/)

<img src="https://i.imgur.com/Kh901c1.png" style="width: 150px; position: fixed; top: 100px; right: 10px; border: 0; box-shadow: none;">