Krtko a Jerry sa idú zapísať na ústnu skúšku z analýzy. Keďže analýza je najväčší strašiak matfyzákov, chceli by sa na skúške navzájom podporovať svojou prítomnosťou. Vedia, že profesor vždy volá študentov na ústnu skúšku po skupinkách. Najväčšia šanca, že budú v jednej skupinke je, ak sa zapíšu hneď po sebe. Na skúšku sa však musia poctivo pripravovať, preto nemajú čas zisťovať, na ktoré miesto sa majú zapísať aby išli s čo najväčšou pravdepodobnosťou spolu. Pomôžete im?
Na skúšku je voľných $n$ miest. Zistite, aká je pravdepodobnosť, že Krtko a Jerry pôjdu spolu na skúšku ak sa Jerry zapíše na $r$-tú pozíciu a Krtko hneď pred ňu. Profesor si vždy pred skúškou náhodne zvolí $x$ – veľkosť skupiniek po ktorých bude študentov volať dnu, pričom platí, že $1 \leq x \leq n$. Každá veľkosť skupinky od $1$ po $n$ je rovnako pravdepodobná.
Na vstupe sa nachádza jeden riadok a v ňom dve čísla: $n$ - počet ľudí zapísaných na danú skúšku a $r$ - poradie Jerry, pričom platí $(2 \leq r \leq n \leq 10^{12})$. Pozor, v jazykoch podobných C++ vám nemusí na uloženie $n$ a $r$ stačiť klasický typ int. Riešením(v C++) je napr. použiť typ long long.
V testovacích sadách platia pre $n$ a $r$ nasledovné obmedzenia zhora:
| Sada | 1 a 2 | 3 | 4 | 5 | 6 až 8 |
|---|---|---|---|---|---|
| $n,r \leq$ | $10\,000$ | $100\,000$ | $150\,000\,000$ | $250\,000\,000$ | $10^{12}$ |
Vypíšte dve medzerou oddelené čísla $p$ a $q$ kde $p$ je čitateľ a $q$ menovateľ zlomku, ktorý vyjadruje pravdepodobnosť s akou pôjdu Krtko s Jerry odpovedať v jednej skupinke. Zlomok naviac vypíšte v základnom tvare.
Input:
20 15
Output:
4 5
Na skúšku je zapísaných 20 ľudí pričom Krtko je v poradí 14. a Jerry 15. Krtko a Jerry budú spolu v skupinke ak bude profesor volať študentov po skupinkách veľkosti 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19 alebo 20. Celkovo profesor môže vymyslieť 20 rôznych veľkostí skupiniek (1-20), preto je pravdepodobnosť, že pôjdu spolu 16/20, teda v základnom tvare 4/5.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete