Imagine a concatenation of first 100
positive integers i.e.
12345678910111213...979899100.
You are given a task to erase 96 digits of your choice, without changing the original order, then shrink the final sequence to eliminate blank spaces, striving to achieve largest possible result.
What is this maximal value and how was it derived?
The initial concatenation is 9 + 2*90 + 3 = 192 digits long, so erasing 96 will leave 96 as well.
At each point as we proceed from left to right we need to keep track of how many of the remaining digits we need to keep. For the given digit we are looking at in this sweep, we need to look ahead to see if any digit beyond is both higher than the one we're looking at and, if we wait until we get there to keep that one, there are enough digits remaining to satisfy the number still needed to complete the 96 we need to keep; if there is such a higher number then discard the digits until that number is reached; otherwise keep this one.
When you get to that higher number (if that's the decision made), the same decision procedure must be done again. That is, don't automatically assume this one is good just because it is higher than the one first looked at.
If, however, the decision was to keep the given digit being looked at, do so, subtracting 1 from the number still needed and advance to the next position and continue from there.
The program below follows that procedure and produces the following output:
I split up the original number below, with a row of carets (^) underneath each half to show which digits are kept. Below that is the resulting number that remains.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525
^ ^ ^ ^ ^^
354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
999995657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
Note that in this particular case it doesn't really matter that the 5 chosen was the one immediately following the last 9. However, the algorithm is written so that this 5 is chosen so as to allow more choice for subsequent tests, in cases, for example where everything after the given 5 (say) is lower than 5, as in ...54444451111111111111. Depending on how many more are required to be kept, choosing the second 5 instead of the first might (without further code) preclude continuing with the 4's, or actually including both 5's.
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
Open "leaving a maximal result.txt" For Output As #2
s$ = ""
For i = 1 To 100
s = s + LTrim(Str(i))
Next
ReDim kept(96)
ptr = 1: need = 96: keep$ = ""
Do
cmp$ = Mid(s, ptr, 1)
found = 0
For i = ptr + 1 To Len(s) + 1 - need
If Mid(s, i, 1) > cmp Then
ptr = i
found = 1
Exit For
End If
Next
If found = 0 Then
keep = keep + cmp$
need = need - 1
kept(Len(keep)) = ptr
ptr = ptr + 1
End If
Loop Until need = 0
Text1.Text = Text1.Text & s & crlf
Print #2, s
prev = 0
For i = 1 To 96
Text1.Text = Text1.Text & Space(kept(i) - prev - 1) & "^"
Print #2, Space(kept(i) - prev - 1) + "^";
prev = kept(i)
Next
Text1.Text = Text1.Text & crlf & keep & crlf
Print #2,
Print #2, keep
Text1.Text = Text1.Text & crlf & " done"
Close 2
End Sub
|
|
Posted by Charlie
on 2017-08-25 10:47:40 |
algorithm
