'
' Stacking Numbers
' Problem 3, AIC 2003
' Visual Basic Sample Solution (slow but simple, scores 50%)
'

'
' This solution simply runs through all possible choices for the six
' numbers at the bottom of the pyramid.  From these it selects the
' combination that gives the highest possible score (number at the
' top of the pyramid).
'
' If there are N numbers to choose from in the input set, we expect
' a bit under N^6 combinations overall for large N.  If N = 32 (the
' maximum case allowed in the problem statement) then this is about
' 1,000,000,000 combinations which is too many for a 2s time limit.
'
' Note that we use Long instead of Integer for our variables since
' Integer has a maximum value of 32,767 and the best possible score
' can be very much larger than this.
'

' Constants from the problem statement:
Const MAXSET = 100
    ' Maximum size of the input set

' Variables holding the input data:
Dim base As Long
    ' Modular base to use with addition
Dim inputSet(MAXSET) As Long
    ' Set of available starting numbers to choose from
Dim setSize As Long
    ' Number of available starting numbers to choose from

' Variables describing the current and best arrangements:
Dim start(6) As Long
    ' The six members at the bottom of the pyramid
Dim ans(6) As Long
    ' The six numbers that give the best possible final score
Dim bestScore As Long
    ' The best possible final score

'
' Calculates the score at the top of the pyramid from the six numbers
' currently at the bottom of the pyramid.  The numbers at the bottom of
' the pyramid are start(1..6).
'
Function Score As Long
    Dim left As Long
    Dim right As Long

    left = (start(1) + (4 * start(2)) + (6 * start(3)) + (4 * start(4)) + _
        start(5)) mod base
    right = (start(2) + (4 * start(3)) + (6 * start(4)) + (4 * start(5)) + _
        start(6)) mod base
    Score = left * right
End Function

'
' The main program.
'
Sub Main()
    ' Open the I/O files.
    Open "stackin.txt" For Input As #1
    Open "stackout.txt" For Output As #2

    ' Read the input data.
    Input #1, base, setSize
    For i = 1 To setSize
        Input #1, inputSet(i)
    Next i

    ' Search through all possible combinations.
    ' This is done with six nested For loops, one for each number at
    ' the bottom of the pyramid.
    ' Note that we ensure at each stage that these six numbers are
    ' distinct.
    bestScore = -1
    Dim i1 As Integer, i2 As Integer, i3 As Integer
    Dim i4 As Integer, i5 As Integer, i6 As Integer

    Dim currScore As Long
    For i1 = 1 To setSize
      start(1) = inputSet(i1)
      For i2 = 1 To setSize
        If i2 <> i1 Then
          start(2) = inputSet(i2)
          For i3 = 1 To setSize
            If i3 <> i2 And i3 <> i1 Then
              start(3) = inputSet(i3)
              For i4 = 1 To setSize
                If i4 <> i3 And i4 <> i2 And i4 <> i1 Then
                  start(4) = inputSet(i4)
                  For i5 = 1 To setSize
                    If i5 <> i4 And i5 <> i3 And i5 <> i2 And i5 <> i1 Then
                      start(5) = inputSet(i5)
                      For i6 = 1 To setSize
                        If i6 <> i5 And i6 <> i4 And i6 <> i3 And _
                            i6 <> i2 And i6 <> i1 Then
                          start(6) = inputSet(i6)

                          ' We have a selection of six starting numbers.
                          ' See if the resulting score is better than
                          ' we've seen so far.
                          currScore = score
                          If currScore > bestScore Then
                            bestScore = currScore
                            For i = 1 To 6
                              ans(i) = start(i)
                            Next i
                          End If
                        End If
                      Next i6
                    End If
                  Next i5
                End If
              Next i4
            End If
          Next i3
        End If
      Next i2
    Next i1

    ' Output the best solution that was found.
    Print #2, bestScore
    Print #2, ans(1), ans(2), ans(3), ans(4), ans(5), ans(6)

    ' Tidy up.
    Close #1
    Close #2
End Sub