Hide

Problem F
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