Problem K
Två lådor
Kajsa ska köpa två lådor fyrverkerier till nyårsafton, men efter en påkostad julhelg har hon endast en budget på $B$ kronor kvar att spendera på fyrverkerierna. Kajsa vill dock inte snåla mer än nödvändigt, så hon vill köpa det par lådor som kommer närmast hennes budget utan att överskrida den. För att hitta detta par räknar hon ut vad den optimala (dyraste som får plats i budgeten samtidigt) andra lådan skulle vara för alla möjliga val av en första låda. Hjälp Kajsa att hitta vilka lådor hon ska köpa. Det är garanterat att det finns minst ett par lådor som inte överstiger Kajsas budget. Notera att Kajsa inte får köpa samma låda två gånger.
Indata
Den första raden indata består av två heltal $N$ och $B$ ($2 \leq N \leq 5 \cdot 10^5, 2 \leq B \leq 10^9$), antalet fyrverkerilådor i affären och Kajsas budget. Den andra och sista raden innehåller $N$ heltal $L_ i$ ($0 \leq i < N, 1 \leq L_ i \leq 10^9$), där $L_ i$ är priset för lådan med index $i$.
Utdata
Två heltal $i$ och $j$ ($0 \le i, j < N$, $i \neq j$), indexen för lådorna Kajsa ska köpa. Ifall det finns flera lösningar går det bra att skriva vilken som helst av dem.
Poängsättning
Din lösning kommer att testas på två olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
Grupp |
Poängvärde |
Begränsningar |
1 |
40 |
$N \leq 2000$ |
2 |
60 |
Inga ytterligare begränsningar |
Förklaring
Förklara sample
Sample Input 1 | Sample Output 1 |
---|---|
4 100 25 80 30 50 |
2 3 |
Sample Input 2 | Sample Output 2 |
---|---|
5 30 100 1 6 8 29 |
1 4 |