루미 알고리즘

#1484플래티넘Björnes magasin

PO 2020 결선코딩출제 Hugo Eberhard스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Som bekant går björnar i ide under vintern. Men vid ekvatorn blir det inte mörkt och kallt under vintern, så sedan en björnfamilj för många år sedan flyttade söderut har björnarna i björnsamhället som uppstått börjat gå i ide vid helt olika tidpunkter under året. Björne har öppnat ett magasin och är orolig för tjuvar under den del av året då han själv sover. Han ska därför anställa andra björnar så att det alltid är någon av de anställda som är vaken och kan vakta magasinet.

Totalt är det N björnar som sökt jobbet. Varje björn går i ide någon viss dag på året för att sova exakt d dagar i sträck, och kan inte jobba under någon av dessa dagar. Hur många björnar behöver Björne som minst anställa, givet att Björne kommer vakta sitt magasin själv när han är vaken?

Räkna med att varje år har 365 dagar (björnar som bor vid ekvatorn bryr sig inte om skottår), och att:

  1. januari har 31 dagar,
  2. februari har 28 dagar,
  3. mars har 31 dagar,
  4. april har 30 dagar,
  5. maj har 31 dagar,
  6. juni har 30 dagar,
  7. juli har 31 dagar,
  8. augusti har 31 dagar,
  9. september har 30 dagar,
  10. oktober har 31 dagar,
  11. november har 30 dagar och
  12. december har 31 dagar.

Indata

Första raden innehåller två heltal N och d (2 ≤ N ≤ 10^5, 1 ≤ d ≤ 364), antalet björnar (inklusive Björne), samt antalet dagar varje björn sover.

De följande N raderna innehåller dagarna då respektive björn går i ide. De anges på formen dd/mm.

Första björnen som anges är Björne själv.

Utdata

Skriv ut en rad med ett heltal, det minsta antalet björnar som Björne måste anställa.

Om det inte går att vakta magasinet alla dagar, skriv ut -1.

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.

GruppPoängvärdeGränser
130N ≤ 15
240d ≤ 182
330Inga ytterligare begränsningar.

예제

예제 1

입력
5 31
01/01
15/12
03/07
06/11
17/09
출력
1

예제 2

입력
12 303
01/01
01/02
01/03
01/04
01/05
01/06
01/07
01/08
01/09
01/10
01/11
01/12
출력
5

예제 3

입력
6 100
17/05
05/07
13/04
29/06
02/05
29/04
출력
-1

출처 표기

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