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éretek1 ≤ 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 | 
2004-2016 BDG algoritmus szakkör