Programozás‎ > ‎Feladatok‎ > ‎

Végtelen palacsintaház

A Végtelen Palacsintaházban véges sok palacsinta van, de végtelen sok vendég, akik szívesen megennék a palacsintákat. Amikor reggel kinyit az étterem, a végtelen sok vendég közül pontosan D előtt nem üres a tányér, a többieknek egyelőre nincs palacsintája. A D kitüntetett vendég közül az i-diknek Pi palacsinta jutott kezdetben. Mindenki másnak nulla. 

Normál esetben egy vendég percenként egy palacsintát eszik. Néha azonban a főpincér speciális pillanatot hirdethet. Ilyenkor egy percre mindenki félbehagyja az evést, és a pincér egy nem üres tányérból tetszőleges számú palacsintát átrakhat egy tetszőleges vendég tányérjába. 

A főpincér bármelyik percet speciálisnak nyilváníthatja, de az is lehet, hogy nem rendel el ilyen pillanatot. A speciális percek alatt pontosan egy vendégtől kerül át  valamennyi palacsinta egy másikhoz.

Akkor van vége a reggelinek, ha minden palacsinta elfogyott. 

Feladat

Írjunk programot, ami megadja, leghamarabb mikor lehet vége a reggelinek.

Bemenet

A bemenet első sora a tesztesetek T számát tartalmazza. Ezután T teszteset jön, mindegyikben D, a kezdetben palacsintát kapó vendég száma, majd D darab szám, az i-dik vendég palacsintáinak száma kezdetben. 

Kimenet

Minden tesztesethez a minimálisan szükséges percek számát kell kiírni.

Méretek

1 ≤ T ≤ 100.
Kis bemenet: 1 ≤ D ≤ 6. 1 ≤ Pi ≤ 9.
Nagy bemenet: 1 ≤ D ≤ 1000. 1 ≤ Pi ≤ 1000.

Példa

Bemenet  Kimenet
3
1
3
4
1 2 1 2
1
4		Case #1: 3
Case #2: 2
Case #3: 3

Tesztadatok

Címkék

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

megoldás