ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Regional School Programming Contest 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Different Sums

Time limit: 1.0 second
Memory limit: 64 MB
Alex is a very serious mathematician and he likes to solve serious problems. For example, this problem.
You are to construct an array of n integers in which the amount of different integers is not less than k. Among all such arrays you have to construct the one with the minimal amount of different sums on non-empty subarrays. In other words, lets compute the sums of every non-empty subarray and remove repeating sums. You have to minimize the number of remaining sums.


In the only line of input there are two integers n, k (1 ≤ kn ≤ 500), separated by a space.


Print n integers separated by spaces — the answer for the problem. All the numbers must not be greater than 106 by absolute value. It is guaranteed that there exists an optimal solution with numbers up to 105 by absolute value. If there are multiple possible answers, you may print any of them.


1 1
3 2
0 7 0


Let’s take a closer look on the second sample. We will denote the sum on the segment [l,r] by sum(l,r) (elements are numbered starting with 1). sum(1, 1) = sum(3, 3) = 0, sum(1, 2) = sum(1, 3) = sum(2, 2) = sum(2, 3) = 7, so there are only two different sums.
Problem Author: Nikita Sivukhin (prepared by Alexey Danilyuk, Nikita Sivukhin)
Problem Source: Ural Regional School Programming Contest 2015
To submit the solution for this problem go to the Problem set: 2065. Different Sums