A Group Portal
  Go Back to Contest Details

Firstnaukri Code Ninja Programming Contest 2012

Programming Puzzle
Programming Puzzle phase is closed. View Winners
* Write a program in C to solve the following puzzle.
* Compress your source code in a .zip file and upload the same before the deadline.

Puzzle:
Rahul was an information technology student who lives alone. Every day he orders pizza and cola from his favorite outlet. He was particular about paying the exact amount for all purchases and always kept sufficient coins of different denominations in his purse. Every time he eats his food and gulps down his cola, he wonders, if he had chosen different combinations of currency notes and coins for paying, how many different transactions could have been possible for the same purchase amount.
Write a program that reads a file with the amount of currencies and coins that Rahul has, along with the amount to be paid and outputs the number of ways in which the amount could be paid.

Input Format:
The first line of the input file contains an integer N. Each of the next N lines contain numbers A,B separated by spaces such that Bi is the number of notes/coins that Rahul has with denomination Ai. Ai, Bi refers to the value of A,B in the i-th line. Ai ,Bi are non-zero. After all the lines of A,B pairs the last line with have a number C which represents the amount of purchase. C is also an integer. N will be less than 50.

Output:
The output of the program should be a file which has just one number - the number of ways in which the amount can be paid. The program should be written in C language and the source code should be uploaded. The program will take two arguments - the name of the input file and the name of the output file. The code will be compiled in gcc and any compilation error will make the participant disqualified.

Sample Input:
2
10 2
5 2
20

Sample Output:
2

Explanation:
An amount of 20 could be made in 2 ways:
10*2
10*1 + 5*2

Winners List

Participant Name/ College/ University
  • Amit Ranjan
    Birla Institute of Technology

Contest by

Prize