Domácí kolo

F: Volby

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

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Ve volbách do Galaktického senátu spolu soupeřilo N stran. Nyní jsou už všechny hlasy sečteny a je potřeba rozhodnout, jak mezi strany rozdělit M mandátů, o které se soutěžilo. To se dá udělat následujícím způsobem. Vyrobíme si tabulku o N sloupcích a M řádcích; její i-tý sloupeček bude odpovídat i-té straně a označíme-li počet hlasů pro tuto stranu ai, vepíšeme do onoho sloupečku postupně čísla ai / 1, ai / 2, ai / 3, ..., ai / M (viz obrázek).

Nyní se do tabulky M-krát podíváme a najdeme v ní vždy nejvyšší nezakroužkované číslo. Toto číslo následně zakroužkujeme a odpovídající straně přidáme jeden mandát.

Protože se posledních voleb zúčastnil rekordní počet stran, raději bychom do příště tento postup zautomatizovali, pomůžeš nám s tím?

Pozn. Tento způsob se používá např. v českém volebním systému a říká se mu d'Hondtova metoda.

Tvar vstupu

Na první řádce souboru je jedno přirozené číslo T – počet testovacích vstupů. Následuje T testů. V každém testu dostanete na prvním řádku dvě přirozená čísla: N – počet stran a M – počet mandátů. Na druhé řádce následuje N nezáporných celých čísel a1, a2, ..., an. Tato čísla reprezentují zisky hlasů jednotlivých stran. Můžeš se spolehnout na to, že každou stranu volil alespoň jeden člověk. Také pro všechna 1 ≤ i,j ≤ N a 1 ≤ p,q ≤ M platí, že ai / p ≠ aj / q. Tedy můžeš předpokládat, že postup, jak stranám přidávat mandáty, je jednoznačný.

Pozor! Ačkoliv máš zaručeno, že jsou jednotlivé podíly různé, rozdíl mezi nimi může být hodně malý. Chystáš-li se tento podíl uložit do datového typu s plovoucí desetinnou čárkou, doporučujeme použít co nejpřesnější (třeba v C++ dej přednost datovému typu double před typem float).

Tvar výstupu

Pro každý test vypiš na jednu řádku počet mandátů, které získaly jednotlivé strany.

Lehká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000
  • 1 ≤ ai ≤ 1 000 000

Těžká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 500 000
  • 1 ≤ M ≤ 500 000
  • 1 ≤ ai ≤ 100 000 000

Ukázkový vstup

1
3 4
100 36 42

Ukázkový výstup

2 1 1

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

Nejdříve přidělíme mandát první straně, protože získala nejvyšší počet hlasů. Dále máme 100 / 2 = 50, což je více než 36 i 42; i druhý mandát tedy přidělíme téže straně. Protože 100 / 3 = 33,33… už je menší než 36 i 42, poslední dva mandáty přidělíme zbylým dvěma stranám.

Máš na to!

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