Hide

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