Kanui
Na izletu je N učenika i znamo masu svakog. U kanu stanu najviše dva učenika, a njihova ukupna masa ne smije biti veća od W. Koliko najmanje kanua treba?
- Ulaz
U prvom retku N i W. U drugom retku N masa.
- Izlaz
Najmanji broj kanua.
- Ograničenja
1 ≤ N ≤ 100 000, svaka masa je od 1 do W, W ≤ 10⁹
Primjer 1
Ulaz
4 100 80 50 30 20
Izlaz
2
Primjer 2
Ulaz
3 10 9 8 7
Izlaz
3
Zapeo si?
Prvo pokušaj sam. Savjeti se otvaraju jedan po jedan, svaki otkriva malo više.
Sortiraj mase. S kim je najbolje upariti najtežeg?
Dva pokazivača: jedan na lakšem kraju, drugi na težem.