Optimal separation P50778


Statement
 

pdf   zip

thehtml

Consider the sequence 1, 2, …, n. If we use k separators among those numbers, we get k + 1 subsequences. Let si be the sum of the elements of the i-th subsequence. Let m be the minimum si, and let M be the maximum si. Given n and k, please choose where to place the k separators so that Mm is as small as possible.

Input

Input consists of several cases, each one with n and k. You can assume 1 ≤ n ≤ 50 and 0 ≤ k ≤ min(n − 1, 10).

Output

For every case, print k + 3 lines. On the first line print the minimum Mm. Afterwards, print a line for each of the k + 1 subsequences, in order, with the numbers and their sum. Finally, print a line with 10 dashes. Follow exactly the format of the sample output. If there is more than one optimal solution, choose any one.

Observation

The expected solution is a dynamic programming. This problem could also be solved by precomputing the solutions. But, if you do that, your solution will be manually rejected.

Public test cases
  • Input

    4 0
    50 10
    

    Output

    0
    1 + 2 + 3 + 4 = 10
    ----------
    40
    1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 = 120
    16 + 17 + 18 + 19 + 20 + 21 + 22 = 133
    23 + 24 + 25 + 26 + 27 = 125
    28 + 29 + 30 + 31 = 118
    32 + 33 + 34 = 99
    35 + 36 + 37 = 108
    38 + 39 + 40 = 117
    41 + 42 + 43 = 126
    44 + 45 + 46 = 135
    47 + 48 = 95
    49 + 50 = 99
    ----------
    
  • Information
    Author
    Josep Grané
    Language
    English
    Official solutions
    C++
    User solutions
    C++