Vasile este instructor la o şcoala de dans. El pregăteşte un dans special în care dansatorii trebuie să fie aliniaţi pe două rânduri ca în figură:
Observaţi că între perechile de dansatori distanţele sunt egale, iar dansatorii din pereche sunt aşezaţi faţă în faţă, pe rânduri diferite.
Prima pereche trebuie să fie poziţionată la marginea din stânga a scenei, iar ultima pereche în marginea din dreapta a scenei.
La sfârşitul dansului precedent, dansatorii sunt aşezaţi arbitrar pe un singur rând, cel din faţa scenei.
Problema pe care o are Vasile este să deplaseze dansatorii pe poziţiile lor corecte pentru dansul special. Fiind şi programator, Vasile doreşte să deplaseze dansatorii astfel încât distanţa totală parcursă să fie minimă.
Cerinţă
Scrieţi un program care să determine distanţa totală minimă pe care trebuie să se deplaseze dansatorii pentru a se pregăti pentru dansul special.
Date de intrare
Fişierul de intrare dansatori.in conţine pe prima linie numărul natural par N, reprezentând numărul de dansatori. Pe cea de a doua linie se află două numere naturale separate prin spaţiu Lg D, unde Lg reprezintă lungimea scenei exprimată în metri, iar D distanţa dintre rândurile de dansatori, exprimată de asemenea în metri. Pe următoarele N linii sunt descrise poziţiile dansatorilor. Pe linia i+2 este scris un număr natural care reprezintă distanţa exprimată în metri dintre poziţia în care se află iniţial dansatorul i şi marginea din stânga a scenei.
Date de ieşire
Fişierul de ieşire dansatori.out va conţine o singură linie pe care va fi scris un număr real care reprezintă distanţa totală minimă pe care trebuie deplasaţi cei N dansatori astfel încât să fie aşezaţi corect pentru dansul special.
Restricţii
- 4 ≤ N ≤ 2000
- 1 ≤ Lg ≤ 10000
- 1 ≤ D ≤ 20
- Dansatorii sunt consideraţi punctiformi.
- Rezultatul afişat va fi consdierat corect dacă diferenţa în valoare absolută dintre rezultatul afişat şi cel corect este <0.0001.
Exemple
| dansatori.in | dansatori.out |
| 4 10 1 1 0 10 10 |
2.4142135624 |
| prof. Marinel Serban |
| Liceul de Informatică „Grigore Moisil” Iaşi |
| marinel_serban@yahoo.com |