Pagini recente » Diferente pentru blog/agm-vi intre reviziile 5 si 4 | Diferente pentru problema/semipal intre reviziile 31 si 41 | Diferente pentru algoritmiada-2014/runda-2/11-12 intre reviziile 3 si 4 | Probleme "de formula" | Diferente pentru problema/zuma intre reviziile 5 si 4

Diferente pentru problema/zuma intre reviziile #5 si #4

Diferente intre #3 si #4

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="zuma") ==

Se dă un șir de caractere de lungime $N$ format din litere mari ale alfabetului englez și un număr întreg $K$.
Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin $K$ având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime $0$) sau șirul nu mai conține subsecvențe de lungime cel puțin $K$ cu toate elemente egale.

Se dă un șir de caractere de lungime N format din litere mari ale alfabetului englez și un număr întreg K.
Asupra șirului se poate aplica în mod repetat următoarea operație: se alege o subsecvență de lungime cel putin K având toate elementele egale și se elimină din șir. Evident că prima dată operația se aplică asupra șirului inițial și ulterior asupra șirului obținut din aplicarea operației anterioare. Operația se aplică până când șirul devine șirul vid (de lungime 0) sau șirul nu mai conține subsecvențe de lungime cel puțin K cu toate elemente egale.

h2. Cerință

Cunoscând $N, K$ și șirul de caractere, să se determine care este lungimea minimă la care poate fi redus șirul după aplicarea operațiilor într-un mod convenabil.

Cunoscând N, K și șirul de caractere, să se determine care este lungimea minimă la care poate
fi redus șirul după aplicarea operațiilor într-un mod convenabil.

h2. Date de intrare

Fișierul de intrare $zuma.in$ conține pe prima linie numerele $N$ și $K$ separate prin spațiu și pe a doua linie șirul de caractere format din $N$ litere mari.

Fișierul de intrare zuma.in conține pe prima linie numerele N și K separate prin spațiu și pe a
doua linie șirul de caractere format din N litere mari.

h2. Date de ieșire

În fișierul de ieșire $zuma.out$ trebuie să afișați un singur număr natural reprezentând lungimea minimă pe care o poate avea șirul după aplicarea în mod convenabil a operațiilor.

În fișierul de ieșire zuma.out trebuie să afișați un singur număr natural reprezentând lungimea minimă pe care o poate avea șirul după aplicarea în mod convenabil a operațiilor.

h2. Restricții

* $1 ≤ K ≤ N ≤ 500$
* Pentru teste în valoare de $10$ puncte $25 ≤ K ≤ N ≤ 100$
* Pentru alte teste în valoare de $10$ puncte $K = 2$
* Pentru alte teste în valoare de $10$ puncte numărul de caractere distincte din șir este $2$
* Pentru alte teste în valoare de $15$ puncte $1 ≤ N ≤ 50$
* Pentru alte teste în valoare de $35$ puncte $1 ≤ N ≤ 200$

• 1≤K≤N≤500
• Pentru teste în valoare de 10 puncte 25 ≤ K ≤ N ≤ 100
• Pentru alte teste în valoare de 10 puncte K = 2
• Pentru alte teste în valoare de 10 puncte numărul de caractere distincte din șir este 2
• Pentru alte teste în valoare de 15 puncte 1 ≤ N ≤ 50
• Pentru alte teste în valoare de 35 puncte 1 ≤ N ≤ 200

h2. Exemplu

infoarena informatica de performanta

Diferente pentru problema/zuma intre reviziile #5 si #4

Nu exista diferente intre titluri.

Diferente intre continut:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.