2322 - Merry Cristmas: Difference between revisions
Dragos1234 (talk | contribs) |
Dragos1234 (talk | contribs) |
||
| Line 45: | Line 45: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
# | #2322 | ||
def validate_input(n, lst): | |||
if not(1 <= n <= 1000000): | |||
def validate_input(n, | |||
if not (1 <= n <= | |||
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 | def calculate_champagne(n, lst): | ||
nr = sum(lst) | |||
return ((nr-1)*nr)//2 | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
n | 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) | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Revision as of 15:44, 14 April 2023
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
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."
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
<syntaxhighlight lang="python" line>
- 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)
</syntaxhighlight>
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.
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.
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.