Different Differences (Codeforces 1772C)
Tags: Greedy, constructive algorithms

An array $$$a$$$ consisting of $$$k$$$ integers is strictly increasing if $$$a_1 < a_2 < \dots < a_k$$$. For example, the arrays $$$[1, 3, 5]$$$, $$$[1, 2, 3, 4]$$$, $$$[3, 5, 6]$$$ are strictly increasing; the arrays $$$[2, 2]$$$, $$$[3, 7, 5]$$$, $$$[7, 4, 3]$$$, $$$[1, 2, 2, 3]$$$ are not.For a strictly increasing array $$$a$$$ of $$$k$$$ elements, let's denote the characteristic as the number of different elements in the array $$$[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$$$. For example, the characteristic of the array $$$[1, 3, 4, 7, 8]$$$ is $$$3$$$ since the array $$$[2, 1, 3, 1]$$$ contains $$$3$$$ different elements: $$$2$$$, $$$1$$$ and $$$3$$$.You are given two integers $$$k$$$ and $$$n$$$ ($$$k \le n$$$). Construct an increasing array of $$$k$$$ integers from $$$1$$$ to $$$n$$$ with maximum possible characteristic.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 819$$$) — the number of test cases.Each test case consists of one line containing two integers $$$k$$$ and $$$n$$$ ($$$2 \le k \le n \le 40$$$).

Output: For each test case, print $$$k$$$ integers — the elements of the strictly increasing array $$$a$$$ with the maximum possible characteristic. If there are multiple answers, print any of them.


Sample Inputs:
7
5 9
4 12
3 3
3 4
4 4
4 6
8 11

Sample Outputs:
1 3 4 7 8
2 4 7 12
1 2 3
1 3 4
1 2 3 4
2 4 5 6
1 2 3 5 6 7 8 11

Solution (Python):
def fun():
    n = int(input())
    for i in range(n):
        (a, b) = map(int, input().split())
        MinNow = 1
        Left = b - 1
        Out = [1]
        NeedInsert = a - 1
        while NeedInsert > 0:
            if Left - MinNow >= NeedInsert - 1:
                Out.append(Out[-1] + MinNow)
                Left -= MinNow
                MinNow += 1
            else:
                Out.append(Out[-1] + 1)
                Left -= 1
            NeedInsert -= 1
        print(' '.join((str(i) for i in Out)))
if __name__ == '__main__':
    fun()

Solution (Python):
import sys
input = sys.stdin.readline
import math

def print_str_line(str):
    sys.stdout.write(str + '\n')

def print_number(number):
    print_str_line(f'{number}')

def ans(k, n):
    ans = []
    i = 1
    increment = 0
    while k - len(ans) - 1 <= n - i - increment and len(ans) < k:
        i += increment
        ans.append(i)
        increment += 1
    for j in range(len(ans), k):
        i += 1
        ans.append(i)
    return ans
number_of_inputs = int(input())
for i in range(number_of_inputs):
    (k, n) = [int(num) for num in input()[:-1].split(' ')]
    _ans = ans(k, n)
    print_str_line(' '.join([str(num) for num in _ans]))

Solution (Python):
for _ in range(int(input())):
    (n, lim) = map(int, input().split())
    l = [i for i in range(1, n + 1)]
    e = 1
    l[-1] = lim
    for i in range(n - 2, -1, -1):
        if l[i + 1] - e <= l[i]:
            break
        else:
            l[i] = l[i + 1] - e
            e += 1
    print(*l)