Problem C
Jada
Languages
da
de
en
et
fi
lt
lv
pl
uk
Nimetame positiivsetest täisarvudest koosnevat jada $(x_1,\ldots ,x_ m)$ heaks, kui $x_1 = 1$ ja iga $1 < j \leq m$ korral kehtib kas $x_ j=x_{j-1}+1$ või $x_ j=x_ k\cdot x_ l$ mingite $k$ ja $l$ kohta, kus $0< k\leq l< j$. Näiteks on jadad $(1,1)$ ja $(1,2)$ mõlemad head, aga jada $(1,3)$ ei ole hea. On antud $n$ täisarvu $w_1,\ldots ,w_ n$. Nimetame arvujada $(x_1,\ldots ,x_ m)$ kaaluks, kus $1\leq x_ j \leq n$ iga $1\leq j\leq m$ kohta, arvu
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Näiteks kui on antud $w_1=10, w_2=42,w_3= 1$, siis jada $(1,1)$ kaal on $20$ ja jada $(1,3)$ kaal on $11$. Tähistagu iga $1\leq v\leq n$ korral $s_ v$ vähimat võimalikku sellise hea jada kaalu, mis sisaldab väärtust $v$.
Sinu ülesanne on leida väärtused $s_1,\ldots ,s_ n$.
Sisend
Sisendi esimesel real on täisarv $n$ — kaalude arv. Järgmisel $n$ real on antud kaalud $w_1, \ldots , w_ n$.
Väljund
Trüki $n$ rida, milledel on vastavalt arvud $s_1$, $\ldots $, $s_ n$.
Piirangud ja hindamine
Alati kehtivad $1\leq n \leq 30\, 000$ ja $1\leq w_ i \leq 10^6$ iga $1\leq i \leq n$ kohta.
Selles ülesandes on testid jagatud gruppidesse, iga grupp on väärt mingi arvu punkte. Iga grupi eest saavad punkte vaid need lahendused, mis läbivad kõik sellesse gruppi kuuluvad testid. Sinu lõplik skoor on esituste maksimum.
|
Grupp |
Punktid |
Lisapiirangud |
|
$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$ |
Lisapiirangud puuduvad. |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
