Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

123

Adăugată de :
sorynsoo
Sursă :
XOR2010
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
2048 kbytes

Se consideră numerele naturale n, k şi p şi un şir de n numere din mulţimea {1, 2, 3}. Acest şir îl împărţim în mai multe secvenţe de lungime cel mult k astfel încât, dacă în fiecare secvenţă notăm cu a1 numărul de valori de 1, cu a2 numărul de valori de 2 şi cu a3 numărul de valori 3, atunci să fie îndeplinite condiţiile (unde prin |x| am notat modulul lui x):

  • |a1 – a2| <= p cu condiţia ca a1 şi a2 să fie strict pozitive
  • |a2 – a3| <= p cu condiţia ca a2 şi a3 să fie strict pozitive
  • |a1 – a3| <= p cu condiţia ca a1 şi a3 să fie strict pozitive

De exemplu, pentru n=13, k=8, p=1, şirul 1,2,1,1,2,3,3,2,2,2,1,1,3 il putem împărţi în două secvenţe: 1,2,1,1,2 şi 3,3,2,2,2,1,1,3. În prima secvenţă a1=3, a2=2, a3=0 şi |a1 – a2| <= 1, iar celelalte două module nu se vor calcula, pentru că a3 este 0. În secvenţa a doua, a1=2, a2=3, a3=3 şi deci diferenţa în modul dintre oricare două este mai mică sau egală cu 1.

Împărţirea în secvenţe nu este unică. Şirul din exemplul de mai sus se poate împărţi şi în 3 secvenţe de lungime cel mult k. Prima: 1,2,1,1,2,3,3, a doua:  2,2,2,1,1 şi a treia: 3

 

Cerinţa

Scrieţi un program care împarte şirul într-un număr minim de secvenţe de lungime cel mult k astfel încât fiecare secvenţă să respecte condiţiile.

 

Date de intrare

Fişierul de intrare conţine pe prima linie numerele n, k şi p separate printr-un spaţiu. Pe linia a doua se află şirul de n valori din mulţimea {1, 2, 3}, valori scrise fără spaţiu între ele.

 

Date de iesire

Fişierul de iesire va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul minim de secvenţe în care se poate împărţi şirul.

 

Restricţii şi precizări

  • 2 <= n <= 10 000,  1 <= p <= 100,  1 <= k <= 100

 

Exemple

  Date de intrare

  Date de iesire

  Explicaţie

  13 8 1

  1211233222113

  2

  Împărţirea se poate face astfel:

  12112 şi 33222113

  Date de intrare

  Date de iesire

  Explicaţie

  13 12 1

  1111222213133

  2

  Împărţirea se poate face astfel:

  111 şi 1222213133

  Date de intrare

  Date de iesire

  Explicaţie

  7 7 2

  3333333

  1

  Şirul formează o singură secvenţă care îndeplineşte condiţiile cerute

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Programare dinamica


Comentarii

Adauga un comentariu: Click !