Domácí kolo

C: Koblihy

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í)

Tomáš má chuť na něco sladkého. Chce si usmažit koblihy, ale protože má velký hlad, rád by je měl všechny hotové co nejdříve.

Máme N koblih a každá z nich má přesně K stran, které je potřeba osmažit. Na Tomášově pánvičce se dá smažit M koblih najednou, přičemž se každá kobliha smaží vždy jen z jedné strany. Zajímá nás, jak lze nejrychleji osmažit všechny strany všech koblih. Usmažit jednu stranu trvá jednu minutu, navíc předpokládáme, že Tomáš umí vyměnit nebo přetočit vše najednou a okamžitě.

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 jednom řádku tři čísla: N udává počet koblih, K je počet stran, které je potřeba usmažit, a M je počet koblih, které se najednou vejdou na Tomášovu pánvičku.

Tvar výstupu

Pro každý problém vypište na samostatný řádek číslo udávající nejkratší čas, za který je možné osmažit všechny koblihy ze všech stran.

Lehká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 10 000
  • 1 ≤ K ≤ 100
  • 1 ≤ M ≤ 1000

Těžká verze

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 1 000 000 000
  • 1 ≤ K ≤ 1 000 000
  • 1 ≤ M ≤ 1 000 000

Ukázkový vstup

2
3 2 2
5 3 7

Ukázkový výstup

3
3

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

V prvním případě je optimální řešení nejdříve osmažit první a druhou koblihu z jedné strany, potom druhou z druhé strany a třetí z první strany, a nakonec první a třetí koblihu z druhé strany.

Druhý případ je odlišný tím, že se Tomášovi na pánvičku vejde víc koblih, než kolik jich má k dispozici, takže si bude muset počkat tři minuty, než se mu všechny koblihy osmaží ze všech tří stran.

Máš na to!

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