Problem F
Seka
Languages
da
de
en
et
fi
lt
lv
pl
uk
Natūraliųjų skaičių seka $(x_1,\ldots ,x_ m)$ vadinama gera, jeigu $x_1 = 1$ ir kiekvienam $1 < j \leq m$ galioja arba $x_ j=x_{j-1}+1$, arba $x_ j=x_ k\cdot x_ l$, kur $k$ ir $l$ yra tokie skaičiai, kuriems galioja $0< k\leq l< j$.
Pavyzdžiui, abidvi sekos $(1,1)$ ir $(1,2)$ yra geros, bet seka $(1,3)$ – ne.
Duotiesiems $n$ skaičių $w_1,\ldots ,w_ n$, sekos $(x_1,\ldots ,x_ m)$, kur kiekvienam $1\leq j\leq m$ galioja $1\leq x_ j \leq n$ , svoris apibrėžiamas taip:
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Pavyzdžiui, duoti svoriai $w_1=10, w_2=42,w_3= 1$. Tuomet sekos $(1,1)$ svoris yra $20$, o sekos $(1,3)$ – $11$.
Kiekvienam $1\leq i\leq n$ pažymėkime mažiausią geros sekos, kurioje yra $i$, svorį $s_ i$.
Raskite $s_1,\ldots ,s_ n$ reikšmes.
Pradiniai duomenys
Pirmoje įvesties eilutėje pateiktas svorių skaičius $n$ (sveikasis skaičius). Kitose $n$ eilučių pateikti svoriai – sveikieji skaičiai $w_1, \ldots , w_ n$.
Rezultatai
Išveskite $n$ eilučių. Jose iš eilės pateikite $s_1$, $\ldots $, $s_ n$.
Ribojimai ir vertinimas
Visada galioja $1\leq n \leq 30\, 000$ ir $1\leq w_ i \leq 10^6$ kiekvienam $1\leq i \leq n$.
Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kurių kiekviena verta tam tikro skaičiaus taškų. Kiekviena testų grupė sudaryta iš įvairių testų. Testų grupės taškai skiriami tik išsprendus visus grupės testus. Galutinis taškų skaičius lygus daugiausiai surinkusio sprendimo taškų skaičiui.
|
Grupė |
Taškai |
Papildomi ribojimai |
|
$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$ |
nėra |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
