.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » dansatori

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
dansatori


Timp maxim de execuţie/test:
0.3 secunde
Memorie totala disponibilă/stivă:
16 MB/1 MB

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
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, accesibil, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, cladire, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor