2322 - Merry Cristmas - Revision history

Nagy Lenard at 16:34, 14 April 2023

2023-04-14T16:34:42Z

← Older revision		Revision as of 16:34, 14 April 2023
Line 11:		Line 11:

	== Date de ieșire ==		== 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."		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 ==

Dragos1234: /* Date de ieșire */

2023-04-14T15:51:08Z

Date de ieșire

← Older revision		Revision as of 15:51, 14 April 2023
Line 11:		Line 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 ==

Dragos1234: /* Explicatie rezolvare */

2023-04-14T15:46:40Z

Explicatie rezolvare

← Older revision		Revision as of 15:46, 14 April 2023
Line 80:		Line 80:
	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.		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.		Î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.

Dragos1234: /* Explicatie rezolvare */

2023-04-14T15:46:29Z

Explicatie rezolvare

← Older revision		Revision as of 15:46, 14 April 2023
Line 76:		Line 76:

	== 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~~.		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.

	~~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.~~		Î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.

	~~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.

Dragos1234: /* Rezolvare */

2023-04-14T15:44:08Z

Rezolvare

@@ Line 45: / Line 45: @@
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-#3196
+#2322
-NMAX = 100005
+def validate_input(n, lst):
+     if not(1 <= n <= 1000000):
          print("Datele introduse nu corespund cerintelor.")
          exit()
      print("Datele introduse corespund cerintelor.")
-def write_output(filename, n, ma, mi):
+def calculate_champagne(n, lst):
-     with open(filename, "w") as fout:
+     nr = sum(lst)
-        for i in range(1, n + 1):
+    return ((nr-1)*nr)//2
 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 = []
 </syntaxhighlight>

Dragos1234: /* Exemplul 2 */

2023-04-14T15:43:46Z

Exemplul 2

← Older revision		Revision as of 15:43, 14 April 2023
Line 36:		Line 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.

Dragos1234: /* Exemplul 1 */

2023-04-14T15:42:59Z

Exemplul 1

← Older revision		Revision as of 15:42, 14 April 2023
Line 21:		Line 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

Dragos1234: /* Exemplul 1 */

2023-04-14T15:42:45Z

Exemplul 1

← Older revision		Revision as of 15:42, 14 April 2023
Line 22:		Line 22:
	; Intrare		; Intrare
	: ''instabook.in''		: ''instabook.in''
	: ~~3 5~~		: Introduceți numărul de case: 7
	: 3		: Introduceți 0 sau 1 pentru casa 1: 1
	: 2		: Introduceți 0 sau 1 pentru casa 2: 0
	: 1		: Introduceți 0 sau 1 pentru casa 3: 0
	: 3		: Introduceți 0 sau 1 pentru casa 4: 1
	: 3		: 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		; Ieșire
	: Datele introduse corespund cerintelor.		: Datele introduse corespund cerintelor.
	: ~~''instabook.in''~~		: 6
	~~: 1 2~~
	~~: 2 3~~
	~~: 1 3~~
	<br>		<br>

Dragos1234: /* Restricţii şi precizări */

2023-04-14T15:41:59Z

Restricţii şi precizări

← Older revision		Revision as of 15:41, 14 April 2023
Line 14:		Line 14:

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 &les; '''n''' &les; ~~100~~.000		* 1 &les; '''n''' &les; 1.000.000
	* 1 ~~&les; '''m''' &les; 200.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 ==		== Exemplul 1 ==

Dragos1234: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2322/merry-cristmas] == 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...

2023-04-14T15:41:22Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2322/merry-cristmas] == 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...

New page

Sursa: [https://www.pbinfo.ro/probleme/2322/merry-cristmas]
== 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 &les; '''n''' &les; 100.000
* 1 &les; '''m''' &les; 200.000

== Exemplul 1 ==
; Intrare
: ''instabook.in''
: 3 5
: 3
: 2
: 1
: 3
: 3
; Ieșire
: Datele introduse corespund cerintelor.
: ''instabook.in''
: 1 2
: 2 3
: 1 3
<br>

== Exemplul 2 ==
; Intrare
: ''instabook.in''
: 0 0
: 0
: 0
: 0
: 0
: 0
; Ieșire
: Datele introduse nu corespund cerintelor.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
#3196
NMAX = 100005

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.")
exit()
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 write_output(filename, n, ma, mi):
with open(filename, "w") as fout:
for i in range(1, n + 1):
fout.write(str(mi[i]) + ' ' + str(ma[i]) + '\n')

if __name__ == "__main__":
n, ma, mi = read_input("instabook.in")
write_output("instabook.out", n, ma, mi)

</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.