Algorithm

Problem link- https://www.spoj.com/problems/ROBBERY2/

ROBBERY2 - Robbery 2

#math #ad-hoc-1

 

k bandits robbed a bank. They took away n gold coins. Being a progressive group of robbers they decided to use the following procedure to divide the coins. First the most respected bandit takes 1 coin, then the second respected takes 2 coins, ..., the least respected takes k coins, then again the most respected takes k+1 coins, and so on, until one of the bandits takes the remaining coins. Calculate how much gold each of the bandits gets.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consists of two integers n and k - the amount of coins and bandits respectively.

Constraints

1 <= t <= 500
106 <= n <= 1015
2 <= k <= 100

Output

For each test print the amounts of coins each bandit gets separated by spaces.

Example

Input:
3
1000000 2
1234567 3
123456789 4

Output:
499849 500151
411602 411887 411078
30869901 30858368 30862296 30866224

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

T = int(input())
for _ in range(T):
    N, K = map(int, input().split())
    steps = 0
    skipped = 1 << 55
    while skipped > 0:
        current = (steps + skipped) * K
        if current * (current + 1) // 2 <= N:
            steps += skipped
        skipped >>= 1
    coins = [0] * K
    N -= steps * K * (steps * K + 1) // 2
    last = steps * K + 1
    for i in range(K):
        if N <= last:
            coins[i] += N
            break
        coins[i] += last
        N -= last
        last += 1
    for i in range(K):
        a1 = i + 1
        an = (steps - 1) * K + i + 1
        coins[i] += (a1 + an) * steps // 2
    print(" ".join(map(str, coins)))
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3
1000000 2
1234567 3
123456789 4

Output

x
–
+
cmd
499849 500151
411602 411887 411078
30869901 30858368 30862296
30866224
Advertisements

Demonstration

SPOJ Solution-Robbery 2-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python