10611 - The Playboy Chimp

[Riyad]

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]
Riyad

[prince56k]

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

[Riyad]

HI PRINCEK ,

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

NICE HINT
Riyad

[Jewel of DIU]

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.

[Dominik Michniewski]

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

Best regards
DM

[Jewel of DIU]

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?

[Dominik Michniewski]

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

Best regards
DM

[Rajib]

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

[Faizur]

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

[midra]

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!

[Masud]

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);
	}
}

[asif_rahman0]

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.

[kolpobilashi]

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

Code: Select all

1
1
1
1

4
1 5 5 7
1
5

thanx in advance

[asif_rahman0]

HI Sanjana, please read the problem statement carefully.

Code: Select all

the tallest one shorter than he and the shortest one taller than he.

HOPE THIS WILL HELP.
bye

[23423LA]

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]);
}

}
else if(index==-1) //not found in max index
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;
}