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 |