루미 알고리즘

#1333플래티넘Fotografen

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

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

Problem

En fotograf har tagit många fina foton med sin digitalkamera och kopplar in den i sin dator för att överföra bilderna. Bilderna har tagits med olika vridningar av kameran så nu är vissa av bilderna roterade. Vi kallar de fyra möjliga rotationerna ett foto kan ha för upp, höger, ner och vänster och definierar det som den sida som motsvarar uppåt i bilden. En bild är vänd rätt om den är roterad upp. Datorn visar bilderna i en lista och har en funktion som roterar en bild 90° medurs. Rotationen sker alltså enligt följande ordning:

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Hur en bild roteras

Fotografen tycker det verkar tråkigt att rotera foton och bestämmer sig för att göra det till ett roligt spel. Fotografen väljer ett positivt heltal k och bestämmer att det enda sättet att rotera foton är att markera exakt k intill varandra liggande foton ur listan och rotera alla dessa samtidigt. Formellt har fotografen N foton, kalla dem a_1, a_2, … a_N. Fotografen kan nu välja ett index i (1 ≤ i ≤ N-k+1) och bilderna a_i, a_{i+1}, ..., a_{i+k-1} roteras då 90° medurs. Detta kallar vi en operation.

Målet med spelet är att vända alla foton rätt med så få operationer som möjligt. Skriv ett program som beräknar det minsta antalet operationer som krävs.

Indata

På första raden står två heltal N och k (1 ≤ k ≤ N ≤ 4 · 10 ^5), antalet foton totalt respektive antalet foton som måste roteras samtidigt.

På andra raden står N tecken som representerar fotografiernas rotation från början: U för upp, H för höger, N för ner och V för vänster.

Utdata

Skriv ut det minsta antalet operationer som krävs. Om det inte går att vända alla foton rätt, 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ängGränser
110N ≤ 10
240N ≤ 5000
350Inga ytterligare begränsningar.

Förklaring av exempelfall 1

En möjlig optimal lösning är denna: Rotera tre gånger på position 3-4 för att få UVVU, rotera sedan en gång på position 2-3 för att slutligen få UUUU, och vi är klara med fyra operationer utförda.

예제

예제 1

입력
4 2
UVUH
출력
4

예제 2

입력
8 5
HUNVVNVH
출력
9

예제 3

입력
5 2
UUUUV
출력
-1

출처 표기

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