| Fişierul intrare/ieşire: | partmin.in, partmin.out | Sursă | Science on 2021, baraj |
| Autor | Ionut Anghelina, Lucian Trepteanu | Adăugată de |  Ionut Anghelina •ionanghelina |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Partmin
Cum finalul semestrului se apropie, este momentul predării eseului la GCEA (Gândire Critică şi Etică Academică). Ca orice student conştiincios, ţi-ai pregătit cu atenţie eseul şi ai avut grijă să aibă exact limita minimă admisă. Înainte de corectare, însă, acesta va fi verificat cu ajutorul unui program Anti-Plagiat, iar în cazul în care acesta va detecta prea multe pasaje comune cu cele conţinute de surse publice, va trebui să repeţi materia.
Detectorul Anti-Plagiat funcţionează pe un principiu atipic. Pentru fiecare paragraf al textului, acesta va calcula un Scor de Identitate egal cu numărul subsecvenţelor palindromice conţinute de acel paragraf.
Scorul total de Identitate al lucrării va fi reprezentat de suma Scorurilor tuturor paragrafelor.
Astfel, pentru a minimiza şansele de a fi acuzat de plagiat pe nedrept, eşti interesat de modul optim de a-ţi împărţi lucrarea în paragrafe pentru ca Scorul de Identitate rezultat să fie minim posibil.
Una din multele condiţii ale eseului, însă, este că numărul de paragrafe al acestuia nu poate depăşi un număr prestabilit k, pentru a nu se pierde din coerenţa ideilor.
Astfel, dându-se n-lungimea eseului, k şi textul propriu-zis, să se afişeze pentru fiecare 1 ≤ i ≤ k Scorul minim de Identitate al textului dacă îl împărţim în i paragrafe.
Date de intrare
Fişierul de intrare partmin.in va conţine pe prima linie două numere naturale n şi k.
Pe cea de-a doua linie se va afla un şir de caractere, fără spaţii, format din litere mici ale alfabetului latin ce reprezintă textul eseului.
Date de ieşire
În fişierul de ieşire partmin.out se vor afla k linii.
Pe linia i a acestuia se va afişa un singur număr natural reprezentând costul minim de a împărţi eseul in i paragrafe.
Restricţii
- O subsecvenţă a unui şir este formată din caractere aflate pe poziţii consecutive în şir.
- Un paragraf al eseului trebuie să reprezinte o subsecvenţă nevidă a acestuia.
- Toate paragrafele sunt disjuncte, iar reuniunea lor este egală cu textul complet.
- k ≤ n pentru orice test.
- Pentru teste ce valorează 10 puncte: k ≤ n ≤ 100
- Pentru alte teste ce valorează 10 puncte: 2 ≤ n ≤ 1000 şi k=2
- Pentru alte teste ce valorează 10 puncte: k ≤ n ≤ 1000 şi toate caracterele şirului sunt egale.
- Pentru restul testelor k ≤ n ≤ 1000
Exemplu
| partmin.in | partmin.out |
|---|---|
| 5 2 axaxy | 7 5 |
Explicaţie
Dacă vom lăsa tot textul într-un singur paragraf, acesta va conţine subsecvenţele palindromice:
"a", "x", "a", "x", "y", "axa" şi "xax".
Pentru două paragrafe putem împărţi textul în: "ax" şi "axy" ce vor conţine doar cele 5 subsecvenţe palindromice formate dintr-un singur caracter.
