Page 1 of 3

10611 - The Playboy Chimp

Posted: Sat Jan 31, 2004 8:44 am
by 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

Posted: Sat Jan 31, 2004 11:03 am
by 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 :wink:

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

AFTERWALL, PLEASE REMOVE CODE, it's almost done :lol:

THANX

Posted: Sat Jan 31, 2004 5:04 pm
by Riyad
HI PRINCEK ,

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

NICE HINT :wink:
Riyad

10611: WA

Posted: Thu Feb 12, 2004 7:59 am
by 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.

Posted: Thu Feb 12, 2004 9:03 am
by Dominik Michniewski
Two of last three answers are wrong...
Correct ones should be:
...
X 4
5 X
4 7

Best regards
DM

Thank U.

Posted: Thu Feb 12, 2004 10:20 am
by Jewel of DIU
Guru Dominik Michniewski,
Thank u very much for help me. I am a novice programmer. My program is now AC ( :D ) 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?

Posted: Thu Feb 12, 2004 11:04 am
by Dominik Michniewski
I don't know your method, but I use bsearch() [modified] to solve this question.

Best regards
DM

10611 (Should rejudge)

Posted: Mon Jun 21, 2004 9:09 am
by Rajib
There was a bug in my solution but I get AC :lol: . After getting AC verify with the following input;

Input:
2
49997 49997
1
49997
With this input where was no output... :o

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

Posted: Mon Jul 19, 2004 8:48 am
by 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

10611...Runtime Error (SIGSEGV)

Posted: Thu Jan 20, 2005 4:28 am
by 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!

10611 how WA......

Posted: Mon May 08, 2006 7:49 pm
by 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);
	}
}

Posted: Tue May 09, 2006 9:05 pm
by 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.

Posted: Sat Aug 19, 2006 6:18 pm
by kolpobilashi
can any one tell me what will be the output for the following inputs :roll:

Code: Select all

1
1
1
1

4
1 5 5 7
1
5
thanx in advance

Posted: Sat Aug 19, 2006 8:17 pm
by 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

10611

Posted: Wed Sep 20, 2006 12:24 pm
by 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;
}