루미 알고리즘

#1505실버Tebryggning

PO 2020 학교 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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?

Indata

Den första raden innehåller två heltal K och N (1 ≤ K ≤ 10, 1 ≤ N ≤ 100), antalet tepåsar Egon har och antalet programmeringsolympiadsdeltagare.

Den andra raden innehåller de K heltalen x_i (1 ≤ x_i ≤ 100), antalet personer som varje påse räcker till.

Det är garanterat att tepåsarna alltid räcker till N personer.

Utdata

Programmet ska skriva ut ett heltal: det minsta antalet tekannor Egon måste använda.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

FallPoängvärdeGränser
120K = 1
280Inga ytterligare begränsningar.

Förklaring av exempel

I det första exemplet 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 det andra exemplet ä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.

예제

예제 1

입력
3 36
23 5 17
출력
4

예제 2

입력
4 100
54 2 33 16
출력
11

출처 표기

출처: Programmeringsolympiaden 2020년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.