루미 알고리즘

#1481실버Renoveringen

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

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

Problem

Johanna håller på att renovera hemma i sin lägenhet. Eftersom Johanna inte gillar att lämna saker åt slumpen har hon planerat in i detalj precis hur många spikar hon behöver under renoveringen. Totalt sett behöver hon N spikar med längderna x_1, x_2, …, x_N. I hennes spiklåda har hon M spikar av längderna y_1, y_2, …, y_M.

Om Johanna behöver en spik med längd x_i kan hon använda en spik med längd y_j om x_i ≤ y_j eftersom hon kan kapa av den längre spiken tills den är precis så lång som behövs. Däremot kan hon inte kombinera två korta spikar till en längre spik, eller kapa en spik flera gånger (den har ju bara ett spikhuvud).

Innan Johanna ska börja med renoveringen vill hon veta:

  • hur många spikar hon behöver köpa, och
  • vilka längder spikarna hon behöver köpa ska ha.

Hon vill köpa så få spikar som möjligt, och vill dessutom köpa spikar av så kort total längd som möjligt.

Indata

På den första raden står två heltal 1 ≤ N ≤ 15 och 1 ≤ M ≤ 15 – antalet spikar Johanna behöver och antalet spikar Johanna har. På den andra raden står N heltal 1 ≤ x_1, x_2, …, x_N ≤ 100, längderna på de spikar Johanna behöver. På den tredje raden står M heltal 1 ≤ y_1, y_2, …, y_M ≤ 100, längderna på de spikar Johanna har.

Utdata

Programmet ska först skriva ut ett heltal: det minsta antalet spikar Johanna behöver köpa. På nästa rad ska programmet skriva ut längderna på spikarna Johanna ska köpa, i stigande ordning.

Poängsättning

GruppPoängGränser
140Johanna behöver använda alla spikar hon redan har, och hon behöver dessutom inte behöver kapa någon av dessa.
260Inga ytterligare begränsningar.

Förklaring av exempel

I exempel 1 uppfyller behöver Johanna bara fylla på med tre extra spikar av längderna 13, 28 och 77.

I exempel 2 behöver Johanna köpa en till spik av längd 11, och dessutom kapa en spik av längd 100 till 50. Hon skulle kunnat köpa en spik av längd 50 och kapa spiken av längd 100 till längd 11, men då behöver hon köpa spikar av längre total längd.

예제

예제 1

입력
6 3
64 13 45 28 82 77
45 82 64
출력
3
13 28 77 

예제 2

입력
3 2
11 50 45
45 100
출력
1
11 

출처 표기

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