Hide

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

Please log in to submit a solution to this problem

Log in