Fişierul intrare/ieşire:popeala.in, popeala.outSursăCEOI 2016, Ziua 2
AutorEugenie Daniel PosdarascuAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test1.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Popeala

Cuvântul românesc “popeală” îşi are originile în nuvela istorică românească "Alexandru Lăpuşneanul" unde Prinţul Moldovei foloseşte o serie de termeni pentru a descrie o viitoare răzbunarea a sa asupra uzurpatorilor. Termenul a fost recent adoptat, oarecum surprinzător, pe scena concursurilor româneşti de programare. El este folosit pentru a descrie situaţiile când comisia face viaţa grea concurenţilor într-un mod neortodox şi (de regulă) involuntar: limite de timp foarte stricte, teste eronate, probleme greşite, tastaturi furate şi alte mecanisme. Această problemă se referă la o “popeală”.

Considerăm un concurs de programare cu N participanţi. Concursul are doar o problemă cu T teste. Comisia ştiinţifică doreşte să grupeze testele în cel mult S subprobleme. Cum funcţionează subproblemele: Fiecare test aparţine exact unei subprobleme. O subproblemă poate conţine un număr oarecare de teste dar cel puţin unul. Dacă un participant ratează cel puţin un test al unei subprobleme, punctajul său la această subproblemă va fi 0. În caz contrar, scorul pentru această subproblemă va fi egal cu suma valorilor punctajelor tuturor testelor subproblemei. Aceasta este o practică obişnuită a concursurilor de programare, dar acum comisia doreşte să facă acest lucru după ce concursul se termină. Comisia ştie care sunt testele rezolvate corect de fiecare participant şi doreşte să grupeze testele fiecărei subprobleme astfel încât să minimizeze numărul total de puncte obţinut în concurs.
Concret, ţi se dă un şir de întregi Points[] de dimensiune T. Points[i] va conţine punctajul celui de-al i-lea test. Primeşti, de asemenea, un tablou bidimensional Results[][] de dimensiune N * T. Results[i][j] va fi egal cu 1 dacă al i-lea concurent a rezolvat corect cel de-al j-lea test. În caz contrar acesta va fi 0. Comisia a decis deja că toate subproblemele vor conţine teste consecutive. Cu alte cuvinte, dacă testele X şi Y sunt conţinute de aceeaşi subproblemă, atunci orice test Z cu X ≤ Z ≤ Y, se va afla în aceeaşi subproblemă. Tu trebuie să ajuţi comisia. Aceştia doresc să afle, pentru fiecare valoare 1 ≤ K ≤ S, care este numărul total de puncte minim posibil ce se poate obţine în concurs dacă testele se vor grupa în exact K subprobleme.

Intrare:

Fişierul de intrare popeala.in va conţine pe prima linie trei întregi pozitivi N, T, S, separaţi prin spaţiu. Linia a doua va conţine T numere întregi, separate prin spaţiu reprezentând elementele şirului Points[]. Următoarele N linii vor conţine fiecare un şir binar de lungime T, care reprezintă elementele matricei Results[][].

Iesire:

Fişierul de ieşire popeala.out va conţine S linii. A i-a linie trebuie să conţină un singur număr întreg: numărul total minim de puncte ce poate fi obţinut în concurs prin gruparea testelor în i subprobleme.

Restricţii si Precizari

  • 1 ≤ T ≤ 20.000
  • 1 ≤ N ≤ 50
  • 1 ≤ S ≤ min(50, T)
  • 1 ≤ Points[i] ≤ 10 000, oricare 1 ≤ i ≤ T. Se garantează că (Points(1) + Points(2) + … + Points(T)) * N ≤ 2 000 000 000 pentru toate testele.
  • Pentru teste în valoare de 8 puncte, T ≤ 40.
  • Pentru teste în valoare de alte 9 puncte, 40 < T ≤ 500.
  • Pentru teste în valoare de alte 9 puncte, 500
  • Orice codezi se poate folosi împotriva ta.

Exemplu

popeala.inpopeala.outExplicatie
2 3 3
4 3 5
101
110
0
8
16
Avem N = 2 concurenţi, T = 3 teste şi cel mult S = 3 ce înseamnă că trebuie să calculăm punctajul minim pentru 1, 2 şi respectiv 3 subprobleme. Şirul Points[] = {4, 3, 5}.
În cazul unei singure subprobleme, numărul total de puncte care poate fi obţinut este 0, deoarece niciun concurent nu a rezolvat corect toate cazurile şi toate testele trebuie să fie în aceeaşi subproblemă.
Sunt două modalităţi de a grupa testele în două subprobleme. Una dintre ele conduce la un total de 12 puncte iar cealaltă la un total de 8 puncte. Deoarece căutăm valoarea minimă, o vom alege pe a doua.
Este, de asemenea, o singură modalitate de a grupa testele în trei subprobleme, care conduce la un număr de 16 puncte.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?