Page 1 of 1

11832 - Account Book

Posted: Wed Aug 31, 2011 4:48 pm
by Angeh
Can somebody Tell why the result for first Case is that ...

we can make 7 by this these ways
-1+2-3+4+5 =7
+1+2+3-4+5 =7
+1-2-3-4-5 =7

Could someone explain the output ...

Re: 11832 - Account Book

Posted: Mon Feb 23, 2015 3:24 pm
by bradd123
Your third expression is wrong.
Take these two expressions.
-1+2-3+4+5 =7
+1+2+3-4+5 =7
You can clearly see that only second and last transactions are same in both expressions. Remaining are ambiguous to tell whether that is income or expense.

Re: 11832 - Account Book

Posted: Mon Feb 23, 2015 5:38 pm
by bradd123
Hi, I got Time Limit Exceeded for this problem. I used dp with memoization. How to optimize this code?

Code: Select all

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[45][32010];
int N,F;
int a[45];
char path[45];
bool AccBook(int idx,int sum){
    if(idx==N){
        if(sum==F) return true;
        else return false;
    }
    if(!dp[idx][sum+16000]) return false;
    bool tmp=false;
    if(AccBook(idx+1,sum+a[idx])){
        if(path[idx]=='$' || path[idx]=='+') path[idx]='+';
        else path[idx]='?';
        tmp=true;
    }
    if(AccBook(idx+1,sum-a[idx])){
        if(path[idx]=='$' || path[idx]=='-') path[idx]='-';
        else path[idx]='?';
        tmp=true;
    }
    if(!tmp) dp[idx][sum+16000]=false;
    return dp[idx][sum+16000];
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(scanf("%d %d",&N,&F)){
        if(N==0&&F==0) break;
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        memset(dp,true,sizeof dp);
        for(int i=0;i<45;i++) path[i]='$';
        if(AccBook(0,0)){
            for(int i=0;i<N;i++) printf("%c",path[i]);
            printf("\n");
        }
        else printf("*\n");
    }
}

Re: 11832 - Account Book

Posted: Tue Feb 24, 2015 12:00 am
by brianfry713
Try input:

Code: Select all

40 0
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000
0 0
AC code should quickly print 40 ?'s. Your code is reading and writing outside of array bounds.