11832 - Account Book

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

11832 - Account Book

Post by Angeh » Wed Aug 31, 2011 4:48 pm

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 ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 11832 - Account Book

Post by bradd123 » Mon Feb 23, 2015 3:24 pm

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.

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 11832 - Account Book

Post by bradd123 » Mon Feb 23, 2015 5:38 pm

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

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

Re: 11832 - Account Book

Post by brianfry713 » Tue Feb 24, 2015 12:00 am

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

Post Reply

Return to “Volume 118 (11800-11899)”