11517 - Exact Change

[sir sbu]

[quote="sir sbu"]hi
i don't know why my code is WR
it's my code
pl help me :((
#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define ll long long
#define vec vector

int n;
int m;
int cnt2;
bool flag;
bool flag1;
bool mark [101];
vec <int>amin;
int a[101][30001];
int f(int u,int sum)
{
if(sum >= n )
{
if(flag && cnt2 == sum)
flag1=1;
return sum;
}
if(u == -1 )
{
return 10000000;
}
if(a[u][sum] > 0)
return a[u][sum];
mark [u]=1;
int cnt=f(u-1,sum+amin[u]);
if(flag1)
return cnt;
mark [u]=0;
int cnt1=f(u-1,sum);
if(flag1)
return cnt1;
if(cnt < cnt1 )
{
mark [u]=1;
}
else
{
mark [u]=0;
cnt=cnt1;
}
return a[u][sum]=cnt;
}
int main ()
{
int number;
cin>>number;
while(number--)
{
cin>>n>>m;
memset(a,0,sizeof a);
memset(mark,0,sizeof mark);
for(int i=0;i<m;i++)
{
int k;
cin>>k;
amin.push_back(k);
}
flag=0;
flag1=0;
sort(amin.begin(),amin.end());
cnt2=0;
cnt2=f(m-1,0);
flag=1;
memset(a , 0,sizeof a );
memset(mark , 0,sizeof mark );
int k=f(m-1,0);
k=0;
for(int i=0;i<m;i++)
k+=mark [i];
cout<<cnt2<<" "<<k<<endl;
amin.clear();
}
return 0;
}[/quote]

[brianfry713]

Input:

Code: Select all

1
7395
4
6261
766
1188
7317

AC output:
7449 2

[mmfrb]

Hello, guys. My code works well in my compiler, but when I submit it by IDEONE it gives me Runtime Error : Sigkill

I don't know where it is coming from. If someone could help me I would appreciate. Thanks

Code: Select all

#include <cstdio>
#include <utility>
#include <cstring>
#define INF 2000000

using namespace std;

typedef pair <int, int> ii;

int TC, price, coins[105], n, i, j, k;
ii result, memo[105][10005][105];

ii min(ii a, ii b)
{
	return (a < b) ? a : b;
}

ii value(int coin, int money, int m)
{
	if(money >= price) return ii(money, m);
	if(coin == n) return ii(INF, INF);
	if(memo[coin][money][m] != ii(-1, -1)) return memo[coin][money][m];
	return memo[coin][money][m] = min(value(coin+1, money, m), value(coin+1, money + coins[coin], m+1));
}

int main()
{
	scanf("%d", &TC);
	while(TC--)
	{
		scanf("%d", &price);
		scanf("%d", &n);
		for(i = 0; i < n; ++i) scanf("%d", &coins[i]);
		for(i = 0; i < n; ++i) 
			for(j = 0; j < 10005; ++j)
				for(k = 0; k < n; ++k) memo[i][j][k] = ii(-1, -1);
		result = value(0, 0, 0);
		printf("%d %d\n", result.first, result.second);
	}
	return 0;
}

I've tried to memset the memo array too, but gives me the same error.

[brianfry713]

Your memo array is around 841MB, it could be too much memory.

[mmfrb]

Hmm... so is there a way to make it better or my recursive implementation is impossible? ;x;x

[brianfry713]

http://www.algorithmist.com/index.php/UVa_11517

[Scarecrow]

Some one can help me out here please? Getting WA.

Code: Select all

AC

[lbv]

Some one can help me out here please? Getting WA.

You may try these cases:

Input

Code: Select all

2

35
1
75

8
4
41
98
30
79

Output

Code: Select all

75 1
30 1

[Scarecrow]

Thanks a lot lbv! It was such a silly mistake in my code.

[raj]

Need Help Getting 'Wrong Answer'

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
	public static BufferedReader k;
	public static int [] coins;
	public static Pair [][] dp;
	public static boolean [][] marked;
	public static int cap;
	
	
	public static Pair rec(int i,int value,long NoOfCoin){
		if(i>=coins.length){
			if(value<cap){
				return new Pair(-1,-1);
			}
			else{
				return new Pair(value-cap,NoOfCoin);
			}
		}
		
		
		if(value>=cap){
			return new Pair(value-cap,NoOfCoin);
		}
		else{
			if(marked[i][value]==true){
				return dp[i][value];
			}
			else{

				dp[i][value] = Min(rec(i+1,value+coins[i],NoOfCoin+1),rec(i+1,value,NoOfCoin));

				
				marked[i][value] = true;
				return dp[i][value];
			}
		}
	}
	
	
	
	
	
	public static Pair Min(Pair a,Pair b){
		if(a.value==-1){
			return b;
		}
		else if(b.value==-1){
			return a;
		}
		else{
			if(a.value==b.value){
				if(a.noCoins<b.noCoins){
					return a;
				}
				else{
					return b;
				}
			}
			else if(a.value<b.value){
				return a;
			}
			else{
				return b;
			}
		}
			
	}
	
	
	
	
	
	
	

	
	public static void main(String [] args)throws IOException{
		k = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter z = new PrintWriter(System.out);
		int T = Int(read());
		while(T-->0){
			cap = Int(read());
			
			coins = new int[Int(read())];
			dp = new Pair[coins.length][10000+10];
			marked = new boolean[coins.length][10000+10];
			//System.out.println(T);
			for(int c = 0;c<coins.length;c++){
				coins[c] = Int(read());
			}
			
			Pair ans = rec(0,0,0);
			z.println((ans.value+cap)+" "+ans.noCoins);
		}
		z.flush();

	}

	
	
	
	
	
	
	
	public static void fill(long [][] array,int element){
		for(long [] sub : array){
			Arrays.fill(sub,element);
		}
	}
	
	
	
	
	
	

	
	
	public static String read()throws IOException{
		return k.readLine();
	}
	
	
	
	public static int Int(String line){
		line = line.replace(" ","");
		return Integer.valueOf(line);
	}
	
	
}




class Pair{
	int value;
	long noCoins;
	public Pair(int value,long noOfCoins){
		this.value = value;
		this.noCoins = noOfCoins;
	}
}

[brianfry713]

Input:

Code: Select all

1
100
4
25
25
50
50

AC output: 100 2

[raj]

Need Help Getting "Wrong Asnwer"

Code: Select all

import java.io.*;
import java.util.*;
public class Main{
	public static BufferedReader k;
	public static int [] coins;
	public static Pair [][] dp;
	public static boolean [][] marked;
	public static int cap;

	
	
	public static Pair rec(int i,int value,int NoOfCoin){
		if(i>=coins.length){
			if(value<cap){
				return new Pair(-1,-1);
			}
			else{
				return new Pair(value-cap,NoOfCoin);
			}
		}
		
		
		if(value>=cap){
			return new Pair(value-cap,NoOfCoin);
		}
		else{
			if(marked[value][NoOfCoin]==true){
				return dp[value][NoOfCoin];
			}
			else{
				dp[value][NoOfCoin]= Min(rec(i+1,value+coins[i],NoOfCoin+1),rec(i+1,value,NoOfCoin));
				
				marked[value][NoOfCoin] = true;
				return dp[value][NoOfCoin];
			}
		}
	}
	
	
	
	
	
	public static Pair Min(Pair a,Pair b){
		if(a.value==-1)return b;
		if(b.value==-1)return a;
		
		
		if(a.value==b.value){
				if(a.noCoins<b.noCoins){
					return a;
				}
				else{
					return b;
				}
		}
		else if(a.value<b.value){
			return a;
		}
		else{
			return b;
		}	
	}
	
	
	public static void main(String [] args)throws IOException{
		k = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter z = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Int(read());
		while(T-->0){
			cap = Int(read());
			
			coins = new int[Int(read())];
			dp = new Pair[20000+10][110];
			marked = new boolean[20000+10][110];
			for(int c = 0;c<coins.length;c++){
				coins[c] = Int(read());
			}
			
			Pair ans = rec(0,0,0);
			z.write((ans.value+cap)+" "+ans.noCoins+"\n");
		}
		z.flush();

	}

	
	public static String read()throws IOException{
		return k.readLine();
	}
	
	
	
	public static int Int(String line){
		return Integer.valueOf(line);
	}
	
	
}

class Pair{
	int value;
	int noCoins;
	public Pair(int value,int noOfCoins){
		this.value = value;
		this.noCoins = noOfCoins;
	}
}

[brianfry713]

http://www.udebug.com/UVa/11517
Click "Random Input", "Go!"

[raj]

All the random inputs works fine but getting wrong answer..

[brianfry713]

Input:

Code: Select all

1
2895
17
2135
1071
1386
2398
254
1156
2831
1095
1147
1811
1619
1464
844
1562
117
60
1112

AC output:

Code: Select all

2895 4