Problem C
Jono
Languages
da
de
en
et
fi
lt
lv
pl
uk
Jono positiivisia kokonaislukuja $(x_1,\ldots ,x_ m)$ on hyvä, jos $x_1 = 1$ ja jokaiselle $1 < j \leq m$ pätee joko $x_ j=x_{j-1}+1$, tai $x_ j=x_ k\cdot x_ l$ joillekin $k$ ja $l$, joille $0< k\leq l< j$. Esimerkiksi jonot $(1,1)$ ja $(1,2)$ ovat hyviä, mutta jono $(1,3)$ ei ole hyvä. Annettuna on $n$ kokonaislukua $w_1,\ldots ,w_ n$. Jonon $(x_1,\ldots ,x_ m)$, missä $1\leq x_ j \leq n$ kaikille $1\leq j\leq m$, paino määritellään
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Esimerkiksi painoilla $w_1=10, w_2=42,w_3= 1$ jonon $(1,1)$ paino on $20$, ja jonon $(1,3)$ paino on $11$. Jokaiselle arvolle $1\leq v\leq n$ määritellään luku $s_ v$: pienin mahdollinen paino jonolle, joka sisältää arvon $v$.
Tehtäväsi on selvittää arvot $s_1,\ldots , s_ n$.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$: painojen lukumäärä. Seuraavat $n$ riviä sisältävät painot $w_1, \ldots , w_ n$.
Tuloste
Tulosta $n$ riviä sisältäen luvut $s_1$, $\ldots $, $s_ n$ järjestyksessä.
Rajoitukset ja pisteytys
Kaikille syötteille pätee $1\leq n \leq 30\, 000$ ja $1\leq w_ i \leq 10^6$ kaikille $1\leq i \leq n$.
Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.
|
Ryhmä |
Pisteet |
Rajoitukset |
|
$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$ |
Ei muita rajoituksia |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
