1192 - Arhitectura 2

Cerinţa

După ce arhitectul Gigel a reușit să rezolve sarcina primită de la primărie ( #Arhitectura ), el și-a dat seama că aspectul zonei nu va fi unul după preferințele sale. Astfel, s-a stabilit că în oraș nu există clădiri cu înălțimea mai mare decât hmax. Acum primăria îi cere afișarea clădirilor în ordine descrescătoare, precum și verificarea, pentru fiecare clădire din lista ordonată, dacă înălțimea ei este egală cu media aritmetică a înălțimilor celor două clădiri vecine.

Gigel vă cere ajutorul ca să-și termine proiectul care a devenit mult prea greu.

Date de intrare

Fișierul de intrare arhitectura2in.txt conține pe prima linie numărul n, iar pe următoarele linii n numere naturale separate prin spații. Fiecare linie conține maxim 100.000 de valori.

Date de ieşire

Fișierul de ieșire arhitectura2out.txt va conține doua linii cu n valori fiecare. Prima linie va conține înălțimile în ordine descrescătoare , iar a doua linie va conține n valori 1 sau 0, după cum înălțimea clădirii curente este sau nu egală cu media aritmetică a înălțimilor celor două clădiri vecine.

Restricții și precizări

• 1 ≤ n ≤ 2000000
• hmax ≤ 100000
• Pentru 40% din teste n ≤ 50000
• Pentru 80% din teste n ≤ 500000
• Considerăm că înaintea primei clădiri și după ultima clădire se află câte o pseudoclădire de înălțime 0 – care va interveni în verificarea cerută.

Exemplul 1

arhitectura2in.txt

10

5 10 10 9 5 2 5 8 5 2

arhitectura2out.txt

Datele introduse corespund restricțiilor impuse.

10 10 9 8 5 5 5 5 2 2

0 0 1 0 0 1 1 0 0 0

Explicație

Șirul devine 10 10 9 8 5 5 5 5 2 2 Doar 9 si cei doi de 5 din mijloc respectă condiția.

Exemplul 2

arhitectura2in.txt

2000001

5 10 10 9 5 2 5 8 5 2

arhitectura2out.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 1192 - Arhitectura 2
def validare(numar_cladiri, inaltimi):  # functia de validare a datelor de intrare

    if numar_cladiri > 2000000 or numar_cladiri < 1:
        raise ValueError

    for inaltime in inaltimi:
        if inaltime > 100000 or inaltime < 1:  # fiecare inaltime trebuie sa fie intre 1 si 100000
            raise ValueError

    print("Datele de intrare corespund restrictiilor impuse\n")


def arhitectura(numar_cladiri, inaltimi):  # functia de rezolvare
    # Sortăm înălțimile în ordine descrescătoare
    inaltimi.sort(reverse=True)

    # Convertim lista de înălțimi într-un șir de caractere pentru a fi afișată
    cladiri_ordonate = ' '.join(map(str, inaltimi))

    # Inițializăm o listă goală pentru a stoca rezultatele verificării
    verificare = []

    # Parcurgem lista de înălțimi
    for i in range(numar_cladiri):
        # Dacă suntem la prima sau la ultima clădire, adăugăm '0' în lista de verificare
        if i == 0 or i == numar_cladiri - 1:
            verificare.append('0')
        else:
            # Dacă înălțimea clădirii curente este egală cu media aritmetică a înălțimilor celor două clădiri vecine,
            # adăugăm '1' în lista de verificare
            if inaltimi[i] == (inaltimi[i - 1] + inaltimi[i + 1]) / 2:
                verificare.append('1')
            else:
                # Dacă nu, adăugăm '0' în lista de verificare
                verificare.append('0')

    # Convertim lista de verificare într-un șir de caractere pentru a fi afișată
    return cladiri_ordonate, ' '.join(verificare)


if __name__ == '__main__':
    numar_cladiri_input = int(input("Introduceți numărul de clădiri: "))
    inaltimi_input = list(map(int, input("Introduceți înălțimile clădirilor, separate prin spațiu: ").split()))

    try:
        validare(numar_cladiri_input, inaltimi_input)  # apelul functiei de validare
        print(arhitectura(numar_cladiri_input, inaltimi_input))  # apelul functiei de rezolvare

    except ValueError:
        print("Datele de intrare nu corespund restrictiilor impuse")