Zadanie

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 vedieť môžeš skúsiť náš python tutoriál.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Hanke na [email protected]

Hanka sa každé ráno ide prejsť okolo rybníka. Na pomery rybníkov je fakt veľký, preto sa doň celú prechádzku Hanka pozerá. Keďže sa do toho rybníku pozerá dlho, všimne si, že v rybníku sú 2 druhy rýb. Sú v ňom veľké ryby a malé rybičky. Čo jej ale príde fascinujúce je, že počty rýb sa menia! Veľké ryby žerú malé rybičky, rybičky sa zas rozmnožujú. Veľmi by ju zaujímalo, koľko rýb tam nájde o deň, o dva a čo sa vlastne s rybníkom bude diať.

Úloha

V rybníku máme 2 druhy rýb - veľké a malé. Každú noc sa dejú 2 veci: - Najprv zožerie každá veľká ryba \(v\) malých rybičiek. Ak žije menej malých rybičiek, než by chceli dokopy zjesť, zjedia ich všetky a na ďalšiu noc pomrú od hladu. - Potom sa každá malá rybička, čo prežila, rozmnoží na \(m\) malých rybičiek.

Hanku zaujímajú 3 možné prípady, čo sa s rybníkom môže diať: - Po konečnom počte dní budú zožrané všetky malé rybičky a teda všetko v rybníku vymrie. - V rybníku stále niečo bude žiť a množstvo malých rybčiek sa bude stále zväčšovať, teda počet rýb rastie. - V rybníku stále nieco bude žiť, ale existuje nejaké číslo \(H\) také, že počet malých rybičiek nikdy nebude väčší než H, teda sa vytvorí rovnováha.

Formát vstupu

V jedinom riadku vstupu budú 4 medzerou oddelené čísla \(a, b, v, m\) - začiatočný počet veľkých rýb, začiatočný počet malých rybičiek, počet rybičiek, ktoré za 1 noc zožerie 1 veľká ryba a počet rybičiek, na ktoré sa každá malá rybička rozmnoží (každá malá rybička zanikne a bude nahradená \(m\) novými rybičkami). Platí \(1 \leq a, b, v, m \leq 10^4\).

Ak neprogramuješ v Pythone, ale napríklad v C++, dávaj si pozor na veľkosť premenných, ktoré používaš. Keď vynásobíš 3 čísla zo vstupu, výsledok sa už nemusí zmestiť do 32-bitového intu, preto je potrebné namiesto neho použiť 64-bitový long long.

Formát výstupu

Na výstup vypíšte jedno slovo podľa toho, čo sa s rybníkom bude diať: vymrie, rastie alebo rovnovaha.

Príklad

Input:

3 15 4 2

Output:

vymrie

V rybníku sú \(3\) veľké ryby a \(15\) rybičiek. Počas prvej noci zožerú ryby \(12\) malých rybičiek a zvyšné \(3\) sa rozmnožia na \(6\). Počas druhej noci už nie je pre veľké ryby dosť rybičiek, preto zožerú všetky a na ďalšiu noc umrú.

Input:

2 4 2 10

Output:

vymrie

Všetky malé rybičky budú zjedené už počas prvej noci.

Input:

2 5 2 10

Output:

rastie

Po prvej noci bude žiť \(10\) rybičiek, po druhej \(60\), …

Input:

1 2 1 2

Output:

rovnovaha

Počas každej noci najprv veľká ryba zožerie jednu z dvoch rybičiek, následne sa tá druhá rybička rozmnoží opäť na dve.

Myšlienka

Keďže veľkých rýb je každý deň rovnako veľa, každé kolo zožerú rovnako veľa malých rybičiek (pokiaľ nevymreli od hladu). Množstvo vzniknutých rybičiek však závisí od toho, koľko jej je. Čim viac rybičiek je, tým viac ich vznikne. To ale znamená, že pokiaľ po prvej noci množstvo rybičiek stúpne, musí stúpnuť aj po druhej a každej neskoršej, pretože ich ubudne rovnako veľa ale pribudne ich viac. Podobne, pokiaľ po prvej noci množstvo rybičiek klesne, musí ich množstvo klesnúť aj po ďálších nociach.

Riešenie

Na vyriešenie tejto úlohy nám teda stačí odsimulovať jedinú noc a pozrieť sa, koľko rybičiek sme mali predtým a koľko máme po noci.

Ak máme na začiatku \(a\) veľkých rýb a \(b\) rybičiek, tak za jednu noc nám najprv zmizne \(a \cdot v\) malých rybičiek, čiže nám ich ostalo \(b - (a \cdot v)\). Tieto rybičky sa rozmnožia a budeme mať \((b-(a \cdot v)) \cdot m\) rybičiek. Porovnáme \(b\) a \((b-(a \cdot v)) \cdot m\). Podľa toho, ktoré číslo je väčšie alebo či sú rovnaké ľahko určíme, čo sa stane s rybníkom. V C++ sa ale musíme uistiť, že používame dostatočne veľké premenné, aby sa do nich čísla zmestili.

Časová a pamäťová zložitosť

Riešenie úlohy zahŕňa len spočítanie a porovnanie niekoľkých čísel, ktorých je vždy rovnako veľa, bez ohľadu na vstupné dáta. Časová zložitosť bude teda konštantná, čiže \(O(1)\). Taktiež si nemusíme pamätať nič iné, len daných pár čísel. Pamäťová zložitosť bude teda tiež \(O(1)\).

Takto môže vyzerať riešenie v Pythone:

a, b, v, m = map(int, input().split())
novy_pocet = (b - (a * v)) * m

if (novy_pocet > b):
    print('rastie')
elif (novy_pocet < b):
    print('vymrie')
else:
    print('rovnovaha')

A takto v C++:

#include <iostream>
using namespace std;

int main() {
    long long a, b, v, m;
    cin >> a >> b >> v >> m;
    long long novy_pocet = (b - (a * v)) * m;

    if(novy_pocet == b) {
	    cout << "rovnovaha\n";
    } else if(novy_pocet > b) {
	    cout << "rastie\n";
    } else if(novy_pocet < b) {
	    cout << "vymrie\n";
    }

    return 0;
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.