[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Author Message
Mihail Dolinskiy

Topics: 1560
Messages: 38157

My Profile
... 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.

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();
		
	}
	
}


Это цитата из анализа задачи USACO 2007 October Gold: Problem 1. Cow Cash
Aleksey Gulenko

Topics: 4
Messages: 165

My Profile
long long (__int64) из C++ соответствует типу Int64 (для unsigned - QWord) из Free Pascal
______________________
// LeX
Mihail Dolinskiy

Topics: 1560
Messages: 38157

My Profile
а BigInteger?
Насколько я понимаю, это БОЛЬШЕ чем int64?
Или вообще с неограниченной разрядностью?
Fedor Biryukov

Topics: 0
Messages: 1

My Profile
BigInteger - это встроенная в java длинная арифметка, самому писать не надо.
Mihail Dolinskiy

Topics: 1560
Messages: 38157

My Profile
Both C++ and Java have priority queues in their standard library.

Это цитата из анализа задачи 2010 February Silver : 2. Chocolate Giving
Mihail Dolinskiy

Topics: 1560
Messages: 38157

My Profile
Достаточные знания языка Java для спортивного программирования (Codeforces)
 
Forum Index ->Олимпиадное программирование ->Обсуждение теории
Time:0,046