Problem: Manasa and Stones

Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

Note: The numbers on the stones are in increasing order.

Input Format

The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

Constraints

1 <= T <= 10
1 <= n, a, b <= 10^3

Output Format

Space-separated list of numbers which are the possible values of the last stone in increasing order.

Sample Input

2
3 
1
2
4
10
100

Sample Output

2 3 4 
30 120 210 300 

Explanation

All possible series for the first test case are given below:

  1. 0,1,2
  2. 0,1,3
  3. 0,2,3
  4. 0,2,4

Hence the answer 2 3 4.

Series with different number of final steps for second test case are the following:

  1. 0, 10, 20, 30
  2. 0, 10, 20, 120
  3. 0, 10, 110, 120
  4. 0, 10, 110, 210
  5. 0, 100, 110, 120
  6. 0, 100, 110, 210
  7. 0, 100, 200, 210
  8. 0, 100, 200, 300

Hence the answer 30 120 210 300.

Approach:

  1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
  2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

def chain(n, arr, options):
    for i in options:
        arr[n] = arr[n-1] + i
        if n == len(arr) - 1:
            print(arr)
        else:
            chain(n+1, arr, options)

def test():
    chain(1, [0]*4, (10, 100))

if __name__ == '__main__':
    t = int(input().strip())
    for _ in range(t):
        n = int(input().strip())
        a = int(input().strip())
        b = int(input().strip())
        if b > a:
            a, b = b, a
        pos_values = [0]*n
        pos_values[0] = a*(n-1)
        for i in range(1, len(pos_values)):
            pos_values[i] = pos_values[i-1] - (a-b)
        pos_values = list(set(pos_values))
        print(*sorted(pos_values))
Advertisements