루미 알고리즘

#1429플래티넘Skidor

PO 2017 온라인 예선코딩출제 Aron Granberg, Måns Magnusson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Johan gillar att åka skidor. Då menar vi inte att åka slalom, vilket Johan nämligen är väldigt rädd för. Långfärdsskidor däremot, det är hans grej. När man åker långfärdsskidor måste man dock ha stora plana ytor.

Johan har undersökt ett stort rektangulärt område ute i skogen, som har ganska ojämn mark. Här vill Johan välja ut en viss kvadrat att åka runt på, som är tillräckligt stor för att göra skidåkningen intressant. Kvadraten ska ha exakt storlek L × L, och ha sidor parallella med områdets sidor.

Nu ber han dig hitta en sådan kvadrat. För att den ska passa bra för långfärdsskidor har han två krav. Dels får det inte finnas några träd i kvadraten, och dels ska höjdskillnaden mellan den högsta och den lägsta punkten i denna kvadrat vara så liten som möjligt.

Om det finns finns flera möjliga sådana kvadrater, ska du i första hand välja den som ligger längst norrut, d.v.s har lägst radnummer. Om det fortfarande finns flera möjliga ska du i andra hand välja den som ligger längst västerut, d.v.s. har lägst kolumnnummer.

Indata

Den första raden innehåller tre heltal R, C, L sådana att 1 ≤ R,C ≤ 1000, 1 ≤ L ≤ min(R,C). R är antalet rader i det stora området, C antalet kolumner, och L storleken på den sökta kvadraten.

Därefter följer R rader, en för varje rad i området. En rad innehåller C heltal, en för varje kolumn i området.

Det c:te talet på den r:te raden beskriver höjden H_rc på den punkten i området, som är sådan att sådana att -1 ≤ H_rc ≤ 10^9. Om H_rc = -1 finns det istället att det står ett träd på den platsen.

Utdata

Hitta r_l, c_l sådana att Johans kvadrat spänner över koordinaterna r_l ≤ r <r_l + L, c_l ≤ c < c_l + L. r_l och c_l ska vara 0-indexerade, exemplevis är r_l = 0 om den första raden (som ligger längst norrut) menas, och c_l = 0 om den första kolumnen (som ligger längst västerut) menas.

Det är garanterat att det finns en lösning.

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
1210 ≤ H_rc ≤ 1
236R,C ≤ 50
327R,C ≤ 300
416R,C ≤ 1000

예제

예제 1

입력
3 3 2
10 3 5
2 4 3
2 8 1
출력
0 1

출처 표기

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