from random import randint

# napiste funkci guess_number_human, kdy si počítač zvolí náhodné číslo
# od nuly po upper_bound a člověk hádá, o které číslo jde
# po každém pokusu počítač vypíše, zda hádané číslo je to, které si
# zvolil, nebo jestli je jeho číslo větší nebo menší
def guess_number_human(upper_bound):
    pass

# --- pokus c. 1 ---
# Zadej svuj tip: 5
# Moje cislo je mensi.
# --- pokus c. 2 ---
# Zadej svuj tip: 3
# Moje cislo je vetsi.
# --- pokus c. 3 ---
# Zadej svuj tip: 4
# Jo, to je ono!

# guess_number_human(10)

# napište funkci guess_number_pc, kdy vy si myslíte číslo od nuly
# po upper_bound a počítač se ho snaží uhádnout na co nejmenší počet pokusů
# po každém pokusu počítač dostane informaci, jestli číslo uhádl,
# nebo jestli číslo, které si myslíte, je větší nebo menší
def guess_number_pc(upper_bound):
    pass

# Mysli si cislo od 1 do 10.
# Je cislo 5 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Je cislo 2 mensi (0), rovno (1), nebo vetsi (2) nez tvoje cislo?
# 2
# Tvoje cislo je 1.

# guess_number_pc(10)


# Napište funkci guess_number_pc_pc(upper_bound), která vykoná hru
# v hádání myšleného čísla počítače proti počítači. Na závěr vypíše
# počet pokusů potřebných k uhádnutí čísla.
def guess_number_pc_pc(upper_bound):
    pass

# A: Myslim si cislo od 1 do 10
# --- pokus c. 1 ---
# B: Tipuji 5
# A: Moje cislo je mensi.
# --- pokus c. 2 ---
# B: Tipuji 2
# A: Moje cislo je vetsi.
# --- pokus c. 3 ---
# B: Tipuji 3
# A: Jo, to je ono!
# Uhadnuto na 3 pokusu

# guess_number_pc_pc(10)


# Napište funkci binary_search(needle, haystack), která zjistí, zda
# se hodnota needle nachází ve vzestupně uspořádaném seznamu haystack.
# Funkce musí mít logaritmickou časovou složitost.
def binary_search(needle, haystack):
    pass

def test_binary_search_basic():
    assert binary_search(5, [1, 2, 5, 8])
    assert not binary_search(4, [1, 2, 5, 8])

# test_binary_search_basic()

# Napište funkci test_binary_search_extended a vložte do ní
# alespoň 5 testů předchozí funkce binary_search.
def test_binary_search_extended():
    pass

# test_binary_search_extended()

# Vylepšete funkci binary_search funkci tak, aby vracela index pozice,
# kde se hledaný prvek nachází. Pokud prvek v seznamu není, vraťte -1.
def binary_search_position(needle, haystack):
    pass


def test_binary_search_position() -> None:
    assert binary_search_position(5, [1, 2, 5, 8]) == 2
    assert binary_search_position(4, [1, 2, 5, 8]) == -1

# test_binary_search_position()


# Vylepšete předchozí funkci tak, aby vracela seznam indexů pozic,
# na kterých se hledaný prvek vyskytuje. Pokud prvek v seznamu není
# ani jednou, vrátíte prázdný seznam.
# Výzva: dokážete i toto v logaritmickém čase? (pro logaritmické řešení
# nestačí najít nějaký výskyt a od něj pokračovat na obě strany,
# je třeba upravit algoritmus binárního vyhledávání a zvlášť najít
# první a poslední výskyt)
def binary_search_position_list(needle, haystack):
    pass


def test_binary_search_position_list() -> None:
    assert binary_search_position_list(5, [1, 2, 3, 3, 5, 5, 5, 8]) == [4, 5, 6]
    assert binary_search_position_list(4, [1, 2, 5, 8]) == []


# test_binary_search_position_list()


# Napište funkci super_power(base, exp), která umocní dané číslo
# base na daný exponent exp. Funkce musí mít logaritmickou časovou
# složitost vzhledem k hodnotě exponentu.
def super_power(base: int, exp: int) -> int:
    pass


def test_super_power() -> None:
    assert super_power(2, 7) == 128
    assert super_power(5, 15) == 30517578125


# test_super_power()