Problem Link :
http://www.codechef.com/CDCK2015/problems/COINX
Author:
Ankur Goel
Tester:
Ankur Goel
Editorialist
Shuchita Garg
DIFFICULTY:
Easy
PREREQUISITES:
Fibonacci numbers
PROBLEM:
Ankur has two boxes containing infinite number of coins of Re 1 and Rs 2 respectively. He is
interested to purchase an item that cost Rs X. So, he took some coins from the first box and
some coins from the 2nd finally he is able to obtain the total amount as Rs X from the coins.
i.e. Suppose number of Re 1 coins =p and number of RS. 2 coins = q.
Then X= p+ 2q;
Find out the total number of ways possible for the man to achieve the total amount as Rs X from the coins.
Note: The order in which he choose the coins also matters i.e. 1 + 1 + 1 + 2 and 2 + 1 + 1 + 1 are considered as different ways.
EXPLANATION:
There can be total F_{x+1} number of ways to find the combinations of 1’s and 2’s that sum to a given amount X. You can use fibonacci algorithm to get the solution.
How to do it

If the amount is less or equal to 86.

If the amount is greater than 86.
</liIn this case, the amount can’t be obtained by using the ‘+’ operator to add the previous two terms as even the largest data type in c or c++ i.e. long long works till the value of 86 in case of fibonacci numbers. Hence, for the amount greater than 86, you have to design a new function that calculates the fibonacci number.
Simply, you can add the previous two terms to get the desired amount.
For that, you can start with the first position, say i=0, and go till the value one greater than the amount X. Add the previous two elements of the element one greater than the amount X i.e. For A[x+1], add elements A[x1] and A[x]. This will give the total number of combinations.

Not getting the answer for amount greater than 40?
Using the desired way, the answer for amount greater than 40 exceeds the limit of integer data type. Instead use long long data type. Not getting the answer for amount greater than 86?
Solution to amount greater than 86 exceeds the limit of data type long long. Use alternate way to find the solution.