Programozás‎ > ‎Feladatok‎ > ‎

Hangos tetszésnyilvánítás

Az operában új darab bemutatóját fogják adni, és a prima donna jó barátnőd. Nem Tudsz elmenni az előadásra, de szeretnéd, ha barátnődet hangos tetszésnyilvánítással (=mindenki állva tapsol) ünnepelnék a darab végén. 

Kezdetben minden néző ül. Minden nézőnek van egy szégyenlősségi szintje. A Si szégyenlősségi szintű néző csak akkor fog felállni, ha legalább Si néző már állva tapsol, akkor viszont rögtön is feláll, és csatlakozik a hangos tetszésnyilvánításhoz. Ha Si = 0, akkor a néző rögtön a darab végén állva tapsolni kezd. 

Tudod az összes néző szégyenlősségi szintjét, és elhatároztad, hogy meghívsz még néhány jó barátot, akik segítenek a vastaps beindításában. Az általad meghívottak szégyenlősségi szintjét te tudod meghatározni. Legkevesebb hány extra nézőt kell meghívnod a vastaps garantálásához? 

Feladat

Írjunk programot, ami megadja, hogy legalább zhány barát meghívásával garantálható a vastaps.

Bemenet

A bemenet első sora a tezstesetek T számát adja meg. T teszteset következik. Minden tesztesethez egy sor tartozik, amiben az első szám Smax a nézők között előforduló legmagasabb szégyenlősségi szint. Ezután egy Smax+1 hosszú karakterlánc következik, amiben a k-dik karakter azt adja meg, hogy hány néző szégyenlősségi szintje éppen k. (0-tól kezdődik a számozás.) Egy szégyenlősségi szinthez mindig 0 és 9 közé eső számú néző tartozik. 

A karakterlánc nem végződhet 0-ra. Ebből az is következik, hogy mindig van legalább egy néző. 

Kimenet

Minden tesztesethez kiírandó a minimálisan meghívandó extra vendégeg száma.

Méretek

1 ≤ T ≤ 100.
Kis bemenet: 0 ≤ Smax ≤ 6.
Nagy bemenet: 0 ≤ Smax ≤ 1000.

Példa

Bemenet  Kimenet
4
4 11111
1 09
5 110011
0 1
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 0


Tesztadatok

Címkék

A feladat forrása: Google Code Jam 2015, selejtező forduló
Algoritmusok: 

megoldás