Jump to content
Main menu
Main menu
move to sidebar
hide
Navigation
Main page
Recent changes
Random page
Help about MediaWiki
Bitnami MediaWiki
Search
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Editing
2032 - Mmult
Page
Discussion
English
Read
Edit
Edit source
View history
Tools
Tools
move to sidebar
hide
Actions
Read
Edit
Edit source
View history
General
What links here
Related changes
Special pages
Page information
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Cerința== Alexandru, mare informatician, a decis să își impresioneze prietenii cu următoarea problemă: Dându-se un vector cu N numere naturale nenule, se întreabă care este numărul minim de mulțimi cu numere consecutive de forma '''{1...K}''' în care acesta poate fi împărțit. Spre exemplu vectorul '''A = {1, 3, 2, 2, 1, 4}''' poate fi împărțit în număr minim de partiții astfel '''{1, 2, 3, 4}, {1, 2}'''. Cum această problemă a fost prea dificilă pentru prietenii săi, Alexandru te roagă pe tine să o rezolvi. == Date de intrare == Fișierul de intrare '''mmult.in''' conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații. == Date de ieșire == Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse Fișierul de ieșire '''mmult.out''' va conține pe prima linie numărul S, reprezentând răspunsul problemei date de Alex. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.". == Restricţii şi precizări == *'''1 ≤ N ≤ 100.000''' *numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000''' *dacă problema nu are soluție, se va afișa -1 == Exemple == ===Exemplul 1=== ; ''mmult.in'' :6 :1 3 2 2 1 4 ; ''ecran'' :Datele sunt introduse corect. ; ''mmult.out'' :2 ===Exemplul 2=== ; ''mmult.in'' :5 :2 3 1 1 2 ; ''ecran'' :Datele sunt introduse corect. ; ''mmult.out'' :2 ===Exemplul 3=== ; ''mmult.in'' :0 ; ''ecran'' :Datele nu corespund restricțiilor impuse. ; ''mmult.out'' == Rezolvare == <syntaxhighlight lang="python" line="1"> # 2032 - Mmult import sys def validate_input(n, nums): """ Validates input data for the problem """ if n < 1 or n > 100000: return False for num in nums: if num >= 1000000: return False return True def solve(n, nums): """ Solves the problem and returns the answer as an integer """ f = [0] * 100001 m = 0 for x in nums: m = max(m, x) f[x] += 1 for i in range(2, m + 1): if f[i] > f[i - 1]: return -1 return f[1] if __name__ == '__main__': # Read input with open('mmult.in', 'r') as fin: n = int(fin.readline()) nums = list(map(int, fin.readline().split())) # Validate input if not validate_input(n, nums): print("Datele nu corespund restricțiilor impuse.") sys.exit(0) # Solve problem ans = solve(n, nums) # Write output with open('mmult.out', 'w') as fout: fout.write(str(ans)) # Print success message print( "Datele sunt introduse corect.") </syntaxhighlight> ==Explicatie== Funcția validate_input(n, nums): Această funcție primește ca argumente un număr întreg n și o listă de numere întregi nums. Funcția verifică dacă acestea respectă restricțiile impuse de problemă și returnează True în caz afirmativ sau False în caz contrar. Mai precis, funcția verifică următoarele condiții: n trebuie să fie între 1 și 100000, inclusiv toate numerele din lista nums trebuie să fie mai mici decât 1000000. Dacă datele introduse respectă aceste restricții, funcția returnează True, altfel returnează False. Funcția solve(n, nums): Această funcție primește ca argumente un număr întreg n și o listă de numere întregi nums. Funcția rezolvă problema descrisă în enunțul problemei și returnează răspunsul ca un număr întreg. Mai precis, funcția efectuează următoarele operații: inițializează un vector f cu 100001 elemente cu valoarea 0 găsește numărul maxim m din lista nums pentru fiecare număr x din lista nums, incrementează valoarea elementului f[x] parcurge elementele vectorului f de la 2 la m și verifică dacă f[i] este mai mare decât f[i-1]. Dacă da, înseamnă că problema nu are soluție și funcția returnează -1. dacă toate elementele vectorului f respectă această proprietate, funcția returnează valoarea f[1]. Funcția main(): Această funcție este funcția principală a programului și este responsabilă pentru citirea datelor de intrare din fișierul "mmult.in", validarea lor utilizând funcția validate_input, rezolvarea problemei utilizând funcția solve, scrierea răspunsului în fișierul "mmult.out" și afișarea unui mesaj corespunzător pe ecran. Mai precis, funcția efectuează următoarele operații: deschide fișierul "mmult.in" în modul de citire și citește valorile pentru n și nums utilizând metoda readline și funcția map validează datele introduse utilizând funcția validate_input. Dacă acestea nu respectă restricțiile, afișează un mesaj corespunzător pe ecran și oprește programul utilizând funcția exit. rezolvă problema utilizând funcția solve și stochează rezultatul în variabila ans deschide fișierul "mmult.out
Summary:
Please note that all contributions to Bitnami MediaWiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
Bitnami MediaWiki:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)
Toggle limited content width