Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš, koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a, skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si sa naučiť, môžeš skúsiť našu KSP School.
Ak máš akékoľvek otázky ohľadom tejto úlohy, napíš Tomášovi ([email protected]).
Kým sa Štepi snažil dorozumieť s domorodcami, za kuchárkou Miškou pribehli siedmi domorodci. V rieke ulovili tucet rýb a teraz sa pokúšali spravodlivo si ich rozdeliť. Keď to ale skúšali rozdeliť tak, ako ich to učil šaman kmeňa, vyšlo im, že každý má dostať 1,7142857142857… rýb. Kedže tomu nerozumeli, poprosili Mišku o pomoc. Ona im teda začala vysvetľovať, čo sa to vlastne deje. Pomôž jej s tým.
Májme $m$ rýb a $n$ domorodcov, medzi ktorých treba ryby rozdeliť. Vypočítaj, koľko má každý z nich dostať, teda urobte delenie $m/n$ a nájdite aj prípadnú periódu za desatinnou čiarkou.
V jedinom riadku vstupu budú 2 medzerou oddelené čísla $m$ a $n$ ($1 \le m,n \le 10000$).
Na výstup vypíšte na jeden riadok výsledok delenia v tvare celá časť, čiarka, neopakujúca sa desatinná časť a perióda v hranatých zátvorkách.
43 6
7,1[6]
Číslo pred desatinnou čiarkou je celá časť (7), za čiarkou (,) nasleduje desatinná neopakujúca sa časť (1) a v hranatých zatvorkách je perióda ([6]).
12 5
2,4[0]
V tomto prípade nemáme žiadnu periódu, preto [0].
Kľúč k riešeniu je príjsť na to, ako zistíme, že sme našli koniec periódy. Predstavme si, že chceme vydeliť 2 siedmimi (teda 2/7). 1. Celá časť podielu: Najskôr vypočítame, koľkokrát sa sedmička zmestí do dvadsaťdvojky. To je 3 razy (pretože 3×7=21).
Takže:
$22÷7=3$ (celá časť podielu)
Takže zvyšok je:
$22−21=1$
$10/7=1$ a zvyšok je 3 (takže prvé desatinné miesto je 1)
Pokračujeme so zvyškom 3:
$30/7=4$ a zvyšok je 2 (takže daľšie desatinné miesto je 4)
A tak ďalej, až si všimneme, že sa desatinné miesta opakujú. To je moment, keď sme pravdepodobne našli periódu. Toto nastane vtedy, keď dostaneme rovnaký zvyšok, ako sme už mali. Teda nám stačí si pamätať aké zvyšky sme už mali a keď dostaneme znova rovnaký, vieme, že je to začiatok periódy (cyklu). Kľudne si to vyskúšajte. Ak vieme toto, zvyšok úlohy je celkom jednoduchý.
Tu je celý program v pythone:
def perioda(a, b):
# Krok 1: Vykonanie delenia
cela_cast = a // b
zvysok = a % b
# Ak nie je ziadny zvysok, nie je ani desatinna cast
if zvysok == 0:
return f"{cela_cast},[0]"
# Krok 2: Vypocet desatinnej casti a detekcia periody
desatinne = []
zvysky = {}
pos = 0
while zvysok != 0:
if zvysok in zvysky:
# Nasli sme zaciatok periody
repeat_start = zvysky[zvysok]
non_repeating = ''.join(desatinne[:repeat_start])
repeating = ''.join(desatinne[repeat_start:])
return f"{cela_cast},{non_repeating}[{repeating}]"
# Zaznamename poziciu aktualneho zvysku
zvysky[zvysok] = pos
pos += 1
# Krok dlheho delenia
zvysok *= 10
desatinna_cislica = zvysok // b
desatinne.append(str(desatinna_cislica))
zvysok %= b
# Ak opustime cyklus, neexistuje perioda
return f"{cela_cast},{''.join(desatinne)}[0]"
a,b = list(map(int, input().split()))
odpoved =perioda(a, b)
print(odpoved)