## 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

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

### 10684 - The jackpot

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".
_.

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

### i/o

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
a streak in this problem is a continuous subsequence of the given sequence of numbers.

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

### Thanks

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:
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"

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

### My first CPP program :)

Greetings!
Well, don't FLAME me for this but... I forgot to print the '.' after the Maximun
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:
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:
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:
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:
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:
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?

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
best regards,
shu

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

### Re: 0 bet?

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
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:
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.

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

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...