Diferențe pentru problema/reducere între reviziile #2 si #7

Nu există diferențe între titluri.

Diferențe între conținut:

== include(page="template/taskheader" task_id="reducere") ==
Se dă o listă de $N$ puncte în plan prin coordonatele lor carteziene. Fiecare dintre aceste puncte are asociată o greutate notată $G[~P~]$ care inițial este [$1$]. Asupra listei de puncte se efectuează următorul tip de operație: se aleg două puncte diferite $A4 și $B$ și pe baza acestora se determină un al treilea punct $C$ cu caracteristicile:
$XC = (GA * XA + GB * XB) / (GA + GB)$
$YC = (GA * YA + GB * YB) / (GA + GB)$
$GC = GA + GB$
iar costul acestei operații este $GA * GB * Dist(A, B)$. Apoi se elimină din listă punctele $A$ și $B$ și se adaugă punctul [$C$]. Acest tip de operație se efectuează succesiv (de $N - 1$ ori) până când lista va conține un singur punct.
Se dă o listă de $N$ puncte în plan prin coordonatele lor carteziene. Fiecare dintre aceste puncte are asociată o greutate notată $G[~P~]$ care inițial este [$1$]. Asupra listei de puncte se efectuează următorul tip de operație: se aleg două puncte diferite $A$ și $B$ și pe baza acestora se determină un al treilea punct $C$ cu caracteristicile:
$X[~C~] = (G[~A~] * X[~A~] + G[~B~] * X[~B~]) / (G[~A~] + G[~B~])$
$Y[~C~] = (G[~A~] * Y[~A~] + G[~B~] * Y[~B~]) / (G[~A~] + G[~B~])$
$G[~C~] = G[~A~] + G[~B~]$
iar costul acestei operații este $G[~A~] * G[~B~] * Dist(A, B)$. Apoi se elimină din listă punctele $A$ și $B$ și se adaugă punctul [$C$]. Acest tip de operație se efectuează succesiv (de $N - 1$ ori) până când lista va conține un singur punct.
 
h2. Cerință
 
Determinați costul total minim al unei secvențe de operații prin care să rămâneți cu un singur punct în listă.
h2. Date de intrare
Fișierul de intrare $reducere.in$ ...
Fișierul de intrare $reducere.in$ conține pe prima linie numărul natural [$N$]. Pe următoarele $N$ linii sunt date cele $N$ puncte [$P1$], [$P2$], ..., $PN$ prin coordonatele lor carteziene $X[~Pi~]$ și $Y[~Pi~]$, numere naturale, câte unul pe câte o linie.
h2. Date de ieșire
În fișierul de ieșire $reducere.out$ ...
Fișierul de ieșire $reducere.out$ conține un singur număr zecimal, costul total minim al unei secvențe de operații prin care să rămâneți cu un singur punct în listă, cu o precizie absolută de 10^-4^.
h2. Restricții
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 16$
* $-10 000 ≤ X[~Pi~], Y[~Pi~] ≤ 10 000$
* Pentru 30% din teste se garantează că $2 ≤ N ≤ 8$
* Lista poate conține inițial sau pe parcurs două sau mai multe puncte cu aceleași coordonate.
h2. Exemplu
table(example).
|_. reducere.in |_. reducere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
0 0
0 1
1 0
1 1
| 2.8284
|
h3. Explicație
...
Se aleg $P1$ și $P4$ și se obține punctul $P5$ de coordonate $(0.5, 0.5)$ cu costul $~1.4142$ și greutatea [$2$].
Se aleg $P2$ și $P3$ și se obține punctul $P6$ de coordonate $(0.5, 0.5)$ cu costul $~1.4142$ și greutatea [$2$].
Se aleg $P5$ și $P6$ și se obține punctul $P7$ de coordonate $(0.5, 0.5)$ cu costul $0.0000$ și greutatea [$4$].
Costul total este $~2.8284$.
== include(page="template/taskfooter" task_id="reducere") ==

Nu există diferențe între securitate.