루미 알고리즘

#1442플래티넘Vilse i tidtabellen

PO 2018 결선코딩출제 Oskar Werkelin Ahlin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Rakso är på semester i Duln för att titta på dyk-makron. Hon står vid en busshållplats och ska åka till sitt hotell "de nio". Det brukar alltid regna i Duln men idag är det isande kallt.

I glädjen att vara på semester, långt borta från sitt hem i den bedrövliga staden Stomholck, har Rakso totalt tappat tidsuppfattningen – hon vet inte vad klockan är. När hon tar upp sin jättesmarta fickdator för att ta reda på saken dör den – det är för kallt ute för att den ska fungera!

Men Rakso ger inte upp. Hon bestämmer sig för att ta reda på vad klockan är ändå. Till sin hjälp har hon:

  1. En tidtabell på väggen. Den visar vid vilka tider en buss anländer till hållplatsen hon står vid. Samma tidtabell gäller för alla dagar, och enbart en busslinje passerar stationen.
  2. En display som visar hur snart de kommande N bussarna anländer till hållplatsen.

Bussar kommer alltid exakt när de lovar (detta är ju inte Stomholck), och anländer bara vid hela sekunder. Just nu när Rakso observerar tidtabellerna och displayen är det också vid en hel sekund. Om en buss anländer precis just nu kommer den synas på displayen med värde 0.

Kan du hjälpa Rakso att skriva ett program som svarar på vad klockan är? Om det finns flera möjliga svar, så skriv ut alla. Om det inte finns någon giltig lösning (d.v.s. displayen måste visa fel), skriv ut "fel".

(Baserat på en verklig händelse. Rakso heter egentligen något annat.)

Indata

Den första raden innehåller två heltal N och M (1 ≤ N ≤ 10^6 , 1 ≤ M ≤ 3000). Den andra raden innehåller N tal: 0 ≤ t_i ≤ 10^9, den i:te tiden till nästkommande buss som visas på displayen, i sekunder. Dessa garanteras komma i stigande ordning, och inga tider är samma.

De följande M raderna innehåller tiderna i tidtabellen i stigande ordning, på formatet hh:mm:ss (mellan 00:00:00 och 23:59:59). Tidtabellen kommer inte att innehålla några upprepade tider.

Utdata

Skriv ut en enda rad: möjligheterna för vad klockan kan vara, separerade med mellanslag. Tiderna ska vara sorterade i ökande ordning, och formateras på samma sätt som i indata.

Om det inte finns någon möjlighet alls för vad klockan kan vara, skriv ut "fel" (utan citattecken).

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
128N = 3, 3 ≤ M ≤ 10, ingen hänsyn behöver tas till att tolvslaget kan passeras.
2353 ≤ N ≤ M ≤ 1000
337Inga ytterligare begränsningar.

예제

예제 1

입력
3 4
17559 19562 27399
04:57:18
05:30:41
07:41:18
08:36:03
출력
00:04:39

예제 2

입력
2 3
1 2
00:00:02
00:00:03
00:00:04
출력
00:00:01

예제 3

입력
4 3
2 28802 57602 86402
00:00:01
08:00:01
16:00:01
출력
07:59:59 15:59:59 23:59:59

예제 4

입력
2 1
0 172800
01:23:45
출력
fel

출처 표기

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