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

Post 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!
_.

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

i/o

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

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

Post by Maniac »

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

Post 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!
_.

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

Post 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.
"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 :)

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

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

Post 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:-)
"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 »

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 »

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 »

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 »

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 »

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

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 »

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 »

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 »

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)”