10611 - The Playboy Chimp

[sadia_swarna72]

i couldn't understand why um getting wa .here is my code..

#include<cstdio>
using namespace std;
int main()
{
long int shrt,tall,n=0,h,low,high,q,mid,num,a[50002],i,b[25001];
scanf("%ld", &num);
scanf("%ld", &a[n++]);
for(i=1;i<num;i++)
{
scanf("%ld", &h);
if(h != a[n-1])
a[n++]=h;
}
scanf("%ld", &q);
for(i=0;i<q;i++)
scanf("%ld", &b);
for(i=0;i<q;i++)
{
if((a[0]==a[n-1]) && (b==a[0]) && (b==a[n-1]))
{
printf("X X\n");
continue;
}
if(b>a[n-1])
{
printf("%ld X\n",a[n-1]);
continue;
}
if(b==a[n-1])
{
printf("%ld X\n",a[n-2]);
continue;
}
if(b<a[0])
{
printf("X %ld\n",a[0]);
continue;
}
if(b==a[0])
{
printf("X %ld\n",a[1]);
continue;
}
low=0;
high=n-1;
tall=shrt=0;
while(low<high)
{
mid=(low+high)/2;
if(a[mid]==b)
{
shrt=mid-1;
tall=mid+1;
break;
}
else if(a[mid]<b)
low=mid+1;
else
high=mid-1;
}
if(tall==0)
printf("%ld %ld\n",a[low-1],a[high]);
else
printf("%ld %ld\n",a[shrt],a[tall]);
}
return 0;
}
give me some test cases

[brianfry713]

Input:

Code: Select all

4
1 4 5 7
8
1 2 3 4 5 6 7 8

AC output:

Code: Select all

X 4
1 4
1 4
1 5
4 7
5 7
5 X
7 X

[Angry Bird]

Please help me. Getting WA. All sample I/O matched.

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<utility>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<sstream>
#include<stack>
#include<list>
#include<iterator>
#include <bitset>
using namespace std;


#define lop(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define CLEAR(t) memset((t), 0, sizeof(t))
typedef long long int64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define PI 3.1415926535897932384626433832
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back
#define bg begin
#define pf printf
#define sf scanf
#define inp(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d%d",&x,&y)
#define Get(s) getline(cin,s)
#define Sort(v) sort(v.begin(),v.end());
#define out(x) printf("%d\n",x);
#define TC printf("Case %d: ",++cas);
#define TC1 printf("CASE# %d:\n",++cas);

int main()
{
    int n,x,i;
    inp(n);
    vector<int>v,vq;
    set<int>s;
    set<int>::iterator it;

    while(n--)
    {
        inp(x);
        s.insert(x);
    }

    for(it = s.begin(); it != s.end(); it++) {
        v.pb(*it);
    }


    int q,m;
    inp(q);
    while(q--)
    {
        inp(m);
        vq.pb(m);
    }


    lop(i,vq.size())
    {
        int low_ind=0;
        int high_ind=vq.size()-1;
        int mid_ind;

        while(low_ind<=high_ind)
        {
            mid_ind=(low_ind+high_ind)/2;

            if(vq[i]==v[mid_ind])
                break;

            else if(vq[i]<v[mid_ind])
            {
                high_ind=mid_ind-1;
            }

            else
            {
                low_ind=mid_ind+1;
            }
        }

        if(vq[i]==v[mid_ind])
        {
            if((vq[i]<=v[0])&&(vq[i]>=v[v.size()-1]))
            {
                pf("X X");
            }

            else if(vq[i]<=v[0])
            {
                pf("X %d",v[mid_ind+1]);
            }

            else if(vq[i]>=v[v.size()-1])
            {
                pf("%d X",v[mid_ind-1]);
            }

            else
            {
                pf("%d %d",v[mid_ind-1],v[mid_ind+1]);
            }

        }

        else if(vq[i]>=v[v.size()-1])
        {
            pf("%d X",v[v.size()-1]);
        }

        else if(vq[i]<=v[0])
        {
            pf("X %d",v[0]);
        }

        else
        {
            pf("%d %d",v[high_ind],v[low_ind]);
        }
        pf("\n");
    }
    return 0;
}

[brianfry713]

Change line 78 to:
int high_ind=v.size()-1;

[uDebug]

Here are some test cases I found useful during testing / debugging. Thanks to the other contributors from across threads and posts for their input.

Test Case #1
Input:

Code: Select all

9
1 2 2 2 4 5 7 7 7
1
2

AC Output:

Code: Select all

1 4

Test Case #2
Input:

Code: Select all

8
1 1 1 4 5 7 7 7
1
1 

AC Output:

Code: Select all

X 4

Test Case #3
Input:

Code: Select all

7
1 1 1 4 7 7 7
1
7

AC Output:

Code: Select all

4 X

Test Case #4
Input:

Code: Select all

7
1 1 4 5 7 7 8
1
7

AC Output:

Code: Select all

5 8

Test Case #5
Note that the judge's input does not test this case but I'm throwing it in there just for completeness.
Input:

Code: Select all

7
1 1 1 1 1 1 1
1
1

AC Output:

Code: Select all

X X

[sampad74]

I am getting WA.Please,help.Here is my code.Thanks in advance.

Code: Select all

got ac

[brianfry713]

There will be only one set of input for this problem. Don't try to read N more than once.

[sampad74]

I have changed that,but i am getting WA.Please,help me to find any bug..Thanks in advance.

Code: Select all

got ac

[brianfry713]

For input:

Code: Select all

1
2
1
1

On line 31 you're setting r1 = a1[-1];

[sampad74]

Thank you,brian...got ac.

[Marv.Ellis97]

package playc;

/**
*
* @author Harvey
*/
public class PlayC {



public static int main(String[] args)
{
using namespace std;
int main()
{
int(
//N(1<N<5000) Q(1<Q<2500)
long int shrt,tall,n=0,h,low,high,q,mid,num,a[50002],i,b[25001];
scanf("%ld", &num);
scanf("%ld", &a[n++]);
for(i=1;i<num;i++)
{
scanf("%ld", &h);
if(h != a[n-1])
a[n++]=h;
}
scanf("%ld", &q);
for(i=0;i<q;i++)
scanf("%ld", &b);
for(i=0;i<q;i++)
{
if((a[0]==a[n-1]) && (b==a[0]) && (b==a[n-1]))
{
printf("X X\n");
continue;
}
if(b>a[n-1])
{
printf("%ld X\n",a[n-1]);
continue;
}
if(b==a[n-1])
{
printf("%ld X\n",a[n-2]);
continue;
}
if(b<a[0])
{
printf("X %ld\n",a[0]);
continue;
}

if(b==a[0])
{
printf("X %ld\n",a[1]);
continue;
}
low=0;
high=n-1;
tall=shrt=0;

//Height pairing
while(low<high)
{
mid=(low+high)/2;
if(a[mid]==b)
{
shrt=mid-1;
tall=mid+1;
break;
}

else if(a[mid]<b)
low=mid+1;
else
high=mid-1;
}
if(tall==0)
printf("%ld %ld\n",a[low-1],a[high]);
else
printf("%ld %ld\n",a[shrt],a[tall]);
}
return 0;
}
}
}

How do I run the code? I'm clueless on how to do this project, PlayBoy chimp.
http://uva.onlinejudge.org/external/106/10611.html <---- Is the problem I have to create a code for.

[Marv.Ellis97]

package playc;

/**
*
* @author Harvey
*/
public class PlayC {



public static int main(String[] args)
{
using namespace std;
int main()
{
int(
//N(1<N<5000) Q(1<Q<2500)
long int shrt,tall,n=0,h,low,high,q,mid,num,a[50002],i,b[25001];
scanf("%ld", &num);
scanf("%ld", &a[n++]);
for(i=1;i<num;i++)
{
scanf("%ld", &h);
if(h != a[n-1])
a[n++]=h;
}
scanf("%ld", &q);
for(i=0;i<q;i++)
scanf("%ld", &b);
for(i=0;i<q;i++)
{
if((a[0]==a[n-1]) && (b==a[0]) && (b==a[n-1]))
{
printf("X X\n");
continue;
}
if(b>a[n-1])
{
printf("%ld X\n",a[n-1]);
continue;
}
if(b==a[n-1])
{
printf("%ld X\n",a[n-2]);
continue;
}
if(b<a[0])
{
printf("X %ld\n",a[0]);
continue;
}

if(b==a[0])
{
printf("X %ld\n",a[1]);
continue;
}
low=0;
high=n-1;
tall=shrt=0;

//Height pairing
while(low<high)
{
mid=(low+high)/2;
if(a[mid]==b)
{
shrt=mid-1;
tall=mid+1;
break;
}

else if(a[mid]<b)
low=mid+1;
else
high=mid-1;
}
if(tall==0)
printf("%ld %ld\n",a[low-1],a[high]);
else
printf("%ld %ld\n",a[shrt],a[tall]);
}
return 0;
}
}
}

How do I run the code? I'm clueless on how to do this project, PlayBoy chimp.
http://uva.onlinejudge.org/external/106/10611.html <---- Is the problem I have to create a code for.

[brianfry713]

Next time post in the existing thread.
http://uva.onlinejudge.org/index.php?op ... &Itemid=30
Don't use a package.
Use class Main.

[richatibrewal]

Hiii, i m getting rum time error in the following code:

Plz tell the solution

#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
int main()
{
int n,q,i,j,a[60000],k,m=INT_MIN;
scanf("%d",&n);
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
{
scanf("%d",&k);
a[k]++;
if(m<k)
m=k;
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&k);
for(j=k-1;j>=0;j--)
{
if(a[j]!=0)
{
printf("%d ",j);
break;
}
}
if(j==-1)
printf("X ");
if(k>=m)
printf("X\n");
else
for(j=k+1;j<=m;j++)
{
if(a[j]!=0)
{
printf("%d\n",j);
break;
}
}
}
return 0;
}

[lighted]

Use code tags.

In the next line you would have N integers (in the range 1 to 2^31-1)

According to problem description k is in the range [1..2^31]. So a[k]++ will give RE. Read this thread for better solutions.