Hide

Problem F
Talfølge

Languages da de en et fi lt lv pl uk

En følge af positive heltal $(x_1,\ldots ,x_ m)$ er god hvis $x_1 = 1$ og der for $1 < j \leq m$ gælder enten $x_ j=x_{j-1}+1$ eller $x_ j=x_ k\cdot x_ l$ for nogle $k$ og $l$ med $0< k\leq l< j$. For eksempel er talfølgerne $(1,1)$ og $(1,2)$ begge gode, men talfølgen $(1,3)$ er ikke god. For $n$ givne heltal $w_1,\ldots ,w_ n$ defines vægten an en heltalsfølge $(x_1,\ldots ,x_ m)$, der opfylder $1\leq x_ j \leq n$ for alle $1\leq j\leq m$, som

\[ w_{x_1} +\cdots +w_{x_ m}\, . \]

Hvis for eksempel de givne vægte er $w_1=10, w_2=42 ,w_3 = 1$, så har talfølgen $(1,1)$ vægt $20$ og talfølgen $(1,3)$ har vægt $11$. For $1\leq v\leq n$, lad $s_ v$ angive den mindst mulige vægt af en god talfølge, der indeholder værdien $v$.

Din opgave er at bestemme værdierne $s_1,\ldots ,s_ n$.

Indlæsning

Første linje af indlæsningen bestar af heltallet $n$, antallet af vægte. De næste $n$ linjer indeholder heltalsvægtene $w_1, \ldots , w_ n$.

Udskrift

Skriv $n$ linjer med $s_1$, $\ldots $, $s_ n$ i rækkefølge.

Begrænsninger og pointgivning

Der gælder altid $1\leq n \leq 30\, 000$ og $1\leq w_ i \leq 10^6$ for hvert $1\leq i \leq n$.

Din løsning vil blive testet på en række testgrupper, hver med en vist antal point. Hver testgruppe indeholder en række testfald. For at opnå point for en testgruppe skal du løse alle testfald i testgruppen. Din endelige score vil være den højeste score for en enkelt indsendelse.

Gruppe

Point

Begrænsninger

$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$

Ingen yderligere begrænsninger

Sample Input 1 Sample Output 1
3
10
42
1
10
52
53