Problem C
Folgen
Languages
da
de
en
et
fi
lt
lv
pl
uk
Eine Folge positiver ganzer Zahlen $(x_1,\ldots ,x_ m)$ ist gut, wenn $x_1 = 1$ und für jedes $1 < j \leq m$ entweder ${x_ j=x_{j-1}+1}$ oder ${x_ j=x_ k\cdot x_ l}$ für ein $k$ und $l$ mit $0< k\leq l< j$ gilt. Zum Beispiel sind die Folgen $(1,1)$ und $(1,2)$ beide gut, aber die Folge $(1,3)$ ist nicht gut. Für $n$ gegebene ganze Zahlen $w_1,\ldots ,w_ n$ definieren wir das Gewicht einer ganzzahligen Folge $(x_1,\ldots ,x_ m)$, die $1\leq x_ j \leq n$ für jedes $1\leq j\leq m$ erfüllt, als
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Sei zum Beispiel $w_1=10, w_2=42,w_3= 1$. Dann hat die Folge $(1,1)$ das Gewicht $20$ und die Folge $(1,3)$ das Gewicht $11$. Für $1\leq v\leq n$ definiere $s_ v$ als das kleinstmögliche Gewicht einer guten Folge, die den Wert $v$ enthält.
Deine Aufgabe ist es, die Werte $s_1,\ldots ,s_ n$ zu bestimmen.
Eingabe
Die erste Zeile der Eingabe besteht aus der ganzen Zahl $n$, der Anzahl der Gewichte. Die nächsten $n$ Zeilen enthalten die ganzzahligen Gewichte $w_1, \ldots , w_ n$.
Ausgabe
Gib $n$ Zeilen aus, die der Reihe nach $s_1$, $\ldots $, $s_ n$ enthalten.
Beschränkungen und Bewertung
Es gilt immer $1\leq n \leq 30\, 000$ und $1\leq w_ i \leq 10^6$ für jedes $1\leq i \leq n$.
Deine Lösung wird an einer Reihe von Testgruppen getestet, von denen jede eine bestimmte Anzahl von Punkten wert ist. Jede Testgruppe enthält eine Reihe von Testfällen. Um die Punkte für eine Testgruppe zu erhalten, musst du alle Testfälle in der Testgruppe lösen. Deine endgültige Punktzahl ist die maximale Punktzahl für eine einzelne Einsendung.
|
Gruppe |
Punkte |
Beschränkungen |
|
$1$ |
$11$ |
$n\leq 10$ |
|
$2$ |
$10$ |
$n\leq 300$, $w_1=\cdots =w_ n = 1$ |
|
$3$ |
$10$ |
$n\leq 300$, $w_1=\cdots =w_ n$ |
|
$4$ |
$9$ |
$n\leq 1400$, $w_1=\cdots =w_ n = 1$ |
|
$5$ |
$45$ |
$n\leq 5000$ |
|
$6$ |
$15$ |
Keine weiteren Beschränkungen |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
