COINX - Editorial

general
1

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 &#61p and number of RS. 2 coins &#61 q.
Then X= p&#43 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 &#43 1 &#43 1 &#43 2 and 2 &#43 1 &#43 1 &#43 1 are considered as different ways.

EXPLANATION:

There can be total Fx+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.

    • 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[x-1] and A[x]. This will give the total number of combinations.

  • If the amount is greater than 86.

    </li

    In 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.

### Problems that can be encountered

  • 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.