Zadanie

Kristína si ráno obliekla biele ponožky. Keď však prešla po podlahe, zistila, že sa jej ponožky rýchlo zašpinili. Teraz stojí pred schodami a vidí aké su špinavé.

Na každej polke schodu je rôzne veľa špiny. Ľavou nohou Kristína stúpa na ľavú polovicu schodu a pravou na pravú. Na prejdenie schodov používa iba klasické metódy. (Nohy sa po schodoch striedajú, nepreskočí viac schodov naraz, kráča iba jedným smerom…).

Pomôžte Kristíne prejsť po schodoch tak, aby sa jej biele ponožky čo najmenej zašpinili.

Úloha

Vašou úlohou bude zistiť, či má Kristína vstúpiť na schody pravou alebo ľavou nohou.

Formát vstupu

Na vstupe dostanete celé kladné číslo \(n\). Potom nasleduje \(n\) riadkov obsahujúcich dve čísla \(l_i, r_i\) – špinavosť ľavej a pravej polovice \(i\)-teho schodu. Prvý schod, na ktorý Kristína stúpa je ten, ktorý je prvý na vstupe.

Formát výstupu

Vypíšte prava, lava alebo je to jedno podľa toho, ktorou nohou má Kristína vstúpiť na schody.

Príklady

Hodnotenie

Sú 4 sady vstupov, v ktorých platia tieto obmedzenia:

Sada \(1\) \(2\) \(3\) \(4\)
\(1 \le n \le\) \(100\) \(1\,000\) \(50\,000\) \(100\,000\)
\(0 \le l_i, r_i \le\) \(100\) \(100\) \(1\,000\) \(1\,000\)

Input:

3
2 1
2 1
4 4

Output:

je to jedno

Je jedno, ktorou nohou vstúpi na schodisko, ponožky bude mať zašpinené rovnako.

Input:

5
5 2
4 5
3 1
9 3
4 2

Output:

prava

Input:

6
3 1
4 2
4 5
7 1
2 5
9 8

Output:

lava

Ako už vidno zo zadania, sú iba dve možnosti ako môže Kristína prejsť po schodoch – buď začne ľavou nohou, alebo pravou. Stačí nám teda vypočítať špinavosti oboch možností a vybrať tú menšiu.

Špinavosť pre pravú nohu spočítame tak, že v cykle budeme striedavo pripočítavať ku výslednej špinavosti pravú a ľavú časť schodu. Špinavosť pre ľavú nohu vypočítame obdobne, len začneme ľavou časťou schodu.

Všimnite si, že k vyriešeniu tejto úlohy nepotrebujeme pole – jednotlivé špinavosti vieme spočítavať už pri načítavaní vstupu.

Časová zložitosť je \(O(n)\) - pri sčítavaní špinavostí v cykle prejdeme všetkých \(n\) schodov. Ak sme nepoužili polia, stačili nám dve premenné so špinavosťami a teda pamäťová zložitosť je \(O(1)\). S použitím polí je pamäťová zložitosť \(O(n)\).

n = int(input())

sum_lava, sum_prava = 0, 0

for i in range(n):
    l, p = [int(x) for x in input().split()]
    sum_lava += l if i % 2 == 0 else p
    sum_prava += p if i % 2 == 0 else l

if sum_prava > sum_lava:
    print("lava")
elif sum_lava > sum_prava:
    print("prava")
else:
    print("je to jedno")
#include <iostream>

using namespace std;

int main() {
    int n;

    int sum_lava = 0;
    int sum_prava = 0;

    cin >> n;

    int l, p;  
    for (int i = 0; i < n; i++) {
        cin >> l >> p;
        sum_lava += i % 2 == 0 ? l : p;
        sum_prava += i % 2 == 0 ? p : l;
    }

    if (sum_lava > sum_prava) {
        cout << "prava" << endl;
    } else if (sum_prava > sum_lava) {
        cout << "lava" << endl;
    } else {
        cout << "je to jedno" << endl;
    }

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