Page 1 of 3

10684 - The jackpot

Posted: Sun Aug 08, 2004 6:31 am
by _.B._
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!

i/o

Posted: Sun Aug 08, 2004 7:55 am
by sohel
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.

Posted: Sun Aug 08, 2004 11:20 am
by Maniac
a streak in this problem is a continuous subsequence of the given sequence of numbers.

Thanks

Posted: Sun Aug 08, 2004 7:23 pm
by _.B._
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!

Posted: Sun Aug 08, 2004 8:58 pm
by anupam
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.

My first CPP program :)

Posted: Sun Aug 08, 2004 11:08 pm
by _.B._
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.

Posted: Mon Aug 09, 2004 8:03 am
by anupam
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:-)

Posted: Sun Oct 03, 2004 6:54 am
by yiuyuho
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?

Posted: Sun Oct 03, 2004 9:40 pm
by anupam
Yeah, I also think so. It is a positive subsequence for win conds.

Posted: Mon Oct 04, 2004 5:47 pm
by yiuyuho
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).

Posted: Mon Oct 04, 2004 9:32 pm
by anupam
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.

0 bet?

Posted: Fri Sep 16, 2005 5:01 pm
by shu
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:

Re: 0 bet?

Posted: Fri Sep 23, 2005 3:26 am
by Martin Macko
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?

Posted: Tue Nov 22, 2005 7:27 am
by shu
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. :)

10684 -> Runtime Error

Posted: Mon Jan 02, 2006 10:38 am
by yoyakazuma

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