Problem F
Chokladbollar
Bruno och Sofie är med i en matematikförening på deras gymnasieskola, och går till en mataffär för att köpa fika för deras föreningsmöte. När de var i mataffären såg de något helt makalöst: Chokladbollar för endast $2$ kr/st!!! Bruno och Sofie började genast att stoppa ner chokladbollar i var sin papperskasse, betala för chokladbollarna, och sedan återvända till skolan. När de återvände till skolan ville de fördela chokladbollarna mellan $N$ papperskassar jämnt så att antalet chokladbollar i alla $N$ påsar är så lika som möjligt, för att alla $N$ elever kan få varsin påse med chokladbollar. Chokladbollarna är jämnt fördelade i alla påsar ifall skillnaden av antalet chokladbollar mellan 2 valfria påsar aldrig överstiger 1.
För att få alla chokladbollar så jämnt fördelade mellan alla $N$ påsar som möjligt, kan Bruno och Sofie endast göra följande drag hur många gånger som helst: Flytta en chokladboll från sin egna påse till en annan påse.
Givet att det fanns $B$ chokladbollar i Brunos papperskasse, och $S$ chokladbollar i Sofies papperskasse, hur många chokladbollar behöver Bruno och Sofie minst förflytta för att antalet chokladbollar i alla $N$ påsar är så jämnt fördelat som möjligt? Alltså, vad är minsta antalet förflyttningar som behövs för att alla chokladbollar ska vara så jämnt fördelat i alla $N$ påsar som möjligt?
Notera att Brunos och Sofies papperskassar med chokladbollar även räknas med i de $N$ papperskassarna.
Indata
Första raden består av ett heltal, $N$ $(2 \leqslant N \leqslant 10^9)$. Andra raden består av två heltal, $B$ och $S$ $(0 \leqslant B,S \leqslant 10^9)$.
Utdata
Skriv ut ett heltal: det minsta antalet chokladbollar som behöver förflyttas totalt av Bruno och Sofie.
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.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$15$ |
$N=2$, $B+S \leqslant 10$ |
|
$2$ |
$15$ |
$N=3$, $B+S \leqslant 100$ |
|
$3$ |
$30$ |
$N \leqslant 10^3$ , $B+S \leqslant 10^3$ |
|
$4$ |
$20$ |
Det är garanterat att antalet chokladbollar går jämnt ut. Alltså att det kan finnas lika många chokladbollar i varje påse. |
|
$5$ |
$20$ |
Inga ytterligare begränsningar. |
Förklaring av sample 1
I första testfallet finns det endast 2 påsar, Brunos påse med 6 chokladbollar, och Sofies påse med 4 chokladbollar. För att det ska vara jämnt fördelat behöver Bruno endast flytta 1 chokladboll från sin påse till Sofies påse.
Förklaring av sample 2
I andra testfallet finns det 3 påsar. Från början är den tredje påsen tom. Men efter att Bruno har flyttat 2 chokladbollar från sin påse till den tomma påsen, kommer det till slut finnas 3 i Brunos påse, 3 i Sofies påse, samt 2 i den tredje påsen. På det sättet är även chokladbollarna så jämnt fördelat som möjligt, eftersom det inte går att fördela 8 choklad bollar på tre påsar ännu bättre än så.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 6 4 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 3 |
2 |
