Återuppfinnande av matematiken
Ånej, all matematik har gått upp i rök! Hur gick det här till? Du hinner inte fundera över saken, utan inser att du måste återuppfinna så mycket matematik som möjligt innan världen går under! Även om all faktisk kunskap försvunnit så vet du lite om matematiken. Matematiken är uppbyggd av $N$ satser. Varje sats, $i$, beror på ett antal satser $a_{i_1}, a_{i_2}, \cdots , a_{i_ k} < i$, som måste bevisas innan man kan börja med satsen. För att visa sats $i$ måste du spendera $t_ i$ tid. Värdet av en visad sats är $v_ i$.
Du har $T$ tid på dig. Välj vilka satser du ska bevisa för att maximera det totala värdet av matematiken du hinner återuppfinna.
Indata
Den första raden innehåller ett heltal $C$ ($0 \leq C \leq 10$), numret på testfallet ($0$ är exempelfallet nedan).
Den andra raden innehåller två heltal: $N$ ($1 \le N \le 10^5$) och $T$ ($1 \le T \le 10^7$)
Därefter följer $N$ beskrivningar av satser. En beskrivning av en sats består av två rader. Först kommer en rad med tre heltal: $0 \le t_ i \le 10^4$, $0 \le v_ i \le 10^4$, $0 \le k_ i \le N$. Därefter kommer en rad med $k_ i$ heltal: $a_{i_1}, a_{i_2}, \cdots , a_{i_ k} < i$ – indexen på satserna som måste bevisas innan den här satsen. Satserna är indexerade från 0 i ordningen de kommer i input.
Utdata
Skriv först ut en rad med ett tal $S$ ($0 \le S \le N$), antal satser du ska bevisa. Skriv därefter ut en rad med $S$ heltal, satserna du bevisar i ordning du bevisar dem.
Poängsättning
Ditt program kommer att testas på $10$ testfall, och poängsättas baserat på hur det står sig relativt domarnas lösning. Om din inskickning på ett givet testfall uppnår ett totalt värde av satser $X$, och totala värdet domarna uppnått på det testfallet är $Y$, så blir din poäng på det testfallet $10 \cdot (X / Y)^3$, avrundat till två decimaler.
Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.
Din lösning kan maximalt få $100$ poäng, även om den är bättre än den domarna skrivit.
Exempeltestfallet kommer alltid att ge $0$ poäng.
Testfall
Till höger kan ladda ned testfall som är genererade på samma sätt som de riktiga testfallen, men med annat slumpseed.
Här är beskrivningar av de $10$ testfallen som förekommer.
|
Testfall |
Gränser |
|
$1$ |
$N=500,T=5000,k_ i \le 3$ |
|
$2$ |
$N=500,T=5000,k_ i \le 30$ |
|
$3$ |
$N=500,T=50000,k_ i \le 3$ |
|
$4$ |
$N=500,T=50000,k_ i \le 30$ |
|
$5$ |
$N=10^5,T=10^7,k_ i \le 3$ |
|
$6$ |
$N=10^5,T=10^7,k_ i \le 30$ |
|
$7$ |
$N=300,T=30000$ och $k_ i=1$ för alla $i\neq 0$ |
|
$8$ |
$N=300,T=30000$ och varje sats krävs för att bevisa max 1 annan sats. |
|
$9$ |
$N=10^5,T=10^7$ och $k_ i=1$ för alla $i\neq 0$ |
|
$10$ |
$N=10^5,T=10^7$ och varje sats krävs för att bevisa max 1 annan sats. |
| Sample Input 1 | Sample Output 1 |
|---|---|
0 5 11 1 1 0 2 7 1 0 4 2 1 0 5 1 1 0 1 10 2 2 3 |
4 0 2 3 4 |
