Finále

C: Klub boháčů

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích. Pokud si myslíš, že bys finalistou být měl, kontaktuj organizátory.

Zadání (Řešení)

Klub boháčů dospěl při svém XXVI. zasedání ke vskutku překvapujícímu zjištění – členové se nad sebe povyšovali, protože jeden byl bohatší než druhý.

Vrchní boháč by tomuto chtěl zabránit (a zároveň by chtěl získat veřejnost na svou stranu). Proto rozhodl, že každý den se vybraný boháč demonstrativně zbaví půlky svých peněz a vyhodí je z okna.

Neboť všichni členové klubu rádi ukazují své jmění, mají všechny své peníze pouze v jednodolarovkách. Pokud boháč vlastní lichý počet dolarů a má vyhodit polovinu svého majetku, vrchní boháč rozhodne, co se s posledním dolarem stane – zda si ho boháč nechá, nebo ho vyhodí.

Vrchní boháč ale nechce, aby toto vyhazování trvalo příliš dlouho, takže by ho zajímalo, za jaký nejmenší počet dní můžou mít všichni boháči stejné jmění.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku číslo N, počet boháčů. Na dalším řádku je N čísel; i-té z nich je číslo B_i, jmění i-tého boháče v dolarech.

Pozor: V těžké verzi se čísla B_i nemusí vejít do 32-bitové proměnné (typ int v C++), použijte 64-bitovou (typ long long int v C++).

Tvar výstupu

Za každý problém vypište jeden řádek s nejmenším počtem dnů, v nichž lze jmění všech boháčů vyrovnat. Při dělení lichého počtu dolarů můžete vždy zvolit možnost, která je pro vás výhodnější.

Lehká verze

  • 1 \leq T \leq 10
  • 2 \leq N \leq 100
  • 1 \leq B_i \leq 10^4

Těžká verze

  • 1 \leq T \leq 10
  • 2 \leq N \leq 100
  • 1 \leq B_i \leq 10^{12}

Ukázkový vstup

2
3
19 10 41
4
42 42 42 42

Ukázkový výstup

3
0

Vysvětlení ukázkového vstupu a výstupu

V prvním problému musí první boháč vyhodit z okna 9 dolarů, a třetí boháč postupně 21 a 10 dolarů, jsou tedy potřeba tři dny.

V druhém problému mají všichni boháči už na začátku stejně, takže není potřeba nic vyhazovat.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)