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 |
