시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 32 | 22 | 20 | 68.966% |
Egon ska brygga massor av te till $N$ programmeringsolympiadsdeltagare. Han har $K$ påsar te, alla av olika sorter. Påse $i$ har te för $x_i$ personer. Det är garanterat att påsarna sammanlagt räcker till minst $N$ personer.
Egon tänker använda bryggkannor som har plats för te till maximalt 10 personer. Eftersom påsarna är av olika sort går det inte att blanda flera påsar i samma kanna. Dock kan samma påse användas till flera kannor. Hur många kannor måste Egon använda?
På den första raden står två heltal $1 \le K \le 10$ och $1 \le N \le 100$ -- antalet tepåsar Egon har och antalet programmeringsolympiadsdeltagare. På den andra raden står $K$ heltal $1 \le x_1, x_2, \dots, x_K \le 100$, antal personer som varje påse räcker till.
Programmet ska skriva ut ett heltal: det minsta antalet tekannor Egon måste använda.
3 36 23 5 17
4
4 100 54 2 33 16
11
I exempel 1 väljer Egon att brygga två kannor med första tepåsen och två kannor med tredje tepåsen. Det ger $20+17$ koppar te, vilket räcker till de 36 deltagarna.
I exempel 2 är det optimala att brygga sex kannor med första tepåsen, tre kannor med tredje tepåsen och två med den fjärde tepåsen. Det ger $54+30+16$ koppar te, vilket räcker till de 100 deltagarna.
Olympiad > Swedish Olympiad in Informatics > 2020 > Qualification 2번