루미 알고리즘

#1513다이아Blomsymmetri

PO 2021 훈련 캠프코딩출제 Fredrik Ekholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Fredrik har just ställt ut nya blommor på sin fönsterbräda. Men någonting känns lite fel. Det är inte riktigt så symmetriskt som han skulle vilja ha det.

Det finns K olika blomsorter och varje sort beskrivs av ett av heltalen 1,2,...,K. Fönsterbrädan har N blommor utställda på rad från vänster till höger. Den i:te blomman från vänster är av sort a_i. Fredrik vill att blommorna ska vara symmetriska, d.v.s att a_i=a_{N+1-i} gäller för alla i. För att åstakomma detta tänker han göra drag som byter plats på två intilliggande blommor. Ett drag kan alltså byta plats på blomma i och blomma i+1 för något 1 ≤ i ≤ N-1.

Vad är minsta antalet drag som krävs för att uppnå blomsymmetri?

Indata

Den första raden av indata innehåller två heltal N och K (1 ≤ N,K ≤ 200 000): antalet blomor på fönsterbrädan och totala antalet sorter som finns. Därefter följer en rad med N heltal a_1,a_2,...,a_N (1 ≤ a_i ≤ K): blommorna på fönsterbrädan.

Det garanteras att det finns en sekvens av drag som ordnar blommorna symmetriskt.

Utdata

Skriv ut ett heltal: det minsta möjliga antalet drag för att uppnå blomsymmetri.

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
19N ≤ 10, K ≤ 10
211N ≤ 20
313N ≤ 2000
417K ≤ 2
520N är jämn
630Inga ytterligare begränsningar

Förklaring av exempel

I det första exemplet kan vi börja med att byta plats på blomma 2 och 3, och sedan på blomma 1 och 2. Då kommer blommorna hamna i ordningen 1 3 3 1.

I det andra exemplet kan vi till exempel göra följande 5 byten i ordning: 4 och 5, 3 och 4, 1 och 2, 2 och 3, 7 och 8. Då kommer blommorna hamna i ordningen 1 2 3 1 1 3 2 1.

예제

예제 1

입력
4 5
5 5 2 2
출력
2

예제 2

입력
8 3
3 1 1 1 2 3 1 2
출력
5

예제 3

입력
7 3
1 3 2 1 2 2 2
출력
5

출처 표기

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