Fişierul intrare/ieşire:centura.in, centura.outSursăLot I Juniori 2016
AutorConstantin GalatanAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Centura (Lot Juniori)

Pe şoseaua care duce spre intrarea în oraş se află n autovehicule, dintre care m sunt autovehicule de gabarit redus, pe care le vom numi în continuare autoturisme, iar restul sunt de gabarit mare şi le vom numi camioane. Oraşul are o şosea ocolitoare, numită popular centură. Camioanele trebuie să ocolească oraşul trecând în mod obligatoriu pe drumul de centură. Autoturismele pot continua drumul pe şoseaua care intră în oraş sau pot ocoli oraşul intrând pe şoseaua de centură.
Pe centură, camioanele circulă cu viteză redusă îngreunând traficul. De aceea s-a impus restricţia R: nu vor fi admise pe drumul de centură coloane formate din mai mult decât k camioane consecutive.

Cerinţă

Cunoscând n, k şi distribuţia autovehiculelor pe şosea, să se determine două numere naturale V şi T, unde V reprezintă numărul de variante de dirijare a traficului astfel încât să fie respectată restricţia R, iar T reprezintă numărul minim de autoturisme care trebuie să fie deviate pe drumul de centură pentru a se respecta aceeaşi restricţie R.

Date de intrare

Fişierul de intrare centura.in conţine pe prima linie trei numere naturale nenule n m şi k. Pe următoarea linie un şir de caractere format doar din caracterele A şi C. Caracterul A reprezintă un autoturism, iar caracterul C reprezintă un camion.

Date de ieşire

Fişierul de ieşire centura.out va conţine numerele naturale nenule V şi T separate prin spaţiu, cu semnificaţia din enunţ.

Restricţii şi precizări

  • 1 ≤ k < n ≤ 100 000
  • 1 < m ≤ 30
  • Atenţie, dacă iniţial avem un şir de forma CCAAC şi k=2, atunci sunt două soluţii distincte pentru mersul pe centură: CCAC (primul A merge prin oraş) şi din nou CCAC (al doilea A merge prin oraş).
  • Se garantează că, pentru toate datele de test, şirul iniţial de autovehicule respectă restricţia R.

Exemplu

centura.incentura.outExplicaţie
8 3 2
CCAACACC
3 2
Sunt posibile următoarele trei variante de separare a coloanei iniţiale de autovehicule:
1. prin oraş: A1
pe centură: C1C2A2C3A3C4C5
2. prin oraş: A2
pe centură: C1C2A1C3A3C4C5
3. prin oraş: nici unul
pe centură: C1C2A1A2C3A3C4C5 (toate)
Este necesar ca minimum două autoturisme să fie deviate pe drumul de centură. Prin urmare: V = 3 şi T = 2
7 2 2
CCACCAC
1 2
Există o singură variantă: toate autovehiculele vor fi deviate pe drumul de centură: C1C2A1C3C4A2C5 Prin urmare: V = 1 şi T = 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici