10684 - The jackpot

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

Moderator: Board moderators

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

10684 - The jackpot

Post by _.B._ » Sun Aug 08, 2004 6:31 am

Greetings!
I thought this problem was not supposed to be a tough one, but I'm getting a hard time to get it ACed.
Please, what's the right output for this input?:

Code: Select all

4
0 0 0 0
4
0 0 0 -1
6
12 -4 -10 4 4 9
6
12 -4 -10 4 0 9
5
4 9 -10 -4 12
0
Hopefuly it'll help me understand the meaning of the "Streak".
Thanks in advance!
_.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

i/o

Post by sohel » Sun Aug 08, 2004 7:55 am

I get the following output for your input:
Losing streak.
Losing streak.
The maximum winning streak is 17.
The maximum winning streak is 13.
The maximum winning streak is 13.
Hope it helps.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sun Aug 08, 2004 11:20 am

a streak in this problem is a continuous subsequence of the given sequence of numbers.

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks

Post by _.B._ » Sun Aug 08, 2004 7:23 pm

Greetings!
Sohel, thanks once again. Thanks Maniac.
I'm still getting WA :-?
Some problems make me feel like Manzoor... some others make me feel so ignorant.

Keep posting!
_.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sun Aug 08, 2004 8:58 pm

My algo is as following:
let pre=previous profit.
max=maximum profit
then for a single input number a
if pre+a>0 pre=pre+a;
else pre=0;
if(pre+a>max) max=pre+a;

print just max.
I think this will help you getting wrong part of your algorithm and any two for loop system will get Tle (i think). So use )(n) solution.
"Everything should be made simple, but not always simpler"

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

My first CPP program :)

Post by _.B._ » Sun Aug 08, 2004 11:08 pm

Greetings!
Well, don't FLAME me for this but... I forgot to print the '.' after the Maximun :o :o :o
Anyway, Anupam, thanks a lot for the algo, I re-estructured mine.
Thanks to all!, and keep posting!

Best regards.
_.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Aug 09, 2004 8:03 am

You are not the one who forget to put '.', many times I forget such characters. That is why now, I just copy the output from the sample output of the problem and then replace if necessary.
Good luck:-)
"Everything should be made simple, but not always simpler"

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Oct 03, 2004 6:54 am

hey anupam,

so the problem comes down to MCSS, but I though the problem states :
he can identify patterns of consecutive wins and elaborate a win-win strategy.
A bet is an amount of money and is either winning (and this is recorded as a positive value).

So shouldn't consecutive wins be a continuous subsequence of "positive" subsequence rather then just a subsequence?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sun Oct 03, 2004 9:40 pm

Yeah, I also think so. It is a positive subsequence for win conds.
"Everything should be made simple, but not always simpler"

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon Oct 04, 2004 5:47 pm

so the judge data is incorrect!

because
3
10 -1 10

will produce 19 with MCSS algorithm (AC), but consecutive positive values should just give 10 (Result according to problem wording).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Oct 04, 2004 9:32 pm

O O, I think I failed to understand what you were talking about.

>>he can identify patterns of consecutive wins and elaborate a win-win strategy. A bet is an amount of money and is either winning (and this is recorded as a positive value). So shouldn't consecutive wins be a continuous subsequence of "positive" subsequence rather then just a subsequence?<<
consecutive wins doesn't mean consecutive sequence, I may not be correct. as in your example,
10 -1 10
The first win is when you got 10.
then you lose -1
and again got 10 so, now you won total 19.
So, there are two win situations(not consecutive) and 1 fail situation. I think, judge had the same thought in mind.
"Everything should be made simple, but not always simpler"

shu
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:

0 bet?

Post by shu » Fri Sep 16, 2005 5:01 pm

hmm.. i don't understand. I think there's an invalid statement in this problem.
Each bet is an integer greater than 0 and less than 1000.
which means 0 < bet < 1000, right?

but i got WA because of this one...

Code: Select all

if ( result < 0 ) puts( "Losing streak." );
and i got AC when..

Code: Select all

if ( result <= 0 ) puts( "Losing streak." );
could anyone explain to me how to get maximum result = 0 without any single 0 bet :roll:
best regards,
shu

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 0 bet?

Post by Martin Macko » Fri Sep 23, 2005 3:26 am

shu wrote:hmm.. i don't understand. I think there's an invalid statement in this problem.
Each bet is an integer greater than 0 and less than 1000.
which means 0 < bet < 1000, right?

but i got WA because of this one...

Code: Select all

if ( result < 0 ) puts( "Losing streak." );
and i got AC when..

Code: Select all

if ( result <= 0 ) puts( "Losing streak." );
could anyone explain to me how to get maximum result = 0 without any single 0 bet :roll:
What does result mean in your solution? Have you initialised it properly?

shu
New poster
Posts: 6
Joined: Sat Jul 16, 2005 1:43 pm
Contact:

Post by shu » Tue Nov 22, 2005 7:27 am

result is a variable containing the maximum-streak from each testcase. Ofcourse I have it initialized properly.

In the problem description, we can found that there will be NO 0 (zero) bet in each input-set, only negative or positive value will exists. Do we agree with this? If so, I think it's clear that it is impossible to get 0 (zero) maximum-streak from that condition. :D

My WA code went wrong because there're exists input-set such maximum-streak is 0. The only explanation I could think is there're 0 (zero) bets.

I have checked the judge-input, and I found 0 bet there. :)
best regards,
shu

yoyakazuma
New poster
Posts: 1
Joined: Mon Jan 02, 2006 10:28 am

10684 -> Runtime Error

Post by yoyakazuma » Mon Jan 02, 2006 10:38 am

Code: Select all

#include<iostream> 
using namespace std;

int main(){
    int check[10005][10005],money[10005],a,b,n;
    while(cin >> n){
       if(n==0) break;
       int sum=0;
       for(a=0;a<n;a++){
          cin >> money[a];
          check[a][a]=money[a];
          if(check[a][a]>sum)
             sum=check[a][a];
       }
       for(a=0;a<n-1;a++){
          for(b=a+1;b<n;b++){
             check[a][b]=check[a][b-1]+money[b];
             if(check[a][b]>sum) 
                sum=check[a][b];
          }
       }
       if(sum<=0)
          cout << "Losing streak." << endl;
       else
          cout << "The maximum winning streak is " << sum << "." << endl;
    }
    return 0;
}

why??
I can't find any problem...

Post Reply

Return to “Volume 106 (10600-10699)”