3487 - Dealuri

Sursa: NrTriplete

---

Cerinţă

Fie un șir de numere oarecare. Un subșir de numere se numește deal dacă valorile din care este alcătuit sunt în ordine crescătoare. După fiecare deal urmează o prăpastie – o valoare mai mică decât precedenta – de unde poate începe un nou deal.

Fiind data o secvență oarecare de numere ce se termină cu valoarea zero, să se afișeze valorile din care este alcătuit fiecare deal în ordine inversă apariției. Dupa ce s-a terminat primul deal în ordinea dorită, se va afișa al doilea, apoi al treilea, etc.

Date de intrare

Programul va citi de la tastatură mai multe valori, până la intâlnirea valorii 0.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte!", apoi se va afișa se vor afișa dealurie în ordine inversă celei de introducere, separate prin exact un spațiu.. În cazul în care datele nu respectă restricțiile, se va afișa mesajul "Datele introduse nu sunt corecte!".

Restricţii şi precizări

• Un deal nu are mai mult de 10.000 de elemente.
• Valorile din care sunt formate dealurile sunt numere naturale nenune mai mici decât 263.

Exemple

Exemplul 1

Intrare

Introduceti numerele separate prin spatiu: 1 2 5 3 7 2 4 8 123456789101112 4 0

Ieșire

Datele de intrare sunt valide!

5 2 1 7 3 123456789101112 8 4 2 4

Rezolvare

def validare(lst):
    for i in lst:
        if not i.isdigit():
            print("Datele de intrare sunt invalide!")
            return False
    print("Datele de intrare sunt valide!")
    return True

def rezolvare(lst):
    deals = []
    deal = []
    for i in lst:
        if i == 0:
            break
        if len(deal) == 0 or i > deal[-1]:
            deal.append(i)
        else:
            deals.append(deal[::-1])
            deal = [i]
    if len(deal) > 0:
        deals.append(deal[::-1])
    return [num for deal in deals for num in deal]

def main():
    lst = input("Introduceti numerele separate prin spatiu: ").split()
    if validare(lst):
        deals = rezolvare(list(map(int, lst)))
        print(" ".join(str(num) for num in deals))

if __name__ == '__main__':
    main()

Explicație rezolvare

1. 1 Funcția de validare

Funcția validare() verifică dacă datele de intrare sunt valide, adică respectă restricțiile specificate în enunțul problemei. În cazul acestei probleme, singura restricție este ca numerele să fie naturale nenule, dar și mai mici decât 2^63, deci nu am implementat o validare complexă. Dacă datele sunt valide, se afișează mesajul "Datele de intrare sunt valide!", iar funcția returnează valoarea True. Dacă datele nu sunt valide, se afișează mesajul "Datele de intrare sunt invalide!" și funcția returnează valoarea False.

1. 2 Funcția de rezolvare

Funcția rezolvare() primește un șir de numere și îl parcurge, identificând dealurile și afișându-le în ordinea cerută. Pentru aceasta, am folosit un buclă while care se execută până când se întâlnește valoarea 0 (semnificând sfârșitul șirului). În interiorul buclei, am inițializat o variabilă deal cu primul număr din șir. Apoi am parcurs șirul până am găsit o prăpastie (adica un număr mai mic decât precedenta). În momentul în care am găsit prăpastia, am afișat dealul curent în ordine inversă și am inițializat o nouă variabilă deal cu numărul găsit. După ce am parcurs întregul șir, mai rămâne de afișat ultimul deal, care nu a fost afișat în bucla while, deoarece nu a fost urmat de nicio prăpastie.

1. 3 Funcția main

Funcția main() primește input-ul de la utilizator, îl validează folosind funcția validare(), și apoi îl prelucrează folosind funcția rezolvare(). În final, afișează soluția pe o singură linie, separată prin spații.