Problem C
Ciąg liczb
Languages
da
de
en
et
fi
lt
lv
pl
uk
Ciąg dodatnich liczb całkowitych $(x_1,\ldots ,x_ m)$ jest dobry jeśli $x_1 = 1$ oraz dla każdego $1 < j \leq m$ mamy albo $x_ j=x_{j-1}+1$ albo $x_ j=x_ k\cdot x_ l$ dla pewnych $k$ oraz $l$ spełniających $0< k\leq l< j$. Na przykład, oba ciągi $(1,1)$ oraz $(1,2)$ są dobre, ale ciąg $(1,3)$ nie jest dobry. Dla danych $n$ liczb całkowitych $w_1,\ldots ,w_ n$ definiujemy wagę ciągu liczb całkowitych $(x_1,\ldots ,x_ m)$ spełniającego $1\leq x_ j \leq n$ dla każdego $1\leq j\leq m$ jako
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]Na przykład, mając wagi $w_1=10, w_2=42,w_3= 1$, wagą ciągu $(1,1)$ jest $20$, a wagą ciągu $(1,3)$ jest $11$. Dla $1\leq v\leq n$ definiujemy $s_ v$ jako najmniejszą możliwą wagę dobrego ciągu zawierającego wartość $v$.
Twoim zadaniem jest wyznaczenie wartości $s_1,\ldots ,s_ n$.
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita $n$, będąca liczbą wag. Kolejne $n$ wierszy zawierają liczby całkowite wag $w_1, \ldots , w_ n$.
Wyjście
Wypisz $n$ wierszy zawieraje kolejno: $s_1$, $\ldots $, $s_ n$.
Ograniczenia i punktacja
Zawsze jest spełnione $1\leq n \leq 30\, 000$ oraz $1\leq w_ i \leq 10^6$ dla każdego $1\leq i \leq n$.
Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda warta jest pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.
|
Grupa |
Punkty |
Ograniczenia |
|
$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$ |
Brak dodatkowych ograniczeń |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
