10611 - The Playboy Chimp

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

Moderator: Board moderators

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10611 - The Playboy Chimp

Post by Riyad » Sat Jan 31, 2004 8:44 am

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

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » Sat Jan 31, 2004 11:03 am

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:

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

THANX

Post by Riyad » Sat Jan 31, 2004 5:04 pm

HI PRINCEK ,

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

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

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

10611: WA

Post by Jewel of DIU » Thu Feb 12, 2004 7:59 am

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!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Feb 12, 2004 9:03 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)

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Thank U.

Post by Jewel of DIU » Thu Feb 12, 2004 10:20 am

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?
Hate WA
Visit phpBB!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Feb 12, 2004 11:04 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)

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

10611 (Should rejudge)

Post by Rajib » Mon Jun 21, 2004 9:09 am

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:

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

Post by Faizur » Mon Jul 19, 2004 8:48 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

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10611...Runtime Error (SIGSEGV)

Post by midra » Thu Jan 20, 2005 4:28 am

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
New poster
Posts: 5
Joined: Sat May 06, 2006 1:12 am
Location: Bangladesh
Contact:

10611 how WA......

Post by Masud » Mon May 08, 2006 7:49 pm


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

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

Post by asif_rahman0 » Tue May 09, 2006 9:05 pm

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
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi » Sat Aug 19, 2006 6:18 pm

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
Sanjana

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

Post by asif_rahman0 » Sat Aug 19, 2006 8:17 pm

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
New poster
Posts: 1
Joined: Sun Aug 20, 2006 8:14 am
Location: Bangladesh

10611

Post by 23423LA » Wed Sep 20, 2006 12:24 pm

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

Post Reply

Return to “Volume 106 (10600-10699)”