TowerHungarian
From CEOIWiki
|
July 12-19
|
[edit] Torony
Különböző méretű kockákból kell tornyot építeni. Nem lehet egy kisebb kockára sokkal nagyobb kockát tenni.
Bármely két kockát különbözőnek tekintünk akkor is, ha azonos a méretük.
Ismerjük N kocka méretét és egy D egész számot,amely azt jelenti, hogy az A kockát nem lehet a B kockára rakni, ha A oldalhossza nagyobb, mint B oldalhossza + D.
Szabályos toronynak azt nevezzük, ahol az N kockát úgy tesszük egymásra, hogy ilyen eset nem fordul elő.
[edit] Feladat
Írj programot, amely kiszámolja, hogy hány szabályos torony építhető! Mivel ez a szám nagyon nagy lehet, ezért az eredményt modulo 109 + 9 kell kiszámolni!
[edit] Bemenet
A bemenet első sorában 2 egész szám van, a kockák N száma és a D érték.
A második sor N egész számot tartalmaz egy-egy szóközzel elválasztva: a kockák oldalhosszait.
[edit] Korlátok
A bemenet minden száma legfeljebb 109.
N legalább 2.
70 pont szerezhető, amikor N legfeljebb 70.
Ezen belül 45 pont, amikor N legfeljebb 20.
Ezen belül 10 pont, amikor N legfeljebb 10.
30 pontot lehet szerezni olyan esetekre, amikor a szabályos tornyok száma legfeljebb 
.
Az utolsó 6 tesztesetben N nagyobb, mint 70. N-re nincs felső korlát, de van olyan megoldás, amely időlimiten belül fut.
[edit] Kimenet
A kimenet egyetlen sorába egy számot kell írni: a szabályos tornyok számát modulo 
!
[edit] Példák
input:
4 1 1 2 3 100
output:
4
Az első 3 kocka tetszőleges sorrendbe tehető, kivéve a 2,1,3 és a 1,3,2 sorrendet. Az alsó kocka csak a negyedik lehet.
input:
6 9 10 20 20 10 10 20
output:
36
20-as méretű kocka nem tehető 10-es méretűre. A 10-es méretűek 6-féle sorrendbe rendezhetők és a 20 méretűek is 6-félébe, emiatt a megoldás 6*6.
