Domácí kolo

G: Virtuální realita

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

Každého pilota Mezinárodní Futuristické Flotily čeká výcvik ve virtuální realitě. Během výcviku jsou piloti rozděleni do N letek. Výcvik se skládá z R částí, přičemž se každé části může zúčastnit nejvýše K pilotů. Účast pilotů na jedné části výcviku se určuje takto: letky jsou seřazeny ve frontě a připraveny k výcviku. Jakmile se jedna letka dostane na řadu, zjistí, jestli se všichni její členové ještě do výcvikového střediska vejdou, a pokud ano, zaujmou svá místa. Když se na řadu dostane letka, na kterou už kapacita nevystačí, část výcviku začne. Po ukončení každé části se všechny letky zařadí na konec fronty ve stejném pořadí jako předtím.

Během každé části výcviku je pro každého účastníka této části vygenerováno hlášení, které je předáno generálu Kájovi. Kolik těchto hlášení se po R částech výcviku objeví generálu Kájovi na stole?

Tvar vstupu

Na prvním řádku souboru je číslo T – počet testovacích vstupů. Na prvním řádku každého testu je R – počet částí výcviku, K – počet pilotů, kteří se mohou najednou zúčastnit výcviku, a N – počet letek. Na dalším řádku následuje N celých čísel udávajících počty pilotů v jednotlivých letkách. Velikosti letek jsou udané v tom pořadí, v jakém stojí ve frontě (první číslo je velikost letky, která je ve frontě první). Neexistuje letka, která by měla více než K členů.

Tvar výstupu

Pro každý testovací výstup vypište na samostatný řádek, kolik hlášení bude generálu Kájovi za R částí výcviku předáno.

Lehká verze

  • T ≤ 20
  • R ≤ 1 000
  • K ≤ 100
  • N ≤ 10
  • Velikosti jednotlivých letek ≤ 10

Těžká verze

  • T ≤ 20
  • R ≤ 1012
  • K ≤ 105
  • N ≤ 1000
  • Velikosti jednotlivých letek ≤ K

Ukázkový vstup

3
4 6 4
1 4 2 1
100 10 1
1
5 5 10
2 4 2 3 4 2 1 2 1 3

Ukázkový výstup

21
100
20

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

V prvním případě máme čtyři části výcviku s kapacitou šesti pilotů. V první části se vejdou první dvě letky (třetí by už limit šesti míst překročila), které mají celkem 5 pilotů. Druhé části se zúčastní třetí, čtvrtá a první letka (4 piloti). Třetí části se zúčastní druhá a třetí letka, které dohromady přesně středisko naplní (6 pilotů). V poslední části se výcviku zúčastní čtvrtá, první a druhá letka, přičemž se využije opět celé středisko (6 pilotů). Máme tedy celkem 5+4+6+6=21 hlášení.

Ve druhém případě se jediná letka zúčastní každé ze 100 částí výcviku. Protože je v té letce pouze jeden pilot, dostane generál Kája 100 hlášení.

Ve třetím případě se první části zúčastní pouze první letka (druhá se už nevejde) o velikosti 2 pilotů. Druhou částí výcviku projde pouze druhá letka se 4 piloty. Třetí části se zúčastní třetí a čtvrtá letka, které dohromady naplní celou kapacitu střediska - 5 pilotů. Čtvrté části se účastní pouze pátá letka, která má 4 piloty. Poslední, páté části se budou účastnit šestá, sedmá a osmá letka, které mají dohromady 5 pilotů. Celkem tedy máme 2+4+5+4+5=20 hlášení.

Máš na to!

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