~/algor $ cat masalalar/ochkoz-qayiqlar
Greedy-04
Daryodan o'tish
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
56%
$n$ kishi daryodan o'tishi kerak; $i$-kishining vazni $w_{i}$. Har bir qayiq ko'pi bilan ikki kishini oladi va ularning umumiy vazni $C$ dan oshmasligi kerak. Hammani o'tkazish uchun eng kamida nechta qayiq kerakligini aniqlang.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita natural son: $n$ va $C$. Ikkinchi qatorda bo'sh joy bilan ajratilgan $n$ ta natural son $w_{i}$.
Chiquvchi ma'lumotlar
Bitta butun son — qayiqlarning eng kam soni.
Izoh
$1 \le n \le 10^{5}$
$1 \le w_{i} \le C \le 10^{9}$
Misollar
Kirish #1
4 100 60 40 70 30
Chiqish #1
2
Kirish #2
3 50 50 50 50
Chiqish #2
3