Cow Cash [Traditional, 2003]

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure. The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others. Write a program to compute how many ways to construct a given amount of money N (1 <= N <= 10,000) using V (1 <= V <= 25) coins. It is guaranteed that the total will fit into both a signed 'long long' integer (C/C++), 'Int64' (Pascal), and 'long' integers in Java. PROBLEM NAME: money INPUT FORMAT: * Line 1: Two space-separated integers: V and N * Lines 2..V+1: Each line contains an integer that is an available coin SAMPLE INPUT (file money.in): 3 10 1 2 5 OUTPUT FORMAT: * Line 1: A single line containing the total number of ways to construct N money units using V coins. SAMPLE OUTPUT (file money.out): 10

ძროხების ფული – გივი ბერიძის თარგმანი

ძროხებმა თავიანთი მთავრობის შექმნას არ დასჯერდნენ და თავიანთი ფულის სისტემაც კი შექმნეს. ისინი, როგორც რევოლუციონერები არიან დაინტერესებულები მონეტებით. ტრადიციული მონეტები გვხვდება 1, 5,10, 20, 25, 50 და 100 თეთრიანები, ხანდახან 2თეთრიანებიც შეგვხვდება ხოლმე. ძროხებს სურთ რომ გაგიონ თუ რამდენნაირად არის შესაძლებელი, რომ მივიღოთ გარკვეული ოდენობის თანხა მონეტების სხვადასხვა სისტემების მეშვეობით. მაგალითად თუ ავიღებთ მონეტების სიმრავლეს {1,2,5,10,...} შესაძლებელია, რომ მივიღოთ 18 თეთრი რამდენიმენაირად : 18x1, 9x2, 8x2+2x1, 3x5+2+1 და ა.შ. დაწერეთ კოდი, რომელიც გამოითვლის თუ რამდენნაირად შეიძლება მივიღოთ მოცემული ოდენობის თანხა N (1<= N <=10,000) თუ ვიყენებთ V (1<= V <= 25) რაოდენობის მონეტას. მიღებული შედეგი აუცილებლად ჩაეტევა ‘long long’ ის საზღვრებში(C/C++), ‘Int64’(Pascal) და ‘long’ (java)-ში. ამოცანის დასახელება : money შესატანი ინფორმაციის ფორმატი: *ხაზი 1: 2 ცალი მთელი რიცხვი, გამოტოვებული ადგილით მათ შორის V და N * ხაზები 2 დან V+1 ჩათვლით: ყოველი ხაზი შეიცავს რიცხვს, რომელიც ასახავს მონეტის ღირებულებას. შესატანი მნიშვნელობის მაგალითი(ფაილი money.in) 3 10 1 2 5 გამოსატანი მნიშვნელობის ფორმატი: *ხაზი 1: ერთი ხაზი, რომელიც შეიცავს ჯამურ რაოდენობას თუ რამდენნაირად შეიძლება მივიღთ N თანხა V ცალი მონეტის საშუალებით. გამოსატანი მნიშვნელობის მაგალითი (ფაილი money.out) 10

money

For this problem, as we try to find the number of combinations of coins that sum up to a certain amount. We search through every possible combination of coins using a recursive routine that keeps track of previously solved subproblems (combinations of coins that sum up to a different, smaller amount) in a 2 dimensional array. One dimension is used to look up the amount of money the coins sums up to, and the second dimension is used to keep track of what subset of coins are used for the sub problem. It is important to account for the fact that the order of the coins is irrelevant, this is accomplished by restricting the recursive calls of the search to using either the last used coin (to allow for multiple coins of the same type) or a subset coins that have not already been used. #include <stdio.h> int v, n; int coins[25]; long long num_ways[25][10001]; /* search for how many combinations of coins which have an index >= lowest_coin, that sum up to amount */ long long search(int amount, int lowest_coin) { if (amount < 0) return 0; if (num_ways[lowest_coin][amount] != -1) return num_ways[lowest_coin][amount]; long long total = 0; for (int i = lowest_coin; i < v; i++) { total += search(amount - coins[i], i); } num_ways[lowest_coin][amount] = total; return total; } int main() { freopen("money.in", "r", stdin); freopen("money.out", "w", stdout); scanf("%d%d", &v, &n); for (int i = 0; i < v; i++) scanf("%d", &coins[i]); for (int j = 0; j < v; j++) { /* initialize the subproblem lookup array */ for (int i = 1; i <= n; i++) num_ways[j][i] = -1; num_ways[j][0] = 1; } printf("%lld\n", search(n, 0)); return 0; } This is a DP problem that can be computed recursively the only thing you should take care of is integer overflows so you can use c++ long long or java long or BigInteger class. Given that the amount needed is V that uses K coins. You can compute the number of ways using all the first K-1 coins except the last one or you can compute it with all the K coins. Compute(v,k)= the number of ways using all the first K-1 coins except the last one+ compute it with all the K coins Compute(v,k)= compute(v,k-1) /*all but the last one*/ + compute(v-coins[k],k) /*using the last one then the remaining value is v-coins[k]*/ Here is wahab1 java solution using java BigInteger class /* ID: wahab1 PROG: money LANG: JAVA */ import java.math.*; import java.io.*; import java.util.*; public class money { static int coins[]=new int[25]; static BigInteger val[][]=new BigInteger[25][10001]; public static BigInteger compute(int v,int k) { if(k==0) return v%coins[k]==0?BigInteger.ONE:BigInteger.ZERO; if(v==0) return BigInteger.ONE; if(v<0) return BigInteger.ZERO; if(val[k][v]!=null) return val[k][v]; return val[k][v]=compute(v,k-1).add(compute(v-coins[k],k)); } public static void main(String[] args) throws Exception { FileReader in=new FileReader("money.in"); PrintWriter out=new PrintWriter(new FileWriter("money.out")); StreamTokenizer st=new StreamTokenizer(in); int n,v; st.nextToken(); n=(int)st.nval; st.nextToken(); v=(int)st.nval; for(int i=0;i<n;i++) { st.nextToken(); coins[i]=(int)st.nval; } out.println(compute(v,n-1)); out.close(); } }

money – გივი ბერიძის თარგმანი

გარჩევა: რადგან ჩვენ გვჭირდება რომ ვიპოვოთ კომბინაციები მონეტებისა, რათა მივიღოთ კონკრეტული ოდენობის თანხა ჩვენ უნდა ვეძებოთ ყველა შესაძლო კომბინაცია რეკურსიული გზით, რომელიც ინახავს ყველა ქვე-ამოცანებში მიღებულ შედეგებს 2 განზომილებიან მასივში(რათა პროგრამის მუშაობის დრო არ იყოს ძალიან დიდი). მასივის ერთი განზომილება გამოიყენება იმისათვის, რომ გავიგოთ თუ რა თანხაზე ადის მონეტების ჯამი ხოლო მეორე განზომილება გამოიყენება რომ თვალყური ვადევნოთ თუ მონეტების სიმრავლიდან რა ქვესიმრავლე გამოიყენება ქვე-ამოცანის ამოსახსნელად. მნიშვნელოვანია, ყურადღება გავამახვილოთ ფაქტზე, რომ მონეტების მიმდევრობას მნიშვნელობა არ აქვს. ამას გავითვალისწინებთ თუ რეკიურსიული გამოძახებით ძებნისას გამოვიყენებთ ან მხოლოდ ბოლოს გამოყენებულ მონეტას ან მონეტების ქვესიმრავლეს, რომელიც ჯერ არ გამოგვიყენებია. ამ ამოცანის დინამიური პროგრამირებით დაწერილი კოდი, რომელიც რეკურსიულად იწერება შეიძლება აჭარბებდეს int-ის ზომას c++-ში ასე, რომ უნდა გამოვიყენოთ long long-ი c/c++-ში ხოლო java-ში biginteger ან long-ი. როცა მოცემული გვაქვს V მისაღები თანხა ხოლო K მონეტა, ამოცანის ამოხსნა შესაძლებელია ორნაირად, ერთი, შედეგი დავთვალოთ პირველი k-1 მონეტის გამოყენების გზები გარდა ბოლო მონეტისა, ან დავთვალოთ ყველა K მონეტის მეშვეობით. Compute(v,k)= შედეგი დავთვალოთ პირველი k-1 მონეტის გამოყენების გზები გარდა ბოლო მონეტისა + დავთვალოთ ყველა K მეშვეობით Compute(v,k)= compute(v,k-1) /*გამოვიყენოთ ყველა გარდა ბოლო მონეტისა*/ + compute(v-coins[k],k) /*გამოვიყენოთ მხოლოდ ბოლო მონეტა და საბოლოო მნიშვნელობა იქნება v-coins[k]*/ #include <stdio.h> int v, n; int coins[25]; long long num_ways[25][10001]; /* ვეძებთ თუ რამდენი ისეთი მონეტის კომბინაციით, რომელთა index >= lowest_coin-ზე მიიღება გადმოცემული amount-ი*/ long long search(int amount, int lowest_coin) { if (amount < 0) return 0; if (num_ways[lowest_coin][amount] != -1) return num_ways[lowest_coin][amount]; long long total = 0; for (int i = lowest_coin; i < v; i++) { total += search(amount - coins[i], i); } num_ways[lowest_coin][amount] = total; return total; } int main() { freopen("money.in", "r", stdin); freopen("money.out", "w", stdout); scanf("%d%d", &v, &n); for (int i = 0; i < v; i++) scanf("%d", &coins[i]); for (int j = 0; j < v; j++) { /* ქვეამოცანების მასივის ინიციალიზაცია(დინამიური პროგრამირება) */ for (int i = 1; i <= n; i++) num_ways[j][i] = -1; num_ways[j][0] = 1; } printf("%lld\n", search(n, 0)); return 0; }

Here is wahab1 java solution using java BigInteger class

import java.math.*;
import java.io.*;
import java.util.*;

public class money
{

static	int coins[]=new int[25];
static	BigInteger val[][]=new BigInteger[25][10001];
	public static BigInteger compute(int v,int k)
	{
		if(k==0)
			return v%coins[k]==0?BigInteger.ONE:BigInteger.ZERO;
		if(v==0)
			return BigInteger.ONE;
		if(v<0)
			return BigInteger.ZERO;
		if(val[k][v]!=null)
			return val[k][v];
		return val[k][v]=compute(v,k-1).add(compute(v-coins[k],k));
	}
		
	
	public static void main(String[] args) throws Exception
	{
		FileReader in=new FileReader("money.in");
		PrintWriter out=new PrintWriter(new FileWriter("money.out"));
		StreamTokenizer st=new StreamTokenizer(in);
		int n,v;
		st.nextToken();
		n=(int)st.nval;
		st.nextToken();
		v=(int)st.nval;
		for(int i=0;i<n;i++)
		{
			st.nextToken();
			coins[i]=(int)st.nval;
		}
		out.println(compute(v,n-1));
		out.close();
		
	}
	
}