10611 - The Playboy Chimp

[arsalan_mousavian]

try this input :

Code: Select all

5 1 
5 5 5 5 5 
5

the output should be :

Code: Select all

X X 

Hope it Helps . . .

[nymo]

I think, arsalan_mousavian wished to say:

Code: Select all

5
5 5 5 5 5
1
5

... anyway, I am getting P.E. on this problem, What is the expected format?
I tried:

Code: Select all

		if(!lower)
			printf("%c ", 'X');
		else
			printf("%ld ", lower);
		if(!higher)
			printf("%c", 'X');
		else
			printf("%ld", higher);

... and I 've tried both with printing newline after the last case and without it.

[helloneo]

... anyway, I am getting P.E. on this problem, What is the expected format?

What I did was pretty much like this..

Code: Select all

	while (qn--) {

		if(!lower)
			printf("%c ", 'X');
		else
			printf("%ld ", lower);
		if(!higher)
			printf("%c", 'X');
		else
			printf("%ld", higher);
		printf("\n");
	}

[nymo]

Thanks helloneo, I get ACC. As far as I recall, I pretty much did the same thing and got P.E. and then I changed to different formats... Don't know what is changed... anyway, ACC now and thanks.

[turcse143]

Sanjana look it.
this is the sample input:

Code: Select all

4
1 4 5 7
4
4 6 8 10

1
1
1
1

3
1 3 3
2
1
3 

5
5 5 5 5 5
1
5

output:
1 5
5 7
7 X
7 X
X X
X 3
1 X
X X

hope it helps.

[kbr_iut]

code deleted after AC

[Jan]

Why 25003? Read the description again.

[kbr_iut]

sorry ,,,,,for array size..
but when i increased array size i got TLE...pliz tell me,is my proceed is right?
I used binary search method to find where start==end...then i evaluate the greatest but smaller than the number and smallest and the greater than the number.
i took consider when there is repeated number.
pliz tell me......

[Jan]

'Binary search' is enough for solving this problem. However, check the boundary cases carefully.

[kbr_iut]

thanx via.Now AC...

[fido19]

hi guys i was wondering if this problem is solvable in python language if anyone knows this could they post the code as my code doesent work and i have no idea how to solve it please someone out there who knows it can help me

[vahid sanei]

i solved this problem with cin and cout in 0.430 sec
and with scanf and printf in 0.060 sec
how can i reduce time of my algorithm? ( i use Binary search for this pb)
thanks in advance

[yeasin_acm_solver]

plz some one help me, a im getting wrong ans ,here is my code :

Code: Select all

/*
	Author : Muhammad Yeasin
	University of Science & Technology Chittagong (USTC)
	CSE- 11th Batch
	Bangladesh	Date:	12:11 AM 10/23/2010		uva id : 10611 The Playboy Chimp
	E-mail: gigabyte_yeasin@yahoo.com
*/
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define pb push_back
#define file { freopen("input.txt","r",stdin);}

using namespace std;

int binary_search_modify(long int *data,int lb, int ub, int item){
	int beg=0, end=ub;
	int mid=(beg+end)/2;
	while((beg<=end)&&(item!=data[mid])){
		if(item<data[mid])
			end=mid-1;
		else
			beg=mid+1;
	mid=(beg+end)/2;
	if(beg==end)
		break;
	}
if(item>=data[mid])
	return mid;
else if(item<data[mid])
	return mid-1;;
return 0;
}


int main()
{
	long int a[50001]={0};
	
	long int n,it,pos;
	//file
	while(scanf("%ld",&n)==1){
		long int i;
		it=0;
		for(i=0;i<n;i++){
			scanf("%ld",&a[i]);
		}
		long int j,m;
		scanf("%ld",&m);
		for(j=0;j<m;j++){
			scanf("%ld",&it);
			pos=0;
			if(it>a[i-1])
				printf("%ld X\n",a[i-1]);
			else if(it==a[0])
				printf("X %ld\n",a[1]);
			else if(it==a[i-1])
				printf("%ld X\n",a[i-2]);
			else{
			pos=binary_search_modify(a,0,n-1,it);
			if(it==a[pos])
				printf("%ld %ld\n",a[pos-1],a[pos+1]);
			else if((it!=a[pos])&&(it<a[i-1]))
				printf("%ld %ld\n",a[pos],a[pos+1]);
			}
		}
	}
return 0;
}

[sohel]

Use the search option located at the top right corner to find existing discussions.
Don't create a new thread for a problem that already exists! Make your post in an existing thread.

[shaon_cse_cu08]

I have modified my binary search algorithm...that is even if it can't find the data it always return nearest location.... I got it AC in 0.036 s .... Plz be careful using this code...Coz the nearest location can be either smaller or the greater one....

Code: Select all

long b_src(long a[],long n,long x)		//a[] is the array...it can be made global...	
{								//n is the total elements....x is what i m looking for..		
	int ini,end,mid;

	ini=0;
	end=n-1;

	while(ini<=end)
	{
		mid=(ini+end)/2;

		if(x==a[mid])
			return (mid);				
		
		else if(x>a[mid])
			ini=mid+1;
		
		else
			end=mid-1;
	}

return mid;                                     //it always returns something (In case of binary search 'return 0')
}