72 lines
2 KiB
Text
72 lines
2 KiB
Text
' Water collected between towers
|
|
DECLARE SUB ShellSort (A() AS ANY)
|
|
TYPE TTowerRec
|
|
Hght AS INTEGER
|
|
Posi AS INTEGER
|
|
END TYPE
|
|
|
|
'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
|
|
|
|
REM $DYNAMIC
|
|
DIM Manhattan(0 TO 1) AS TTowerRec
|
|
FOR I% = 1 TO 7
|
|
READ N%
|
|
ERASE Manhattan
|
|
REDIM Manhattan(0 TO N% - 1) AS TTowerRec
|
|
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% = Water% - Manhattan(J%).Hght
|
|
IF Manhattan(J%).Posi < First% THEN
|
|
Water% = Water% + Manhattan(J%).Hght * (First% - Manhattan(J%).Posi - 1)
|
|
First% = Manhattan(J%).Posi
|
|
END IF
|
|
IF Manhattan(J%).Posi > Last% THEN
|
|
Water% = 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%
|
|
END
|
|
|
|
REM $STATIC
|
|
SUB ShellSort (A() AS TTowerRec)
|
|
'quick and dirty shellsort, not the focus of this exercise
|
|
Gap% = UBOUND(A): N% = UBOUND(A)
|
|
DIM Temp AS TTowerRec
|
|
DO
|
|
Gap% = INT(Gap% / 2.2)
|
|
IF Gap% = 0 THEN Gap% = 1
|
|
FOR I% = Gap% TO N%
|
|
Temp = A(I%)
|
|
J% = I%
|
|
' Simulated WHILE J% >= Gap% ANDALSO A(J% - Gap%).Hght < Temp.Hght
|
|
DO
|
|
IF J% < Gap% THEN EXIT DO
|
|
IF A(J% - Gap%).Hght >= Temp.Hght THEN EXIT DO
|
|
A(J%) = A(J% - Gap%)
|
|
J% = J% - Gap%
|
|
LOOP
|
|
A(J%) = Temp
|
|
NEXT I%
|
|
LOOP UNTIL Gap% = 1
|
|
END SUB
|