3718 - Tort2
Cerința
Alexandra, prințesa Regatului Visurilor a primit un tort și vrea să-l împartă cu prietenii ei. Astfel ea va organiza o petrecere unde îi va invita. Tortul Alexandrei este format din N bucăți, iar a i-a bucată are ai cireșe. Alexandra va împărți tortul în mai multe secvențe continue de bucăți, astfel încât fiecare bucată este inclusă în exact o secvență, și fiecare secvență conține cel puțin o bucată de tort. Prima secvență – cea care conține prima bucată – o va mânca în noaptea de dinaintea petrecerii, iar restul bucăților le va da celorlalți prieteni invitați. Pentru a nu-i supăra, Alexandra vrea ca fiecare secvență dată unui prieten să conțină la fel de multe cireșe ca oricare altă secvență dată unui prieten (dar nu neapărat la fel de multe cireșe ca aceea mâncată de ea înaintea petrecerii). Alexandra trebuie să invite cel puțin un prieten la petrecere. Dându-se N și șirul a, să se afle numărul de moduri în care Alexandra ar putea să împartă tortul în secvențe continue astfel încât să se respecte condițiile din enunț. Două moduri de a împărți tortul se consideră a fi distincte dacă și numai dacă există în unul o secvență care nu există în celălalt (dacă am reprezenta un mod de împărțire în secvențe prin intermediul șirului crescător al indicilor de început pentru fiecare secvență din acea împărțire, două moduri de împărțire sunt distincte dacă șirurile de indici asociate lor sunt diferite).
Formal, dându-se un șir de numere, se vrea să aflăm numărul de moduri de a împărți șirul în cel puțin două subsecvențe, astfel încât sumele elementelor tuturor subsecvențelor să fie egale, prima putând să aibă suma elementelor diferită de a celorlalte.
Date de intrare
Prima linie a fișierului de intrare tort.in conține numărul N. A doua linie conține valorile a1, …, aN, separate prin spații.
Date de intrare
Fișierul de intrare cosuri.in conține pe prima linie două numere naturale T și N separate printr-un spațiu. A doua linie a fișierului conține cele 2•N numere naturale C1, C2,…, C2•N, separate prin câte un spațiu.
Date de ieșire
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Singura linie a fișierului de ieșire tort.out va conține numărul cerut. Î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 ≤ 200.000
- 1 ≤ ai ≤ 400.000
- a1 + ... + aN ≤ 400.000
- Pentru 12 puncte, N ≤ 12
- Pentru alte 12 puncte, 1 ≤ N ≤ 100 și a1 = ... = aN = 1
- Pentru alte 20 puncte, 1 ≤ N ≤ 100
- Pentru alte 28 puncte, 1 ≤ N ≤ 1000 și a1 + ... + aN ≤ 2000
- Pentru alte 28 puncte, fără alte restricții
Exemple
Exemplul 1
- tort.in
- 5
- 1 1 2 1 1
- ecran
- Datele sunt introduse corect.
- tort.out
- 1
Exemplul 2
- tort.in
- 7
- 3 1 4 1 5 9 2
- ecran
- Datele sunt introduse corect.
- tort.out
- 4
Exemplul 3
- tort.in
- 1
- 1000000
- ecran
- Datele nu corespund restricțiilor impuse.
- tort.out
Rezolvare
<syntaxhighlight lang="python" line="1">
- 3718 - Tort2
import sys
def validare_input(n, secventa):
if n < 2 or n > 200000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
for numar in secventa:
if numar < 1 or numar > 400000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
return sum(secventa)
print("Datele sunt introduse corect.")
def poate_imparti_secventa(secventa, n, suma_dorita, index, bucata_curenta, prieteni):
if prieteni == 1:
return False
if bucata_curenta == suma_dorita:
if prieteni == 2:
return True
return poate_imparti_secventa(secventa, n, suma_dorita, 0, 0, prieteni - 1)
for i in range(index, n):
if secventa[i] + bucata_curenta <= suma_dorita:
if poate_imparti_secventa(secventa, n, suma_dorita, i + 1, secventa[i] + bucata_curenta, prieteni):
return True
return False
def rezolvare(n, secventa):
suma_totala = validare_input(n, secventa)
for i in range(2, n + 2):
if suma_totala % i != 0:
continue
suma_dorita = suma_totala // i
if secventa[0] > suma_dorita:
continue
if poate_imparti_secventa(secventa, n, suma_dorita, 1, secventa[0], i):
return i - 1
return 0
if __name__ == "__main__":
with open("tort.in", "r") as fin:
dimensiune = int(fin.readline().strip())
secventa = list(map(int, fin.readline().split()))
suma_totala = validare_input(dimensiune, secventa)
if dimensiune < 2 or dimensiune > 200000:
print("Datele nu corespund restricțiilor impuse.")
sys.exit(0)
with open("tort.out", "w") as fout:
ans = rezolvare(dimensiune, secventa)
fout.write(str(ans))
</syntaxhighlight>
Explicatie
Funcția validare_input(n, secventa) primește doi parametri: n, care reprezintă numărul de elemente din secvență și secventa, o listă de n numere întregi. Această funcție verifică dacă datele de intrare îndeplinesc condițiile impuse: n trebuie să fie cuprins între 2 și 200000, iar fiecare element din secventa trebuie să fie cuprins între 1 și 400000. Dacă datele de intrare nu îndeplinesc aceste condiții, se afișează un mesaj corespunzător și se iese din program cu ajutorul funcției sys.exit(0). Dacă datele de intrare sunt valide, se calculează și se returnează suma elementelor din secvență.
Funcția poate_imparti_secventa(secventa, n, suma_dorita, index, bucata_curenta, prieteni) primește șase parametri:
secventa: lista de numere întregi care reprezintă secvența de împărțit n: numărul de elemente din secvență suma_dorita: suma dorită a bucăților, adică suma totală împărțită la numărul de prieteni index: indexul elementului curent din secvență bucata_curenta: suma curentă a bucății de împărțit prieteni: numărul de prieteni rămași Această funcție verifică dacă secvența secventa poate fi împărțită în prieteni bucăți astfel încât fiecare bucată să aibă suma suma_dorita. Funcția utilizează o abordare recursivă și verifică toate posibilitățile de împărțire, începând de la indexul index. Dacă secvența poate fi împărțită cu succes, se returnează True, altfel se returnează False.
Funcția rezolvare(n, secventa) primește aceiași doi parametri ca și funcția validare_input(n, secventa). Această funcție calculează suma totală a elementelor din secvență prin apelarea funcției validare_input(n, secventa) și apoi parcurge toate posibilitățile de împărțire a secvenței în bucăți egale. Dacă găsește o împărțire validă, returnează numărul de prieteni implicați în împărțire. Dacă nu există o împărțire validă, se returne