루미 알고리즘

#1325플래티넘Summa summarum

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

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

Problem

Anders och Beatrice har varsin lista med heltal. Dessa två listor innehåller lika många tal. Anders har en dröm. Han har en dröm om att summan av alla tal i hans lista ska vara lika med summan av alla tal i Beatrices lista (för att det skulle göra henne imponerad). Anders har läst flera år på högskolan, så han vet att så inte alltid är fallet. Anders har dock en plan för att komma närmare sin dröm.

Anders vill se till att skillnaden mellan de två summorna är så liten som möjligt. Anders kan ta ett av talen i sin egen lista och byta ut mot ett av talen i Beatrices lista, när hon inte ser det. Observera att han endast vågar göra ett sådant byte, annars blir det för misstänkt.

Givet att han måste göra precis ett sådant byte, vilken är den minimala skillnad mellan summorna som Anders kan åstadkomma?

Indata

Den första raden innehåller heltalet N (1 ≤ N ≤ 10^5), antalet tal i Anders och Beatrices listor.

På andra raden följer en lista med N heltal som beskriver talen i Anders lista. På tredje och sista raden i indata följer en lista med N heltal som beskriver talen i Beatrices lista. För varje tal X i listorna i indata så gäller att -10^5 ≤ X ≤ 10^5.

Utdata

Skriv ut ett heltal: den minimala skillnaden mellan summorna av Anders och Beatrices listor, efter att Anders har utfört bytet som beskrevs ovan.

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
120N ≤ 1000
280Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Anta att Anders och Beatrices listor är [5,2,3,5,1] respektive [1,4,3,4,2]. Om vi tar en femma i den första listan och byter ut mot en fyra i den andra listan så kommer listorna innehålla exakt samma tal. Det innebär att båda summorna kommer vara 15, och vi svarar då 0.

예제

예제 1

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

예제 2

입력
2
1 3
2 2
출력
2

예제 3

입력
4
-6 -12 -2 -7
84 3 50 23
출력
5

출처 표기

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