Water collected between towers: Difference between revisions
Content deleted Content added
add FreeBASIC |
|||
Line 733:
{ 6, 7, 10, 7, 6 } -> 0
</pre>
=={{header|FreeBASIC}}==
Uses Nigel Galloway's very elegant idea, expressed verbosely so you can really see what's going on.
<lang freebasic>type tower
hght as uinteger
posi as uinteger
end type
sub shellsort( a() as tower )
'quick and dirty shellsort, not the focus of this exercise
dim as uinteger gap = ubound(a), i, j, n=ubound(a)
dim as tower temp
do
gap = int(gap / 2.2)
if gap=0 then gap=1
for i=gap to n
temp = a(i)
j=i
while j>=gap andalso a(j-gap).hght < temp.hght
a(j) = a(j - gap)
j -= gap
wend
a(j) = temp
next i
loop until gap = 1
end sub
'heights of towers in each city prefixed by the number of towers
data 5, 1, 5, 3, 7, 2
data 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
data 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1
data 4, 5, 5, 5, 5
data 4, 5, 6, 7, 8
data 4, 8, 7, 7, 6
data 5, 6, 7, 10, 7, 6
dim as uinteger i, n, j, first, last, water
dim as tower manhattan(0 to 1)
for i = 1 to 7
read n
redim manhattan( 0 to n-1 )
for j = 0 to n-1
read manhattan(j).hght
manhattan(j).posi = j
next j
shellsort( manhattan() )
if manhattan(0).posi < manhattan(1).posi then
first = manhattan(0).posi
last = manhattan(1).posi
else
first = manhattan(1).posi
last = manhattan(0).posi
end if
water = manhattan(1).hght * (last-first-1)
for j = 2 to n-1
if first<manhattan(j).posi and manhattan(j).posi<last then water -= manhattan(j).hght
if manhattan(j).posi < first then
water += manhattan(j).hght * (first-manhattan(j).posi-1)
first = manhattan(j).posi
end if
if manhattan(j).posi > last then
water += manhattan(j).hght * (manhattan(j).posi-last-1)
last = manhattan(j).posi
end if
next j
print using "City configuration ## collected #### units of water."; i; water
next i</lang>
{{out}}
<pre>City configuration 1 collected 2 units of water.
City configuration 2 collected 14 units of water.
City configuration 3 collected 35 units of water.
City configuration 4 collected 0 units of water.
City configuration 5 collected 0 units of water.
City configuration 6 collected 0 units of water.
City configuration 7 collected 0 units of water.</pre>
=={{header|Go}}==
| |||