루미 알고리즘

#1515다이아Baka bullar

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

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

Problem

Du har bakat bullar och lagt dem på en lång rad. Totalt har du N bullar, där den i:te finns på x-koordinat x_i. Du skulle vilja samla ihop bullarna så att de ligger bredvid varandra, alltså på koordinater a, a+1, a+2, …, a+N-1 för något a. Men bullarna är väldigt varma och kan endast hanteras med hjälp av en spade med bredd D. I ett drag kan du välja ett intervall av längd D och vända på alla bullar i det intervallet. Mer specifikt kan du välja ett intervall på formen [L, L+D-1]. En bulle vars x-koordinat uppfyller L ≤ x_i ≤ L+D-1 flyttas då till x-koordinat L + D - 1 - (x_i - L).

Du får givet de N bullarnas positioner och talet D. Din uppgift är att hitta en sekvens av drag så att bullarna hamnar bredvid varandra. Du får använda högst 10^5 drag.

Indata

Den första raden innehåller två heltal N och D (2 ≤ N, D ≤ 200).

Den andra raden innehåller N heltal x_i (1 ≤ x_i ≤ 200). Alla talen x_i är olika.

Utdata

Om det inte finns någon lösning, skriv ut “-1”.

Annars, skriv först ut en rad med heltalet M (0 ≤ M ≤ 10^5), antalet drag. Skriv därefter ut M rader, där den i:te innehåller heltalet L_i.

Detta innebär att det i:te draget vänder på intervallet [L_i, L_i + D - 1]. Talet L_i får vara nästan (Heltalet måste uppfylla -2147483648 ≤ L_i ≤ 2147483647, annars får du fel svar.) vilket heltal som helst, inklusive negativt. Lösningen räknas som korrekt om bullarna ligger bredvid varandra efter att samtliga drag utförts. Ordningen på bullarna spelar ingen roll.

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=2
29D=2
314D=3
414N, D, x_i ≤ 5
524N, D, x_i ≤ 30
630Inga ytterligare begränsningar.

예제

예제 1

입력
4 4
1 7 2 8
출력
2
1
5

예제 2

입력
4 5
1 2 3 5
출력
-1

출처 표기

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