루미 알고리즘

#1449다이아Rymdpromenad

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

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

Problem

Astronauten Gustav tjänstgör på en rymdstation bestående av n moduler ihopsatta i en cirkel så att modul 1 sitter ihop med modul 2, 2 med 3, o.s.v. (och modul n sitter ihop med modul 1). Avståndet mellan två närliggande moduler är 1. För att skapa en slags konstgjord gravitation roterar rymdstationen med konstant hastighet runt cirkelns mittpunkt.

Stationen har varit i rymden ett bra tag och det börjar bli dags att putsa utsidan av fönstren. Lotten har fallit på Gustav att göra detta. Det finns m fönster numrerade från 1 till m, där fönster nummer i sitter på modul nummer a_i. Av någon anledning måste fönstrena putsas i just den här ordningen. Den enda ingången och utgången till stationen finns vid modul 1.

För att ta sig mellan modulerna finns det en raketdriven fönsterhiss som går längs utsidan av stationen. Fönsterhissen kan bara färdas mellan närliggande moduler, och kan alltså inte ta några genvägar. Gustav vill välja en väg från modul 1, runt till alla fönstrena, och tillbaka till modul 1. Tyvärr finns det två problem: dels har hissen begränsat med bränsle, så Gustav måste välja en väg som minimerar avståndet han färdas. Dessutom påverkar hissens rörelser rymdstationens rotation, därför måste den färdas lika mycket medsols som motsols.

Hitta det minsta avståndet Gustav kan färdas så att han börjar vid modul 1, besöker alla fönster i rätt ordning, återvänder till modul 1, och färdas lika mycket motsols som medsols.

Indata

Den första raden innehåller två heltal n och m (3 ≤ n ≤ 10^5 , 1 ≤ m ≤ 10^5), antalet moduler och antalet fönster. Den andra raden innehåller m heltal, index på fönstren som ska putsas (1 ≤ a_i ≤ n).

Utdata

Skriv ut ett heltal, det minsta möjliga avståndet.

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
1103 ≤ n ≤ 10 , 1 ≤ m ≤ 10
2243 ≤ n ≤ 100 , 1 ≤ m ≤ 100
3191 ≤ m ≤ 1000
447Inga ytterligare begränsningar

Förklaring av Sample 1

Den optimala vägen att åka här är 1-2^*-3-4^*-3^*-4-5-6^*-5-4-3-2-1 (stjärnan betyder att ett fönster putsas).

Förklaring av Sample 2

I det här exemplet finns det först ett fönster på modul 1, som Gustav kan putsa utan att behöva åka någonstans. Sedan åker han till modul 2, putsar de tre fönstren som är där, och åker tillbaka.

예제

예제 1

입력
8 4
2 4 3 6
출력
12

예제 2

입력
5 4
1 2 2 2
출력
2

예제 3

입력
8 5
4 6 8 2 7
출력
16

출처 표기

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