Diferente pentru problema/slide intre reviziile #6 si #9

Nu exista diferente intre titluri.

Diferente intre continut:

Calendarul competiţional al Algoritmiadei are $N$ ore şi este reprezentat printr-un şir format din $N$ caractere de tipurile $'#'$, $'@'$ şi $'.'$. Poziţiile marcate cu $'#'$ şi $'@'$ în şir reprezintă ore în care se ţin rundele de Algoritmiada, o rundă fiind reprezentată printr-o subsecvenţă de lungime maximală de caractere de acelaşi tip. Poziţiile marcate cu $'.'$ reprezintă ore libere. De exemplu, şirul $"###..@@#..##"$ reprezintă un calendar cu $12$ ore şi $4$ runde de concurs (în intervalele $[1, 3], [6, 7], [8, 8], [11, 12)]$).
Vechea interfaţă infoarena permite decalarea rundelor; din nefericire, o decalare reprezintă mutarea unei runde cu o oră în plus sau în minus (aceasta păstrându-şi lungimea), cu condiţia ca după decalare să nu se suprapună cu o altă rundă. De notat că începutul şi/sau sfârşitul unei runde *pot să se afle în afara celor $N$ ore din reprezentarea iniţială* după una sau mai multe decalări. De exemplu, pentru calendarul $"##..@."$, prima rundă poate fi decalată cu două ore în plus, obţinând calendarul $"..##@."$, dar şi cu două ore în minus, obţînând calendarul $"##....@"$. Pentru calendarul $"##@"$ nu putem decala prima rundă cu o oră în plus, *decât dacă întâi decalăm a doua rundă* cu o oră în plus.
Vechea interfaţă infoarena permite decalarea rundelor; din nefericire, o decalare reprezintă mutarea unei runde cu o oră în plus sau în minus (aceasta păstrându-şi lungimea), cu condiţia ca după decalare să nu se suprapună cu o altă rundă. De notat că începutul şi/sau sfârşitul unei runde *pot să se afle în afara celor $N$ ore din reprezentarea iniţială* după una sau mai multe decalări. De exemplu, pentru calendarul $"##..@."$, prima rundă poate fi decalată cu două ore în plus, obţinând calendarul $"..##@."$, dar şi cu două ore în minus, obţinând calendarul $"##....@"$. Pentru calendarul $"##@"$ nu putem decala prima rundă cu o oră în plus, *decât dacă întâi decalăm a doua rundă* cu o oră în plus.
Notăm cu $T(i)$ numărul minim de decalări necesare pentru ca ora $i$ din reprezentarea iniţială să devină liberă. Calculaţi $S = T(1) + T(2) + ... + T(N)$!
table(example). |_. slide.in |_. slide.out |_. Explicaţie |
| #@##..@
| 7
| T(1) = 1 (decalăm prima rundă cu o oră în minus), T(2) = 2 (decalăm prima rundă cu o oră în minus şi apoi a doua rundă cu o oră în minus), T(3) = 1, T(4) = 2 (decalăm a treia rundă cu două ore în plus), T(5) = 0, T(6) = 0, T(7) = 1. |
| T(1) = 1 (decalăm prima rundă cu o oră în minus), T(2) = 2 (decalăm prima rundă cu o
 oră în minus şi apoi a doua rundă cu o oră în minus), T(3) = 1, T(4) = 2 (decalăm a treia
 rundă cu două ore în plus), T(5) = 0, T(6) = 0, T(7) = 1. |
| #@.####@#@
| 23
| ... |

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.