## 10611 - The Playboy Chimp

Moderator: Board moderators

### 10611 - The Playboy Chimp

hi ,
i am getting WA in this Prob . According to myself the problem statement is some thing like this :

[cpp]YOU R GIVEN A LIST OF NON DECREASING SORTED NUMBER . AND AS AN INPUT A NUMBER WILL BE GIVEN , U HAVE TO FIND OUT THE LARGEST NUMBER SMALLER THAN THE SPECIFIED NUMBER AND THE SMALLEST NUMBER LARGEST THAN THAT NUMBER (SPECIFIED NUMBER).[/cpp]
i used Binary Search to Solve This Prob . Here is my code , can some one plizzzzzzzzzzz check the code for me , and tell me what is wrong with it .
more over i considered the input :

4
1 2 3 4
5
5 0 3 1 4

and my output is :

4 X
X 1
2 4
X 2
3 X

i guess this r the cases which i should be considering ..

[cpp]
**********************CODE REMOVED************************
[/cpp]
Last edited by Riyad on Sat Jan 31, 2004 4:56 pm, edited 1 time in total.
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

U should be more carefull while reading description. they said that height are in non decreasing order. how u assumed that two adjacent height will not same

consider this INPUT:

8
1 1 1 4 5 7 7 7
8
4 6 8 10 12 1 7 5

and u will find your fault.

AFTERWALL, PLEASE REMOVE CODE, it's almost done
prince56k
New poster

Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm

### THANX

HI PRINCEK ,

THANX FOR U R IO . I REALIZED MY STUPID MISTAKE . I GOT IT FIXED . AND GOT AC .

NICE HINT
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

### 10611: WA

prince56k My program gives the following output for your input
1 5
5 7
7 X
7 X
7 X
X 1
5 7
4 7

Are my output correct? Pls give me some input. I have got WA.
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am

Two of last three answers are wrong...
Correct ones should be:
...
X 4
5 X
4 7

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### Thank U.

Guru Dominik Michniewski,
Thank u very much for help me. I am a novice programmer. My program is now AC ( ) with a runtime 0:01.904 . How can I improve the time . I am in 3rd position in this prob from back. Would u help me to improve my solution?
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am

I don't know your method, but I use bsearch() [modified] to solve this question.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### 10611 (Should rejudge)

There was a bug in my solution but I get AC . After getting AC verify with the following input;

Input:
2
49997 49997
1
49997

With this input where was no output...

But the output should be 'X X'

So I think there is no much critical input. But the input should be strong enough to judge...
Rajib
New poster

Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

I have solved this problem using my binary search function in 0.191s.Can some one tell me how to modify the built in bsearch function to get the index of the array(sample code) of the key or near the key.
Regards
Faizur
Faizur
New poster

Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

### 10611...Runtime Error (SIGSEGV)

I can't understand Why I get Runtime Error (SIGSEGV)
Usually I fix this error with the size of the array, but in this case it doesn't work
I tried to use "Divide and Conquer" algorithm but I am a beginner so my algorithm is almost sure very ugly and ineficient
Here is my code:
Code: Select all
`#include <stdio.h>search(int ind,int l[],int c,int last){    int j;    if(ind<=0 || ind >=last) {        printf("X X\n");        return 0;    }        if(c>l[ind] && c>l[ind+1]) search(ind+(last-ind)/2,&l[0],c,last);    if(c<l[ind] && c<l[ind-1]) search(ind-ind/2,&l[0],c,last);    if(c==l[ind]){         for (j=ind;j>1;j--){            if(l[j]!=l[j-1]){                printf("%d ",l[j-1]);                break;                if(j==2 && l[j]==l[j-1])                  printf("X ");            }        }        for (j=ind;j<last;j++){            if(l[j]!=l[j+1]){                printf("%d\n",l[j+1]);                break;                if(j==last-1 && l[j]==l[j+1])                  printf("X\n");            }        }        return 0;    }    if(c>l[ind] && c<l[ind+1]) {        printf("%d %d\n",l[ind],l[ind+1]);        return 0;    }}    int main(){  int n1,n2,l[50004],c[25004],i,j,k;  scanf("%d",&n1);  for (i=1;i<=n1;i++)    scanf("%d",&l[i]);  scanf("%d",&n2);  for (i=1;i<=n2;i++)    scanf("%d",&c[i]);   for (i=1;i<=n2;i++){     if(c[i]<l[1]){          printf("X %d\n",l[1]);          continue;     }         if(c[i]>l[n1]){          printf("%d X\n",l[n1]);          continue;     }     k=c[i];     search(n1/2,&l[0],k,n1);  }  return 0;}`

I think I could make in a easier way this problem if I use the function built-in bsearch() but I don't know how to use it... does anyone knows?
thanks for reading and sorry for my ugly english
good luck! BYE!
midra
Experienced poster

Posts: 119
Joined: Fri Feb 13, 2004 7:20 am

### 10611 how WA......

i don't know why judge give me WA
plz any one help me....

Code: Select all
`#include<stdio.h>long cham[50001];int BinSearch(long x,long n){ long low=0,high=n-1,mid,max=0,min=0; while(low<=high)   {    mid=(low+high)/2;    if(x<cham[mid])max=cham[mid],high=mid-1;    else if(x>cham[mid])min=cham[mid],low=mid+1;    else      {       if(mid!=n-1)max=cham[mid+1];       if(mid!=0)min=cham[mid-1];       break;      }   }  if(max==0)printf("%ld X\n",min);  else if(min==0)printf("X %ld\n",max);  else printf("%ld %ld\n",min,max);return 0;}void main(){ long n,q,luchu,i; scanf("%ld",&n); for(i=0;i<n;i++)    scanf("%ld",&cham[i]); scanf("%ld",&q); while(q--)   {    scanf("%ld",&luchu);    BinSearch(luchu,n);   }}`
Hi I am Masud...
Masud
New poster

Posts: 5
Joined: Sat May 06, 2006 1:12 am

hi masud
try this ----

1
1
1
1

and

3
1 3 3
2
1
3

Also add this line in ur input part
Code: Select all
`while(scanf("%ld",&n)==1){    //add this line                for(i=0;i<n;i++)          scanf("%ld",&cham[i]);      scanf("%ld",&q);   while(q--){           scanf("%ld",&luchu);           BinSearch(luchu,n);   }} `

hope this will help u.
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

can any one tell me what will be the output for the following inputs

Code: Select all
`111141 5 5 715`

Sanjana
kolpobilashi
Learning poster

Posts: 54
Joined: Mon Jan 02, 2006 3:06 am

Code: Select all
`the tallest one shorter than he and the shortest one taller than he.`

HOPE THIS WILL HELP.
bye
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10611

Is the description is not strong enough?
Here's my code. I havent inserted the duplicate inputs.

// The PlayBoy Chimp (10611)
// 20.09.06

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

long arr[50009];

int comp(const void *a,const void *b);

void main()
{
long key,index,i,data,n1;
long *p;
long n,height,node_no;
bool flag;
scanf("%ld",&n);
n1=n;
node_no=0;
while(n--)
{
scanf("%ld",&data);
flag=false;
if(node_no==0) //no duplicate will be in stored array
{
arr[node_no]=data;
node_no++;
flag=true;
}
else
{
if(arr[node_no-1]==data)
flag=true;
}
if(flag==false)
{
arr[node_no]=data;
node_no++;
}
}
n=n1;

scanf("%ld",&height);

i=0; // searching starts
while(height)
{
height--;
scanf("%ld",&key);
p=(long *)bsearch(&key,arr,n,sizeof(long),comp);

if(p)
index=p-arr;
else
index=-1;

if(arr[index]==key) //if height_i found
{
if((index-1)<0)
printf("%c ",'X');
else
{
printf("%ld ",arr[index-1]);
}

}
printf("%ld ",arr[node_no-1]);
else if(arr[index]>key && index>0)
printf("%ld ",arr[index-1]);
else if(arr[index]>key && index==0) //if less than 1st element
printf("X ");

if(arr[index]==key)
{
if(index+1<node_no)
printf("%ld\n",arr[index+1]);
else
printf("X\n");
}
else if(index==-1)
printf("X\n");
else if(arr[index]>key)
printf("%ld\n",arr[index]);
i++;
}
}

int comp(const void *a,const void *b)
{
long *A=(long *)a; //key
long *B=(long *)b; //current

if(*A<*B && (B-arr==0 || *A>*(B-1)))
return 0;
return *A-*B;
}
23423LA
New poster

Posts: 1
Joined: Sun Aug 20, 2006 8:14 am