# Optimal separation P50778

Statement

html

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++
Event
Setzè Concurs de Programació de la UPC - Final
Date
2018-09-19