루미 알고리즘

#1350골드Ståskrivbordet

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

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

Problem

Annas mamma klagar att hon sitter för mycket vid datorn varje dag. Nä detta ska Anna minsann ordna. Hon har bestämt sig för att stå upp vid datorn istället!

Men datorskärmen står för högt upp! Anna behöver komma upp exakt x centimeter av ergonomiska skäl. Hon har n plattor till sin hjälp. Genom att lägga ett antal av dem under vardera foten, så kan hon komma upp exakt x centimeter. Plattorna under höger fot måste alltså ha sammanlagd höjd x centimeter, och plattorna under vänster fot måste också ha sammanlagd höjd x centimeter. Vad är det minsta totala antalet plattor hon behöver?

Indata

Först kommer en rad med talen x och n (10 ≤ x ≤ 100, 2 ≤ n ≤ 20), hur många centimeter Anna måste lägga under varje fot respektive antalet plattor.

Därefter kommer en rad med n heltal h_i (1 ≤ h_i ≤ 100). Det kommer alltid att finnas en lösning.

Utdata

För att göra det svårare att gissa rätt svar, så ska du skriva ut två heltal n_1 och n_2, antalet plattor hon har under vardera fot. Skriv det minsta talet först, d.v.s. se till att n_1 ≤ n_2. Om det finns flera lösningar där totala antalet plattor är samma så kan du välja vilken som helst utav dem.

GruppPoängvärdeGränser
130n ≤ 12
270Inga ytterligare begränsingar.

예제

예제 1

입력
14 5
10 5 4 9 7
출력
2 2 

예제 2

입력
100 9
30 33 33 4 50 40 60 51 48
출력
2 4 

출처 표기

출처: Programmeringsolympiaden 2014년 학교 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.