Nosaukums
Gaisma tavos logos (gaisma)
Laika limits
0.20s
Atmiņas limits
256.0 MB
Grūtība
88%

Definīcija

Arhitektu birojam „Tasja & Esabruks” ir uzdots projektēt daudzstāvu viesnīcu kompleksu slavenā piejūras kūrortā. Viesnīcu būvei ir atvēlēta vien šaura zemes strēle N vienību garumā, kas stiepjas gar jūru un ko abos galos ierobežo stāvas klintis, pie kam katrā vienībā drīkst būvēt ne vairāk kā vienu viesnīcu. Shematiski katru viesnīcu var aprakstīt kā naturāla augstuma stabiņus uz veselo skaitļu ass, uz kuras atzīmētas N vienības, kas sanumurētas pēc kārtas ar skaitļiem no 1 līdz N:

Tā kā paredzētais viesnīcu blīvums ir visai liels, ir svarīgi noteikt, cik daudz gaismas nokļūs katras viesnīcas stāva logos. Visu viesnīcu stāvi ir vienādi augsti un katram no tiem tiek aprēķināts labums, kas tiek izteikts iepriekšminētajās garuma vienībās. Ja viesnīcu paredzēts būvēt vienībā i(1≤i≤N), tad tās j-tā(1≤j) stāva labumu aprēķina vispirms uz katru pusi atrodot tuvāko objektu, kas ir vismaz j stāvus augsts (pietiekami augsta viesnīca vai klints) un izvēloties lielāko no šiem attālumiem. Aprēķinos tiek uzskatīts, ka klintis atrodas vienībās 0 un N+1, pie kam tās ir augstākas par visaugstāko iespējamo viesnīcu. Zīmējumā katrā rūtiņā ierakstītais skaitlis ir attiecīgā viesnīcas stāva labums.

Uzrakstiet programmu, kas plānotam viesnīcu izvietojumam un katras viesnīcas stāvu skaitam, aprēķina katras viesnīcas visu stāvu kopējo labumu!


Ievaddatu raksturojums

Pirmajā rindā dots naturāls skaitlis N(N≤105 , zemes strēles garums garuma vienībās). Otrajā rindā doti N veseli nenegatīvi skaitļi. Katram i(1≤i≤N) i-tais skaitlis šajā rindā apzīmē tās viesnīcas, ko paredzēts būvēt i-tajā vienībā, stāvu skaitu. 0 nozīmē, ka viesnīcu šajā vienībā būvēt nav paredzēts. Neviena viesnīcas augstums nepārsniedz 109 . Starp katriem diviem blakus skaitļiem ievaddatos ir viena tukšumzīme.


Izvaddatu raksturojums

Pirmajā rindā jāizvada tik skaitļi, cik viesnīcu ir aprakstīts ievaddatos. Šiem skaitļiem jāapraksta viesnīcu labumi pēc kārtas vienību numuru pieaugšanas secībā. Starp katriem diviem blakus skaitļiem izvaddatos jābūt tukšumzīmei.


Piezīmes

Uzdevums izmantots LIO 2015. gada atlases kārtā


Paraugdati

Stdin
14
8 0 4 3 9 0 0 6 0 1 2 3 0 0
Stdout
24 8 3 50 31 2 4 10

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.