Zadanie

V prísne tajnej KSP miestnosti T2 je koberec. Kedysi vraj býval modrý, teraz však už pohltil toľko prachu, omrviniek, vlasov a kadečoho ďalšieho, že je skôr sivý. Kubík sa teda rozhodol, že je najvyšší čas koberec opäť povysávať. S hrôzou však zistil, že za tú dobu, čo tam koberec ležal, na ňom začalo všeličo rásť. Dokonca sa v ňom vytvoril samostatný ekosystém! Spozoroval dva typy organizmov: predátorov a korisť. Predátori sú (prekvapivo) špecifickí tým, že žerú korisť. Korisť je špecifická tým, že sa množí.

Kubík má teraz dilemu; nemôže predsa vysávať ekosystém! Radšej by bol, keby ekosystém prirodzene vymrel. Totiž, keby sa stalo, že predátori požerú všetku korisť, nebudú mať čo jesť a vymrú. Ak sa to nestane, bude musieť zavolať deratizátorov. Je ochotný chvíľu s vysávaním počkať, ale má to vôbec zmysel? Čo ak sa ekosystém rozrastie a potom sa ho nezbaví už nikto?

Úloha

Pre jednoduchosť budeme náš ekosystém modelovať po kolách. V každom kole sa postupne udeje nasledovné:

  • Každý predátor zožerie \(p\) kusov koristi. V prípade, že na toto nežije dostatočne veľa koristi, predátori vyžerú všetku žijúcu korisť a v ďalšom kole pomrú od hladu.

  • Každá korisť, ktorá ostala, sa nahradí \(k\) novými korisťami.

V ekosystéme môžu nastať tri prípady:

  • Po nejakom (konečnom) počte kôl vymrie všetka korisť a následne aj predátori. Vtedy hovoríme, že ekosystém vymrie.

  • Ekosystém bude schopný fungovať donekonečna a množstvo koristi bude rásť nad všetky medze. Vtedy hovoríme, že ekosystém rastie.

  • Ekosystém síce bude žiť donekonečna, ale existuje nejaké číslo \(H\) také, že množstvo koristi nikdy neprekročí \(H\). Vtedy hovoríme, že ekosystém je v rovnováhe.

Zistite, ktorý z týchto prípadov nastane.

Formát vstupu

V prvom riadku sú štyri celé čísla \(a, b, p, k\) - začiatočný počet predátorov, začiatočný počet kusov koristi, počet koristi, ktorú za jedno kolo jeden predátor skonzumuje, a počet koristi, ktorá vznikne z jednej pôvodnej koristi (pôvodná korisť zanikne a bude nahradená \(k\) novými). Platí \(1\leq a, b, p, k\leq 10^4\).

Dávajte si pozor na veľkosť čísel, s ktorými pracujete. Keď napríklad vynásobíte tri čísla zo vstupu, výsledok sa vám nemusí zmestiť do 32-bitovej premennej.

Formát výstupu

Na výstupe vypíšte jedno slovo (bez úvodzoviek): “vymrie” , “rastie” alebo “rovnovaha” podľa toho, ktorý prípad nastane.

Príklady

Input:

3 15 4 2

Output:

vymrie

V ekosystéme sú traja predátori a \(15\) kusov koristi. V prvom kole predátori zožerú \(12\) kusov koristi a zvyšné \(3\) sa rozmnožia na \(6\). V druhom kole už nie je pre predátorov dosť koristi, preto zožerú všetku a následne umrú.

Input:

2 4 2 10

Output:

vymrie

Všetka korisť bude zožraná už v prvom kole.

Input:

2 5 2 10

Output:

rastie

Po prvom kole bude žiť \(10\) kusov koristi, po druhom \(60\), …

Input:

1 2 1 2

Output:

rovnovaha

V každom kole najprv predátor zožerie jednu z dvoch koristí, následne sa tá druhá korisť rozmnoží opäť na dve.

Keďže predátorov je vo všetkých kolách rovnako veľa, každé kolo zožerú rovnako veľa koristi (pokiaľ nevymreli od hladu). Množstvo vzniknutej koristi však závisí od toho, koľko jej je. Čím viac koristi je, tým viac jej vznikne. To však znamená, že pokiaľ v prvom kole množstvo koristi stúpne, musí stúpnuť aj v druhom kole a každom neskoršom, pretože ich ubudne rovnako veľa ale pribudne ich viac. Podobne, pokiaľ v prvom kole množstvo koristi klesne, musí jej množstvo klesnúť aj v ďalších kolách.

Na vyriešenie tejto úlohy nám teda stačí odsimulovať jediné kolo ekosystému a pozrieť sa, koľko koristi sme mali predtým a koľko máme po kole.

Ak máme teda na začiatku \(a\) predátorov a \(b\) kusov koristi, tak za jedno kolo nám najprv zmizne \(a\cdot p\) kusov koristi, čiže nám ich ostalo \(b-(a\cdot p)\) kusov. Táto korisť sa rozmnoží a budeme mať \((b-(a\cdot p))\cdot k\) kusov koristi. Porovnáme teda \(b\) a \((b-(a\cdot p))\cdot k\). Podľa toho, ktoré číslo je väčšie alebo či sú čísla rovnaké ľahko určíme, čo sa stane s ekosystémom. Musíme sa ale uistiť, že používame dostatočne veľké premenné, aby sa nám do nich číslo zmestilo.

Č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 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ž konštantná: \(O(1)\).

#include <iostream>
using namespace std;

int main() {
    long long pocet_predatorov, pocet_koristi, p, k;
    cin >> pocet_predatorov >> pocet_koristi >> p >> k;
    long long zozrata_korist = pocet_predatorov * p;
    long long nova_korist = (pocet_koristi - zozrata_korist) * k;
    if(nova_korist == pocet_koristi) {
	cout << "rovnovaha\n";
    } else if(nova_korist > pocet_koristi) {
	cout << "rastie\n";
    } else if(nova_korist < pocet_koristi) {
	cout << "vymrie\n";
    }
}
a, b, p, k = map(int, input().split())
c = (b - a * p) * k
if (c > b):
    print('rastie')
elif (c < b):
    print('vymrie')
else:
    print('rovnovaha')

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ť.