Want to try solving this problem? You can submit your code online if you log in or register.

**Input File:** `stackin.txt`

**Output File:** `stackout.txt`

**Time Limit:** 0.5 seconds

It's raining outside, you're bored and you desperately need something to do. Staring at a pile of soft drink cans in the corner, you devise a game that could keep you entertained for hours.

This game is played on a pyramid of side length six. This pyramid contains 21 boxes as illustrated below. In each box you must place a single non-negative integer.

You may choose the six integers that are placed in the bottom row of the pyramid. Once this bottom row has been filled, you have rules that describe how to fill the remaining boxes from bottom to top. The integer that is placed in the very top box of the pyramid is your score. Your aim is to obtain the highest score possible.

Before you play the game you are given some positive integer *b* called
the *base*.
The rules for filling in the remaining boxes are as follows.

- For each box below the top row, you add the
integers in the two boxes directly beneath it. If this sum is
greater than or equal to the base
*b*, you subtract*b*from this total so that the sum becomes strictly less than*b*. - For the very top box, you simply multiply the integers in the two boxes directly beneath it.

A sample game is illustrated below, played with base *b* = 100.
The left hand diagram shows six integers initially placed in the bottom
row, and the right hand diagram shows the resulting pyramid with every
box filled.

Examine the first box of the fourth row (61). This box simply
contains the sum of the two integers beneath it: 33+28. On the other
hand, consider the first box of the third row (49). The sum of the
two integers beneath it is 61+88 = 149, which is larger than
*b*. We thus subtract *b* = 100 from this total to
obtain 49, which is placed
within the box. The topmost box contains 9702, which is the product
99 x 98.

Note that every box aside from the topmost box contains an integer
between 0 and *b*-1 inclusive. In particular, if the two integers
beneath a box add to precisely *b* then that box is filled with the
integer 0.

To make the game more interesting, you are given a small set of numbers from which the six integers in the bottom row must be chosen. No integer from this set may be used more than once in the bottom row. You must write a program that selects six integers from this set to place in the bottom row so that you obtain the highest score possible.

The input file will consist of three lines.
The first line will contain the base *b* with which the game is played.
You are guaranteed that
1 <= *b* <= 32,768.

The second line will contain an integer *s* representing the number
of integers in your set from which the bottom row must be chosen.
You are guaranteed that
6 <= *s* <= 32.

The third line will contain the entire list of *s* integers from which
the bottom row of the pyramid must be chosen. Each of these integers will be
between 0 and *b*-1 inclusive. These integers will be separated
by spaces, and no two of these integers will be equal.

The output must consist of precisely two lines. The first line must contain a single integer representing the highest possible score.

The second line must contain six integers that can be placed in the bottom row of the pyramid to obtain this highest possible score. The six integers should be written from left to right as they appear in the bottom row, and should be separated by spaces.

If more than one solution exists then you should only output one of these solutions. Any of these solutions will suffice.

100 7 1 2 3 4 5 6 7

8100 2 5 6 7 4 3

100 8 7 12 15 21 35 49 53 67

9702 12 21 7 53 49 35

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 2 October 2022, 10:51am AEDT