## 11517 - Exact Change

Moderator: Board moderators

sir sbu
New poster
Posts: 2
Joined: Thu Aug 02, 2012 8:08 pm

### Re: 11517 - Exact Change

[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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

Input:

Code: Select all

``````1
7395
4
6261
766
1188
7317
``````
AC output:
7449 2
Check input and AC output for thousands of problems on uDebug!

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

### Re: 11517 - Exact Change

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

Your memo array is around 841MB, it could be too much memory.
Check input and AC output for thousands of problems on uDebug!

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

### Re: 11517 - Exact Change

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

Check input and AC output for thousands of problems on uDebug!

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11517 - Exact Change

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

Code: Select all

``AC``
Last edited by Scarecrow on Thu Mar 07, 2013 1:40 am, edited 2 times in total.
Do or do not. There is no try.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 11517 - Exact Change

Scarecrow wrote: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
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11517 - Exact Change

Thanks a lot lbv! It was such a silly mistake in my code.
Do or do not. There is no try.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Wrong Answer: 11517 - Exact Change

Code: Select all

``````import java.io.*;
import java.util.*;
public class Main{
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{
PrintWriter z = new PrintWriter(System.out);
while(T-->0){

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++){
}

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 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

Input:

Code: Select all

``````1
100
4
25
25
50
50
``````
AC output: 100 2
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Wrong Answer: 11517 - Exact Change

Need Help Getting "Wrong Asnwer"

Code: Select all

``````import java.io.*;
import java.util.*;
public class Main{
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{
BufferedWriter z = new BufferedWriter(new OutputStreamWriter(System.out));
while(T-->0){

dp = new Pair[20000+10][110];
marked = new boolean[20000+10][110];
for(int c = 0;c<coins.length;c++){
}

Pair ans = rec(0,0,0);
z.write((ans.value+cap)+" "+ans.noCoins+"\n");
}
z.flush();

}

}

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

http://www.udebug.com/UVa/11517
Click "Random Input", "Go!"
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

### Re: 11517 - Exact Change

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11517 - Exact Change

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
``````
Check input and AC output for thousands of problems on uDebug!