Intergalaktički konflikt 2

Interfejs

Pošaljite jedan C++23 izvorni fajl koji implementira sledeći interfejs:

long long Konflikt(int N, int M, int* A, int* B);

Tekst zadatka

О, не! Започео је већ други по реду конфликт између Нишоваца и Марсоваца! Овог пута су се умешали и пацифистички оријентисани Баки и Хепију, староседаоци Ташкента, којима су ови конфликти већ дојадили и желе што пре да га спрече. Помозите Бакију и Хепију да окончају Интергалактичке конфликте једном за свагда тако што ћете предвидети план напада Марсоваца! Овог пута се битка одвија у "Спољашњем Ободу" на планети Ташкент која се може представити као дуж дужине . У битци учествује M

N Нишоваца и Марсоваца. Сваки од учесника битке се на почетку налази на некој целобројној тачки дужи N . {0, 1, … M − 1}

Могуће је да више учесника битке буде на истој тачки. На почетку позиција -тог Марсовца је а позиција -тог Нишовца је . i A[i] i B[i]

Марсовци поседују колективну способност телепортације коју могу искористити једном пре почетка напада. Марсовци бирају број X

из скупа {0, 1, … M − 1} након чега ће позиција -тог Марсовца постати i . Након тога сваки од A[i] := (A[i] + X) mod M

Марсоваца напада тачно једног Нишовца и никоја два Марсовца не нападају истог Нишовца. Сваки Марсовац може да се креће по Ташкенту тако што ако је тренутно на позицији може да се помери на позицију X или(X − 1) mod M и тиме (X + 1) mod M

прелази дистанцу . У општем случају, ако Марсовац жели да пређе са позиције на позицију минимална дистанца коју мора да 1 p q

пређе ће бити једнака . Марсовци ће напасти тако што ће изабрати напад у коме укупна дистанца коју сви min(|p − q|, M − |p − q|)

Марсовци пређу заједно буде минимална. Ваш задатак је да израчунате колика је укупна дистанца коју ће сви Марсовци прећи. Описи функција Потребно је да имплементирате функцију Konf likt(N , M , A[…], B[…])

Ова функција ће бити позвана једном по примеру. Број представља број Нишоваца и број Марсоваца. Број представља величину N M

дужи Ташкента. Низ представља позиције Марсоваца на почетку. Низ представља позиције Нишоваца на почетку. Ова функција A B

треба да врати укупну дистанцу коју сви Марсовци пређу у нападу. Сви низови су индексирани од 1. Пример Нека је , N = 3 , M = 20 , A = {0, 6, 2} . Марсовци бирају B = {5, 19, 7} за телепортацију. Након тока позиције Марсоваца X = 1

постају . Први Марсовац ће напасти другог Нишовца и прећи дистанцу , други Марсовац ће напасти трећег Нишовца и прећи {1, 7, 3} 2

дистанцу и трећи Марсовац ће напасти првог Нишовца и прећи дистанцу . Укупна дистанца коју су Марсовци прешли у нападу је . Ограничења 0 2 4

1 ≤ N ≤ 5000 9 1 ≤ M ≤ 10

0 ≤ A[i] < M

Подзадаци 0 ≤ B[i] < M

Тест примери су подељени у подзадатка: [5 поена]: , 6

N ≤ 10 M ≤ 20

N ≤ 500 M ≤ 500

12 поена: A[i] < , M B[i] < M

[23 поена]: 4 4

N ≤ 500

[18 поена]: Укупна дистанца коју Марсовци пређу биће највише 4 и [30 поена]: Нема додатних ограничења 10 N ≤ 2000

Детаљи имплементације Потребно је да пошаљете тачно један фајл који имплементира поменуте функције. Осим тражених функција, ваш фајл konflikt.cpp може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке. Ваша функција мора бити следећег облика: long long Konflikt(int N, int M, int* A, int *B); Вашим програмима је дозвољено да мењају садржај низова али не смеју да приступају ван граница датих низова. Уз задатак, обезбеђен вам је "template" фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке: У првом реду број . У наредном реду бројева: . N N A[i]

У наредном реду бројева: N B[i] . Затим овај програм зове вашу функцију и исписује резултат који ваша функција врати. 