Hide

Problem F
Jono

Languages da de en et fi lt lv pl uk

Jono positiivisia kokonaislukuja (x1,,xm) on hyvä, jos x1=1 ja jokaiselle 1<jm pätee joko xj=xj1+1, tai xj=xkxl joillekin k ja l, joille 0<kl<j. Esimerkiksi jonot (1,1) ja (1,2) ovat hyviä, mutta jono (1,3) ei ole hyvä. Annettuna on n kokonaislukua w1,,wn. Jonon (x1,,xm), missä 1xjn kaikille 1jm, paino määritellään

wx1++wxm.

Esimerkiksi painoilla w1=10,w2=42,w3=1 jonon (1,1) paino on 20, ja jonon (1,3) paino on 11. Jokaiselle arvolle 1vn määritellään luku sv: pienin mahdollinen paino jonolle, joka sisältää arvon v.

Tehtäväsi on selvittää arvot s1,,sn.

Syöte

Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun n: painojen lukumäärä. Seuraavat n riviä sisältävät painot w1,,wn.

Tuloste

Tulosta n riviä sisältäen luvut s1, , sn järjestyksessä.

Rajoitukset ja pisteytys

Kaikille syötteille pätee 1n30000 ja 1wi106 kaikille 1in.

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

n10

2

10

n300, w1==wn=1

3

10

n300, w1==wn

4

9

n1400, w1==wn=1

5

45

n5000

6

15

Ei muita rajoituksia

Sample Input 1 Sample Output 1
3
10
42
1
10
52
53
Hide

Please log in to submit a solution to this problem

Log in