## Citizens' safety

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

### Citizens' safety

President of Lampville asked you to implement an algorithm which would help him make one of the most dangerous streets in his city safe. To do so, he wants to build a street lantern on one of the buildings on this street. The buildings are standing in a straight line numbered from 1 to x (both x and lantern's height are integers). However, funds are not infinite and therefore they are highly important for the president - the higher the lantern is, the more it will cost. To let the lantern of l height stand on the roof of the q building (of height h_q) so that it will enlight the whole street, for every other r building (of height h_r) such inequality has to apply: h_r<=h_q+l-sqrt(abs(q-r)). You are to deliver an algorithm which would print a minimum height of the lantern on every building such that it would make the street safer.

INPUT: x (1<=x<=500001) meaning how many buildings are there on the street and x times the h_q meaning the height of the q building (0<=h_q<=1 000 000 001).

OUTPUT: x lines and in every line l_q meaning the minimum height of the lantern on q building.

EXAMPLE:
For input:
10
2
9
8
5
6
7
4
3
10
1

The answer is:
11
4
5
8
6
5
8
9
2
11

What I think after thinking for some time is that we should always use the highest building as the h_r in the inequality since if the inequality is true for the highest building, it's automatically true for every other. On the other hand, however, what I wrote above is not always true because we also consider this absolute value of q-r so the height doesn't have the most significance.. Could you please help me with this?
Foamy

Posts: 34
Joined: Sun Sep 12, 2010 2:09 pm UTC

### Re: Citizens' safety

So maybe I should check for every building and there is no faster way to do this than brute force?
Foamy

Posts: 34
Joined: Sun Sep 12, 2010 2:09 pm UTC

Return to Coding

### Who is online

Users browsing this forum: Bing [Bot], Sizik and 11 guests