2322 - Merry Cristmas: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
 
(Nu s-au afișat 6 versiuni intermediare efectuate de un alt utilizator)
Linia 11: Linia 11:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul '''instabook.out''' va conține n linii: pe linia i se vor afișa separate printr-un spațiu cel mai slab loc si cel mai bun loc din clasament al pozei i, (1 ≤ i ≤ n), iar în consolă se va afișa mesajul "Datele introduse corespund cerintelor." În caz contrar programul va afisa "Datele introduse nu corespund cerintelor."
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse corespund cerintelor.", apoi pe un rând nou afișează  numărul s de sticle necesare . În caz contrar, se va afișa pe ecran: "Datele nu corespund cerintelor."


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Linia 21: Linia 21:
== Exemplul 1 ==
== Exemplul 1 ==
; Intrare
; Intrare
: ''instabook.in''
: Introduceți numărul de case: 7
: Introduceți numărul de case: 7
: Introduceți 0 sau 1 pentru casa 1: 1
: Introduceți 0 sau 1 pentru casa 1: 1
Linia 37: Linia 36:
== Exemplul 2 ==
== Exemplul 2 ==
; Intrare
; Intrare
: ''instabook.in''
: Introduceți numărul de case: 2
: 0 0
: Introduceți 0 sau 1 pentru casa 1: 6
: 0
: Introduceți 0 sau 1 pentru casa 2: 7
: 0
: 0
: 0
: 0
; Ieșire
; Ieșire
: Datele introduse nu corespund cerintelor.
: Datele introduse nu corespund cerintelor.
Linia 50: Linia 45:
== Rezolvare ==  
== Rezolvare ==  
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
#3196
#2322
NMAX = 100005
def validate_input(n, lst):
 
     if not(1 <= n <= 1000000):
 
def validate_input(n, m):
     if not (1 <= n <= 100000):
        print("Datele introduse nu corespund cerintelor.")
        exit()
    if not (1 <= m <= 200000):
         print("Datele introduse nu corespund cerintelor.")
         print("Datele introduse nu corespund cerintelor.")
         exit()
         exit()
    for x in lst:
        if not(0 <= x <= 1):
            print("Datele introduse nu corespund cerintelor.")
            exit()
     print("Datele introduse corespund cerintelor.")
     print("Datele introduse corespund cerintelor.")
   


def read_input(filename):
    with open(filename, "r") as fin:
        n, m = map(int, fin.readline().split())
        validate_input(n, m)
        a = [0] * NMAX
        p = [0] * NMAX
        ma = [0] * NMAX
        mi = [0] * NMAX
        for i in range(1, n + 1):
            a[i] = i
            p[i] = i
            ma[i] = i
            mi[i] = i
        for i in range(1, m + 1):
            x = int(fin.readline())
            if p[x] != 1:
                a1 = a[p[x] - 1]
                a2 = a[p[x]]
                a[p[x] - 1] = a2
                a[p[x]] = a1
                p[a1] += 1
                p[a2] -= 1
                ma[a1] = max(ma[a1], p[a1])
                mi[a2] = min(mi[a2], p[a2])
    return n, ma, mi


 
def calculate_champagne(n, lst):
def write_output(filename, n, ma, mi):
     nr = sum(lst)
     with open(filename, "w") as fout:
    return ((nr-1)*nr)//2
        for i in range(1, n + 1):
            fout.write(str(mi[i]) + ' ' + str(ma[i]) + '\n')




if __name__ == "__main__":
if __name__ == "__main__":
     n, ma, mi = read_input("instabook.in")
     n = int(input("Introduceți numărul de case: "))
     write_output("instabook.out", n, ma, mi)
     lst = []
    for i in range(n):
        x = int(input(f"Introduceți 0 sau 1 pentru casa {i+1}: "))
        lst.append(x)
    validate_input(n, lst)
    result = calculate_champagne(n, lst)
    print(result)


</syntaxhighlight>
</syntaxhighlight>


== Explicatie rezolvare ==
== Explicatie rezolvare ==
Acest program citeste date de intrare dintr-un fisier '''instabook.in''' si apoi le valideaza prin intermediul functiei validate_input, care verifica daca n si m respecta limitele impuse de cerinta. Daca datele de intrare sunt invalide, se afiseaza un mesaj corespunzator si programul se opreste prin intermediul functiei '''exit()'''. Daca datele sunt valide, se afiseaza un mesaj corespunzator si programul continua executia.
Acest program primește de la utilizator un număr n care reprezintă numărul de case, urmat de n numere care indică dacă fiecare casă acceptă sau nu șampania oferită de Moș Crăciun. Dacă o casă acceptă șampania, valoarea introdusă va fi 1, altfel va fi 0. Programul validează inputul și verifică dacă datele introduse sunt conforme cu cerințele. Mai precis, se verifică dacă n este un număr între 1 și 1.000.000, iar toate cele n numere introduse sunt fie 0, fie 1. Dacă inputul nu este conform, programul va afișa un mesaj de eroare și se va încheia. În caz contrar, programul va calcula numărul minim de sticle de șampanie necesare pentru a servi toate casele care acceptă șampania și va afișa rezultatul.
 
In continuare, programul aloca cate o lista pentru a, p, ma si mi de dimensiune '''NMAX'''. Lista a retine ordinea initiala a elementelor, lista p retine pozitia curenta a fiecarui element, lista ma retine pozitia maxima pe care a fost gasit fiecare element si lista mi retine pozitia minima pe care a fost gasit fiecare element.


Urmeaza citirea efectiva a elementelor si executia operatiilor de interschimbare. Daca elementul citit nu se afla deja pe pozitia 1 (adica nu este primul element), se efectueaza interschimbarea elementelor aflate pe pozitiile p[x]-1 si p[x]. Dupa aceasta, pozitia fiecarui element modificat este actualizata in lista p, iar pozitia maxima si minima pe care a fost gasit fiecare element sunt actualizate in listele ma si mi.
Funcția '''calculate_champagne''' primește numărul de case n și lista de valori de la input lst și calculează numărul minim de sticle de șampanie necesare în conformitate cu cerințele problemei. Funcția '''validate_input''' primește aceleași date de la input n și lst și verifică dacă inputul este conform cu cerințele problemei. În cazul în care inputul nu este conform, funcția va afișa un mesaj de eroare și va încheia programul.


In final, programul scrie datele de iesire in fisierul '''instabook.out''' utilizand functia '''write_output'''. Aceasta parcurge toate elementele si scrie, pentru fiecare dintre ele, valorile minime si maxime ale pozitiei acestora in listele mi si ma.
În funcția main, se citește inputul și se validează folosind funcția validate_input. Dacă inputul este conform, programul calculează numărul minim de sticle de șampanie necesare cu ajutorul funcției '''calculate_champagne''' și afișează rezultatul.

Versiunea curentă din 14 aprilie 2023 16:34

Sursa: [1]

Cerinţa

Într-un ținut îndepărtat cu peisaje de poveste pacea domnește peste întreg ținutul deoarece lumea are absolut tot ce îi trebuie.

Moș Crăciun însa dorește să le mai aducă zâmbetul pe buze și de aceea a decis să ducă fiecărei case câte o sticlă de șampanie deoarece deși oamenii de aici au bani, nu au magazine de unde să cumpere. Însă din păcate Moș Crăciun este bătrân și nu poate transporta prea multe sticle așa că decide să distribuie câte o sticla de șampanie la fiecare două case. Pentru simplitate Moș Crăciun a făcut o hartă a caselor în care o casă este notată cu 1 și pământul gol cu 0. Moș Crăciun însă nu prea le are cu programarea și de aceea vă roagă să îl ajutați!

Scrieți un program care primind harta caselor afișează câte sticle de șampanie trebuie să aducă Moș Crăciun.

Date de intrare

Programul va citi un număr natural n de pe prima linie și de pe a doua linie n numere naturale din intervalul [0;1].

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse corespund cerintelor.", apoi pe un rând nou afișează numărul s de sticle necesare . În caz contrar, se va afișa pe ecran: "Datele nu corespund cerintelor."

Restricţii şi precizări

  • 1 ⩽ n ⩽ 1.000.000
  • cele n numere citite vor fi din intervalul [0;1]
  • desigur șampania oferită de Moș Crăciun este una fără alcool
  • oricare două case sunt prietene și nu există pereche de case care să refuze șampania

Exemplul 1

Intrare
Introduceți numărul de case: 7
Introduceți 0 sau 1 pentru casa 1: 1
Introduceți 0 sau 1 pentru casa 2: 0
Introduceți 0 sau 1 pentru casa 3: 0
Introduceți 0 sau 1 pentru casa 4: 1
Introduceți 0 sau 1 pentru casa 5: 0
Introduceți 0 sau 1 pentru casa 6: 1
Introduceți 0 sau 1 pentru casa 7: 1
Ieșire
Datele introduse corespund cerintelor.
6


Exemplul 2

Intrare
Introduceți numărul de case: 2
Introduceți 0 sau 1 pentru casa 1: 6
Introduceți 0 sau 1 pentru casa 2: 7
Ieșire
Datele introduse nu corespund cerintelor.


Rezolvare

#2322
def validate_input(n, lst):
    if not(1 <= n <= 1000000):
        print("Datele introduse nu corespund cerintelor.")
        exit()
    for x in lst:
        if not(0 <= x <= 1):
            print("Datele introduse nu corespund cerintelor.")
            exit()

    print("Datele introduse corespund cerintelor.")


def calculate_champagne(n, lst):
    nr = sum(lst)
    return ((nr-1)*nr)//2


if __name__ == "__main__":
    n = int(input("Introduceți numărul de case: "))
    lst = []
    for i in range(n):
        x = int(input(f"Introduceți 0 sau 1 pentru casa {i+1}: "))
        lst.append(x)
    validate_input(n, lst)
    result = calculate_champagne(n, lst)
    print(result)

Explicatie rezolvare

Acest program primește de la utilizator un număr n care reprezintă numărul de case, urmat de n numere care indică dacă fiecare casă acceptă sau nu șampania oferită de Moș Crăciun. Dacă o casă acceptă șampania, valoarea introdusă va fi 1, altfel va fi 0. Programul validează inputul și verifică dacă datele introduse sunt conforme cu cerințele. Mai precis, se verifică dacă n este un număr între 1 și 1.000.000, iar toate cele n numere introduse sunt fie 0, fie 1. Dacă inputul nu este conform, programul va afișa un mesaj de eroare și se va încheia. În caz contrar, programul va calcula numărul minim de sticle de șampanie necesare pentru a servi toate casele care acceptă șampania și va afișa rezultatul.

Funcția calculate_champagne primește numărul de case n și lista de valori de la input lst și calculează numărul minim de sticle de șampanie necesare în conformitate cu cerințele problemei. Funcția validate_input primește aceleași date de la input n și lst și verifică dacă inputul este conform cu cerințele problemei. În cazul în care inputul nu este conform, funcția va afișa un mesaj de eroare și va încheia programul.

În funcția main, se citește inputul și se validează folosind funcția validate_input. Dacă inputul este conform, programul calculează numărul minim de sticle de șampanie necesare cu ajutorul funcției calculate_champagne și afișează rezultatul.

Adus de la „http://wiki.universitas.ro/index.php?title=2322_-_Merry_Cristmas&oldid=3612”