12032 - The Monkey and the Oiled Bamboo

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

Moderator: Board moderators

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

12032 - The Monkey and the Oiled Bamboo

Here are some test case for those who are getting wa:

Code: Select all

``````5
6
1 6 10 14 20 30
10
10 20 30 45 60 75 100 234 4546 45666
3
5 10 15
5
10 20 31 41 51
6
1 2 3 10 20 30``````

output:

Code: Select all

``````Case 1: 10
Case 2: 41120
Case 3: 6
Case 4: 12
Case 5: 11
``````

But the judge data should contain more tricky cases. I got wa trying to solve the problem with logic. Than i ran a simple binary search simulating the scenario and got ac easily.

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

Re: 12032

ACCEPTED
Last edited by Eather on Fri Jul 22, 2011 1:56 pm, edited 1 time in total.

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

Re: 12032

Shafaet_du wrote:Here are some test case for those who are getting wa:

Code: Select all

``````5
6
1 6 10 14 20 30
10
10 20 30 45 60 75 100 234 4546 45666
3
5 10 15
5
10 20 31 41 51
6
1 2 3 10 20 30``````

output:

Code: Select all

``````Case 1: 10
Case 2: 41120
Case 3: 6
Case 4: 12
Case 5: 11
``````
this is edited code. Im getting WA. Please help me why my code is not giving correct answer?

Code: Select all

``````Accepted
``````

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

Re: 12032

I don't know what is wrong with my code...please anyone help me....

Code: Select all

``````#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
long a[100090],i,j,k,t,n;
scanf("%ld",&t);
for(i=0;i<t;i++)
{
scanf("%ld",&n);
for(j=0;j<n;j++)
scanf("%ld",&a[j]);
k=a[0];
for(j=n-2;j>=0;j--)
{
if(a[j+1]-a[j]>k)
k=a[j+1]-a[j];
else if(a[j+1]-a[j]==k)
k++;
}
printf("Case %ld: %ld\n",i+1,k);
}
return 0;
}
/code]``````
If you have determination, you can do anything you want....

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 12032

naseef, check your output for following input.

Code: Select all

``````1
3
3 2 2
``````

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm

Re: 12032

My code gives output 3...... I think it is the right one...What is wrong???
If you have determination, you can do anything you want....

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

Re: 12032

I got WA !
can anybody give me some testcase for my weak point...
my code :

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
int t , n;
int a , b , k;
scanf("%d", &t);
for(int pp = 0; pp < t ; pp++)
{
k = -1;
a = 0;
scanf("%d",&n);
for(int i = 0 ; i < n ; i++)
{
scanf("%d" , &b);
if(b - a == k)
k++;
else
k = max(k , b - a);
a = b;
}
printf("Case %d: %d\n" , pp +1 , k);
}
return 0;
}

``````

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 12032

oh.. im sorry.. here's the input i intended to post

Code: Select all

``````1
4
3 5 7 9
``````
correct answer would be 4. but your code gives 3.

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

Re: 12032

Input:

Code: Select all

``````1
2
3 5``````
AC output:

Code: Select all

``````Case 1: 3
``````
Check input and AC output for thousands of problems on uDebug!

dcclyde
New poster
Posts: 2
Joined: Fri Jul 05, 2013 10:14 am

Re: 12032

Anyone want to help me? My code passes all test cases given in this thread and a bunch of others that I wrote myself, but I still get WA.

My strategy is to start from the top of the ladder and move downward, at each stage keeping track of how much strength I need to climb the rest of the ladder.

Code: Select all

``````
#include <iostream>

using namespace std;

int main()
{
int T;
int n;
int* rungs;
int str;
cin >> T;
for (int i = 1; i <= T; i++)
{
cout << "Case " << i << ": ";
cin >> n;
rungs = new int[n+1];
rungs[0] = 0;
for (int j = 0; j <= n-1; j++)
{
cin >> rungs[j+1];
}
str = -1;
for (int jump = n; jump >= 0; jump--)
{
if (rungs[jump+1] - rungs[jump] == str)
str += 1;
else if (rungs[jump+1] - rungs[jump] > str)
str = rungs[jump+1] - rungs[jump];
}
cout << str << endl;
delete [] rungs;
}
return 0;
}

``````

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

Re: 12032

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

dcclyde
New poster
Posts: 2
Joined: Fri Jul 05, 2013 10:14 am

Re: 12032

brianfry713 wrote:Doesn't match the sample I/O.
It certainly does when I run it, unless there's some formatting mistake that I'm not noticing. Admittedly I'm compiling in visual c++, but I wouldn't expect that to matter here. Which case was wrong when you tried it?

Thanks for taking a look in any case

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

Re: 12032

Check input and AC output for thousands of problems on uDebug!

reza_cse08
New poster
Posts: 8
Joined: Sun Nov 17, 2013 9:55 pm

Re: 12032

/**************************************12032_monkey.cpp**************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

int main()
{
long int t, n, m, p, l, d, i, a[100000] = {0};

t = 0;
cin>>n;
while(n!=0)
{
t++;
cin>>p;
d = 0;
for(i= 0;i<p;i++)
{
cin>>a;
if(i==0)
{
d = a[0];
}
else if(i>0)
{
if((a - a[i-1])>d)
{
d = a-a[i-1];
}
}
}
m = d;
for(i = 0;i<(p-1);i++)
{
if(a[0]==d)
{
d--;
}
if((a[i+1]-a)==d)
{
d--;
}
else if(d<(a[i+1]-a))
{
m++;
d = m;
i = -1;
}
}
cout<<"Case "<<t<<": "<<m<<endl;
memset(a, 0,sizeof(a));
n--;
}
return 0;
}

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

Re: 12032

Move lines 37-40 outside of the for loop:
if(a[0]==d)
{
d--;
}
Check input and AC output for thousands of problems on uDebug!