#!/usr/bin/python3 # coding=utf8 # Zdrojový kód k úloze 29-Z1-5 Dva seznamy # Autorka: Katka Zákravská # Vstup programu: # Jsou zadané dva řádky -- dva seznamy kamarádů (jako čísla). # Příklad seznamu: 10 130 57 5 14 8 93 21 56 79 3 2 6 (čísla jsou unikátní) # Výstup programu: # Jména (resp. čísla) kamarádů, kteří jsou v obou seznamech. ## Třídění zde implementujeme, neb se to sluší, když to je v řešení. Ale ## samozřejmě má Python třídění implementované ve funkci sort(). ## Funkce MergeSort setřídí seznam. def MergeSort(seznam): delka = len(seznam) if delka >= 2: pulka = delka // 2 # Celočíselné dělení prvni = MergeSort(seznam[0:pulka]) # Setřídíme první půlku druha = MergeSort(seznam[pulka:delka]) # Setřídíme druhou půlku vysledne = merge(prvni, druha) # A spojíme je do jednoho pole return vysledne else: return seznam # Seznam je jednoprvkový, není tedy co třídit ## Funkce merge bude slévat dvě setříděné části a vrátí jednu setříděnou. def merge(prvni, druha): ## Inicializace a deklarace proměnných p, d = 0, 0 prvni_delka = len(prvni) druha_delka = len(druha) vysledna = list() # Části procházíme, dokud jsou neprázdné obě. while p < prvni_delka and d < druha_delka: # První kamarád z prvního seznamu "je v abecedě dřív" než první kamarád # z druhého seznamu. ("v abecedě dřív" zde znamená, že má nižší číslo.) if prvni[p] <= druha[d]: vysledna.append(prvni[p]) p += 1 # První kamarád z druhého seznamu je v abecedě dřív než první kamarád # z prvního seznamu. else: vysledna.append(druha[d]) d += 1 ## Jedna část je prázdná, v druhé ještě někdo zbývá. # Pokud je prázdná první část, zbylé kamarády z druhé přesuneme na konec # výsledku. if p == prvni_delka: # Funkce extend připojí všechny prvky druha od indexu d na konec listu # vysledna. vysledna.extend(druha[d:]) # Pokud je prázdná druhá část, zbylé kamarády z první přesuneme na konec # výsledku. else: # (d == druha_delka) vysledna.extend(prvni[p:]) return vysledna ## Main # Načtení vstupu prvni_seznam = list(map(int, input().split())) druhy_seznam = list(map(int, input().split())) # Inicializace a deklarace proměnných prvni_delka = len(prvni_seznam) druha_delka = len(druhy_seznam) p, d = 0, 0 vysledny_seznam = list() # Pokud už na vstupu dostaneme jeden ze seznamu prázdný, není co hledat. if prvni_delka == 0 or druha_delka == 0: print("Žádný kamarád se nechce zúčastnit obou her.") sys.exit() # Setřídíme si oba seznamy prvni_setr = MergeSort(prvni_seznam) druhy_setr = MergeSort(druhy_seznam) # Části projdeme a najdeme společné prvky. while p < prvni_delka and d < druha_delka: # Našli jsme stejného kamaráda, zapíšeme si jej. if prvni_setr[p] == druhy_setr[d]: vysledny_seznam.append(prvni_setr[p]) # Posuneme se tam, kde je menší číslo. if prvni_setr[p] <= druhy_setr[d]: p += 1 else: d += 1 # Vypsání výsledného seznamu ve formátu: [1, 4, 7, 10] if len(vysledny_seznam) == 0: print("Žádný kamarád se nechce zúčastnit obou her.") else: print(vysledny_seznam)