Diferențe pentru problema/centura între reviziile #3 si #13

Diferențe între titluri:

centura
Centura (Lot Juniori)

Diferențe între conținut:

== include(page="template/taskheader" task_id="centura") ==
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.
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.
h2. 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**.
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$].
h2. 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.
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.
h2. 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ț.
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ț.
h2. Restricții și precizări
* 1 ≤ k < n ≤ 100 000
* 1 < m30
* 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.
 
* $1 ≤ k < n100 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.$
h2. Exemplu
centura.in centura.out Explicaț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
centura.in centura.out Explicație
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
table(example).
|_. centura.in |_. centura.out |_. Explicație |
| 8 3 2
  CCAACACC
| 3 2
| $Sunt posibile următoarele trei variante de separare a coloanei inițiale de autovehicule:$
  $1. prin oraș: **A[~1~]**$
  $pe centură: **C[~1~]C[~2~]A[~2~]C[~3~]A[~3~]C[~4~]C[~5~]**$
  $2. prin oraș: **A[~2~]**$
  $pe centură: **C[~1~]C[~2~]A[~1~]C[~3~]A[~3~]C[~4~]C[~5~]**$
  $3. prin oraș: nici unul$
  $pe centură: **C[~1~]C[~2~]A[~1~]A[~2~]C[~3~]A[~3~]C[~4~]C[~5~]** (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ă: **C[~1~]C[~2~]A[~1~]C[~3~]C[~4~]A[~2~]C[~5~]** Prin urmare: **V = 1** și **T = 2**$
|
 
== include(page="template/taskfooter" task_id="centura") ==

Nu există diferențe între securitate.