스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Grupp | Poäng | Gränser |
|---|---|---|
| 1 | 10 | N ≤ 10 |
| 2 | 40 | N ≤ 5000 |
| 3 | 50 | Inga 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