3648 - Pitici: Difference between revisions
Benzar Ioan (talk | contribs) Pagină nouă: == Cerința == Într-un tărâm îndepărtat, există două grupuri de pitici care se pregătesc să își unească forțele pentru a găsi comori ascunse. Fiecare pitic poartă un număr magic pe pălăria sa, iar aceste numere sunt ordonate crescător în ambele grupuri. Să se determine care sunt piticii comuni în cele două grupuri, utilizând căutarea binară pentru a face operațiunea cât mai eficientă. == Date de intrare == Programul citește de la tastatură două... |
Benzar Ioan (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
== Cerința == | == Cerința == | ||
În orașul Piticot locuiesc N pitici, fiecare într-o casă pe o stradă cu sens unic. Casele sunt așezate de-a lungul străzii, în sensul în care se circulă începând cu casa numerotată cu 1 până la casa numerotată cu N. În orașul Piticot piticii nu au un nume obișnuit! Ei poartă ca nume numărul casei în care stau. Neobișnuite sunt și casele lor! Dacă suni la soneria oricărei case depui atâta efort încât slăbești pe loc un număr de pitic-kilograme. | |||
Pentru că au constatat că în timpul pandemiei s-au îngrășat, fiecare și-a propus să slăbească un număr de pitic-kilograme, într-o singură zi. Pentru asta fiecare pitic va alerga pe stradă, plecând din propria casă și respectând sensul de deplasare al străzii iar în timpul alergării va suna la fiecare casă întâlnită, inclusiv la propria casă, o singură dată la fiecare. Ca regulă, suplimentară ei se vor opri din alergare în următoarele situații: | |||
Orice pitic se va opri la prima casă la care, după ce a sunat, a constatat că a slăbit de când a pornit alergarea, cel puțin cât și-a propus; | |||
Orice pitic se va opri din alergare dacă a sunat la ultima casă (casa N), chiar dacă nu a reușit să slăbească cât și-a propus. | |||
Scrieți un program care determină care este numărul maxim de pitici care au sunat la o casă și la câte case s-a sunat de acest număr maxim de ori. | |||
== Date de intrare == | == Date de intrare == | ||
Fișierul de intrare pitici.in conține pe prima linie numărul natural N. Pe a doua linie se găsesc N numere naturale A[i], reprezentând numărul de pitic-kilograme cu care orice pitic slăbește dacă sună la casa cu numărul i (1 ≤ i ≤ N). A treia linie conține N numere naturale B[i], reprezentând numărul de pitic-kilograme pe care piticul i dorește să îl slăbească. În cadrul unei linii datele sunt separate prin câte un spațiu. | |||
== Date de ieșire == | == Date de ieșire == | ||
Fișierul de ieșire pitici.out conține pe prima linie numerele Max și Nr, separate prin-un spațiu, care reprezintă numărul maxim de pitici care au sunat la o casă, respectiv la câte case s-a sunat de număr maxim de ori. | |||
În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse." | În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse." | ||
== Restricții și precizări == | == Restricții și precizări == | ||
* 1 | *1 ≤ N ≤ 200.000 | ||
*1 ≤ A[i] ≤ 1.000.000.000 | |||
*1 ≤ B[i] ≤ 10^18 | |||
*A[i] ≤ B[i], pentru orice 1 ≤ i ≤ N. | |||
== Exemplu 1 == | == Exemplu 1 == | ||
;Intrare | ;Intrare | ||
1 2 | 7<br> | ||
1 2 4 5 6 6 6<br> | |||
4 2 8 10 14 6 17<br> | |||
;Iesire | ;Iesire | ||
2 6 | |||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
def | def citire_date(): | ||
with open("pitici.in", "r") as f: | |||
N = int(f.readline().strip()) | |||
A = list(map(int, f.readline().strip().split())) | |||
B = list(map(int, f.readline().strip().split())) | |||
return N, A, B | |||
def | def calculeaza_max_pitici(N, A, B): | ||
case = [0] * (N + 1) | |||
for i in range(N): | |||
return | casa = i + 1 | ||
while casa <= N and A[i] > 0: | |||
case[casa] += 1 | |||
A[i] -= B[i] | |||
casa += 1 | |||
max_pitici = max(case) | |||
numar_case = case.count(max_pitici) | |||
return max_pitici, numar_case | |||
def | def scrie_rezultate(max_pitici, numar_case): | ||
with open("pitici.out", "w") as f: | |||
f.write(f"{max_pitici} {numar_case}\n") | |||
def | def main(): | ||
N, A, B = citire_date() | |||
# Verificarea restrictiilor | |||
assert 1 <= N <= 200000, "N trebuie sa fie intre 1 si 200.000" | |||
assert all(1 <= a <= 1000000000 for a in A), "Fiecare A[i] trebuie sa fie intre 1 si 1.000.000.000" | |||
assert all(1 <= b <= 1000000000 for b in B), "Fiecare B[i] trebuie sa fie intre 1 si 1.000.000.000" | |||
max_pitici, numar_case = calculeaza_max_pitici(N, A, B) | |||
scrie_rezultate(max_pitici, numar_case) | |||
if __name__ == "__main__": | if __name__ == "__main__": |
Latest revision as of 21:14, 2 June 2024
Cerința[edit | edit source]
În orașul Piticot locuiesc N pitici, fiecare într-o casă pe o stradă cu sens unic. Casele sunt așezate de-a lungul străzii, în sensul în care se circulă începând cu casa numerotată cu 1 până la casa numerotată cu N. În orașul Piticot piticii nu au un nume obișnuit! Ei poartă ca nume numărul casei în care stau. Neobișnuite sunt și casele lor! Dacă suni la soneria oricărei case depui atâta efort încât slăbești pe loc un număr de pitic-kilograme. Pentru că au constatat că în timpul pandemiei s-au îngrășat, fiecare și-a propus să slăbească un număr de pitic-kilograme, într-o singură zi. Pentru asta fiecare pitic va alerga pe stradă, plecând din propria casă și respectând sensul de deplasare al străzii iar în timpul alergării va suna la fiecare casă întâlnită, inclusiv la propria casă, o singură dată la fiecare. Ca regulă, suplimentară ei se vor opri din alergare în următoarele situații:
Orice pitic se va opri la prima casă la care, după ce a sunat, a constatat că a slăbit de când a pornit alergarea, cel puțin cât și-a propus; Orice pitic se va opri din alergare dacă a sunat la ultima casă (casa N), chiar dacă nu a reușit să slăbească cât și-a propus. Scrieți un program care determină care este numărul maxim de pitici care au sunat la o casă și la câte case s-a sunat de acest număr maxim de ori.
Date de intrare[edit | edit source]
Fișierul de intrare pitici.in conține pe prima linie numărul natural N. Pe a doua linie se găsesc N numere naturale A[i], reprezentând numărul de pitic-kilograme cu care orice pitic slăbește dacă sună la casa cu numărul i (1 ≤ i ≤ N). A treia linie conține N numere naturale B[i], reprezentând numărul de pitic-kilograme pe care piticul i dorește să îl slăbească. În cadrul unei linii datele sunt separate prin câte un spațiu.
Date de ieșire[edit | edit source]
Fișierul de ieșire pitici.out conține pe prima linie numerele Max și Nr, separate prin-un spațiu, care reprezintă numărul maxim de pitici care au sunat la o casă, respectiv la câte case s-a sunat de număr maxim de ori.
În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."
Restricții și precizări[edit | edit source]
- 1 ≤ N ≤ 200.000
- 1 ≤ A[i] ≤ 1.000.000.000
- 1 ≤ B[i] ≤ 10^18
- A[i] ≤ B[i], pentru orice 1 ≤ i ≤ N.
Exemplu 1[edit | edit source]
- Intrare
7
1 2 4 5 6 6 6
4 2 8 10 14 6 17
- Iesire
2 6
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line> def citire_date():
with open("pitici.in", "r") as f: N = int(f.readline().strip()) A = list(map(int, f.readline().strip().split())) B = list(map(int, f.readline().strip().split())) return N, A, B
def calculeaza_max_pitici(N, A, B):
case = [0] * (N + 1) for i in range(N): casa = i + 1 while casa <= N and A[i] > 0: case[casa] += 1 A[i] -= B[i] casa += 1 max_pitici = max(case) numar_case = case.count(max_pitici) return max_pitici, numar_case
def scrie_rezultate(max_pitici, numar_case):
with open("pitici.out", "w") as f: f.write(f"{max_pitici} {numar_case}\n")
def main():
N, A, B = citire_date()
# Verificarea restrictiilor assert 1 <= N <= 200000, "N trebuie sa fie intre 1 si 200.000" assert all(1 <= a <= 1000000000 for a in A), "Fiecare A[i] trebuie sa fie intre 1 si 1.000.000.000" assert all(1 <= b <= 1000000000 for b in B), "Fiecare B[i] trebuie sa fie intre 1 si 1.000.000.000"
max_pitici, numar_case = calculeaza_max_pitici(N, A, B) scrie_rezultate(max_pitici, numar_case)
if __name__ == "__main__":
main()
</syntaxhighlight>