Zoznam úloh

1. Kristínine ponožtičky

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 MATH_STASH_4_ENDSTASH MATH_STASH_5_ENDSTASH MATH_STASH_6_ENDSTASH MATH_STASH_7_ENDSTASH
MATH_STASH_8_ENDSTASH MATH_STASH_9_ENDSTASH MATH_STASH_10_ENDSTASH MATH_STASH_11_ENDSTASH MATH_STASH_12_ENDSTASH
MATH_STASH_13_ENDSTASH MATH_STASH_14_ENDSTASH MATH_STASH_15_ENDSTASH MATH_STASH_16_ENDSTASH MATH_STASH_17_ENDSTASH

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;
}
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty