madslayer's blog

By madslayer, history, 7 years ago, In English

Gautam as an employee got a target from his boss Jawed. His target is to increase the sale of the goods by selling the number of goods to the ith customer equal to sum of number of goods he sold to the last three customers. As Gautam is weak in Mathematics now your job is to calculate the number of goods he has to sell to ith customer. He had already sold 1,2,3 number of goods to the first three customers respectively.

Input Format: The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of the test case contains an integer I denoting the Ith customer.

Output Format: For each test case you have to tell the number of goods Gautam have to sell to the Ith customer separated by new line. As the numbers can be quite large, print them modulo 10^9+7.

Constraints: 1<=T<=10 4<=I<=10^18 Input: 2 5 56 Output: 11 165552744 https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/salesman-and-his-target/description/ Time Limit: 1.0 sec(s) for each input file. I am unable to think of an approach better than O(n). How should it be solved?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it