UVA – 10611 – The Playboy Chimp

  • Problem StatementUVA – 10611 – The Playboy Chimp
  • Type : Binary search.
  • Solution : as the normal binary search will contain so many special cases that will cause a headache it’s more usable to use a balanced binary tree DS to store the values then use the iterators to bracket the key. (this solution was suggested to me by a friend of mine MohammadKotb. and the whole problem was suggested to be solved by YoussefSalama.  )
  • Gochas : if you used binary search, the input set may contain duplicate keys so make sure to handle this.
#include <iostream>
#include <stdio.h>
#include <set>
using namespace std;
typedef set<int>::iterator It;
int main() {
	int N, n, Q, q;
	set<int> s;
	scanf("%d", &N);
	while (N-- && (scanf("%d", &n)==1)) s.insert(n);
	scanf("%d", &Q);
	while (Q-- && (scanf("%d", &q)==1)) {
		It a = s.begin(),f = s.find(q), i= s.upper_bound(q), e = s.end(), b = --e;
		if (q < *a)			printf("X %d\n", *(++a));
		else if (*b < q)	printf("%d X\n", *b);
		else if (*f == *a)	printf("X %d\n", *(++a));
		else if (*f == *b)	printf("%d X\n", *b);
		else{
			int u = *(i--);
			int l = *(i)==q ? *(--i) : *(i);
			printf("%d %d\n", l, u);
		}
	}
	return 0;
}
Advertisements

One thought on “UVA – 10611 – The Playboy Chimp

  1. this is a lot better than my binary search solution, really nice .. 😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: