/**************************************************************************************************************
* Md. Abdulla Al Mamun (Nayon)
* ID: 1306001
* Session: 2013-2014
* Department of Computer Science and Engineering
* Begum Rokeya University, Rangpur (BRUR)
***************************************************************************************************************/
#include <stdio.h>
#define MAX 10000
#define swap(typeName, a, b) {typeName _tmp = a; a = b; b = _tmp;}
#define max(a, b) ((a) > (b)) ? (a):(b)
#define min(a, b) ((a) < (b)) ? (a):(b)
int maxHeap[MAX];
int minHeap[MAX];
int maxHeapSize, minHeapSize;
void maxHeapInsert(int n)//push operation
{
maxHeap[++maxHeapSize] = n;
int tmp = maxHeapSize;
while(tmp > 1){
int parent = tmp/2;
if(maxHeap[parent] < maxHeap[tmp]){
swap(int, maxHeap[parent], maxHeap[tmp]);
tmp = parent;
}
else
break;
}
}
void minHeapInsert(int n)//push operation
{
minHeap[++minHeapSize] = n;
int tmp = minHeapSize;
while(tmp > 1){
int parent = tmp/2;
if(minHeap[parent] > minHeap[tmp]){
swap(int, minHeap[parent], minHeap[tmp]);
tmp = parent;
}
else
break;
}
}
int maxHeapRemove()//pop operation
{
int tmp = maxHeap[1];
maxHeap[1] = maxHeap[maxHeapSize];
maxHeapSize--;
int parent = 1;
while(2*parent <= maxHeapSize){
int lftChild = parent * 2;
int ritChild = lftChild + 1;
int ch = lftChild;
if(ritChild <= maxHeapSize){
if(maxHeap[lftChild] < maxHeap[ritChild])
ch = ritChild;
}
if(maxHeap[parent] < maxHeap[ch]){
swap(int, maxHeap[parent], maxHeap[ch]);
parent = ch;
}
else
break;
}
return tmp;
}
int minHeapRemove()//pop operation
{
int tmp = minHeap[1];
minHeap[1] = minHeap[minHeapSize];
minHeapSize--;
int parent = 1;
while(2*parent <= minHeapSize){
int lftChild = parent *2;
int ritChild = lftChild+1;
int ch = lftChild;
if(ritChild <= minHeapSize){
if(minHeap[lftChild] > minHeap[ritChild])
ch = ritChild;
}
if(minHeap[parent] > minHeap[ch]){
swap(int, minHeap[parent], minHeap[ch]);
parent = ch;
}
else
break;
}
return tmp;
}
int main(int argc, char* argv[])
{
int n, a, b, successInp;
successInp
= scanf("%d", &a
); if(successInp == EOF)
return 0;
successInp
= scanf("%d", &b
); if(successInp == EOF)
return 0;
maxHeap[1] = min(a, b);
minHeap[1] = max(a, b);
maxHeapSize = minHeapSize = 1;
while(scanf("%d", &n
) != EOF
){ if(n < maxHeap[1])
maxHeapInsert(n);
else
minHeapInsert(n);
//balance heaps
while(maxHeapSize - minHeapSize >= 2){
int tmp = maxHeapRemove();
minHeapInsert(tmp);
}
while(minHeapSize - maxHeapSize >= 2){
int tmp = minHeapRemove();
maxHeapInsert(tmp);
}
//calculate median
if((maxHeapSize+minHeapSize)%2==1){
if(maxHeapSize > minHeapSize)
printf("%.1lf\n", 1.0*maxHeap
[1]); else
printf("%.1lf\n", 1.0*minHeap
[1]); }
else{
printf("%.1lf\n", (maxHeap
[1]+minHeap
[1])/2.0); }
}
return 0;
}
LyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqCiAgICogIE1kLiBBYmR1bGxhIEFsIE1hbXVuIChOYXlvbikKICAgKiAgSUQ6IDEzMDYwMDEKICAgKiAgU2Vzc2lvbjogMjAxMy0yMDE0CiAgICogIERlcGFydG1lbnQgb2YgQ29tcHV0ZXIgU2NpZW5jZSBhbmQgRW5naW5lZXJpbmcKICAgKiAgQmVndW0gUm9rZXlhIFVuaXZlcnNpdHksIFJhbmdwdXIgKEJSVVIpCioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIE1BWCAxMDAwMAojZGVmaW5lIHN3YXAodHlwZU5hbWUsIGEsIGIpIHt0eXBlTmFtZSBfdG1wID0gYTsgYSA9IGI7IGIgPSBfdG1wO30KI2RlZmluZSBtYXgoYSwgYikgKChhKSA+IChiKSkgPyAoYSk6KGIpCiNkZWZpbmUgbWluKGEsIGIpICgoYSkgPCAoYikpID8gKGEpOihiKQoKaW50IG1heEhlYXBbTUFYXTsKaW50IG1pbkhlYXBbTUFYXTsKaW50IG1heEhlYXBTaXplLCBtaW5IZWFwU2l6ZTsKCnZvaWQgbWF4SGVhcEluc2VydChpbnQgbikvL3B1c2ggb3BlcmF0aW9uCnsKCW1heEhlYXBbKyttYXhIZWFwU2l6ZV0gPSBuOwoJaW50IHRtcCA9IG1heEhlYXBTaXplOwoJd2hpbGUodG1wID4gMSl7CgkJaW50IHBhcmVudCA9IHRtcC8yOwoJCWlmKG1heEhlYXBbcGFyZW50XSA8IG1heEhlYXBbdG1wXSl7CgkJCXN3YXAoaW50LCBtYXhIZWFwW3BhcmVudF0sIG1heEhlYXBbdG1wXSk7CgkJCXRtcCA9IHBhcmVudDsKCQl9CgkJZWxzZQoJCQlicmVhazsKCX0KfQoKdm9pZCBtaW5IZWFwSW5zZXJ0KGludCBuKS8vcHVzaCBvcGVyYXRpb24KewoJbWluSGVhcFsrK21pbkhlYXBTaXplXSA9IG47CglpbnQgdG1wID0gbWluSGVhcFNpemU7Cgl3aGlsZSh0bXAgPiAxKXsKCQlpbnQgcGFyZW50ID0gdG1wLzI7CgkJaWYobWluSGVhcFtwYXJlbnRdID4gbWluSGVhcFt0bXBdKXsKCQkJc3dhcChpbnQsIG1pbkhlYXBbcGFyZW50XSwgbWluSGVhcFt0bXBdKTsKCQkJdG1wID0gcGFyZW50OwoJCX0KCQllbHNlCgkJCWJyZWFrOwoJfQp9CgppbnQgbWF4SGVhcFJlbW92ZSgpLy9wb3Agb3BlcmF0aW9uCnsKCWludCB0bXAgPSBtYXhIZWFwWzFdOwoJbWF4SGVhcFsxXSA9IG1heEhlYXBbbWF4SGVhcFNpemVdOwoJbWF4SGVhcFNpemUtLTsKCWludCBwYXJlbnQgPSAxOwoJd2hpbGUoMipwYXJlbnQgPD0gbWF4SGVhcFNpemUpewoJCWludCBsZnRDaGlsZCA9IHBhcmVudCAqIDI7CgkJaW50IHJpdENoaWxkID0gbGZ0Q2hpbGQgKyAxOwoJCWludCBjaCA9IGxmdENoaWxkOwoJCWlmKHJpdENoaWxkIDw9IG1heEhlYXBTaXplKXsKCQkJaWYobWF4SGVhcFtsZnRDaGlsZF0gPCBtYXhIZWFwW3JpdENoaWxkXSkKCQkJCWNoID0gcml0Q2hpbGQ7CgkJfQoJCWlmKG1heEhlYXBbcGFyZW50XSA8IG1heEhlYXBbY2hdKXsKCQkJc3dhcChpbnQsIG1heEhlYXBbcGFyZW50XSwgbWF4SGVhcFtjaF0pOwoJCQlwYXJlbnQgPSBjaDsKCQl9CgkJZWxzZQoJCQlicmVhazsKCX0KCXJldHVybiB0bXA7Cn0KCmludCBtaW5IZWFwUmVtb3ZlKCkvL3BvcCBvcGVyYXRpb24KewoJaW50IHRtcCA9IG1pbkhlYXBbMV07CgltaW5IZWFwWzFdID0gbWluSGVhcFttaW5IZWFwU2l6ZV07CgltaW5IZWFwU2l6ZS0tOwoJaW50IHBhcmVudCA9IDE7Cgl3aGlsZSgyKnBhcmVudCA8PSBtaW5IZWFwU2l6ZSl7CgkJaW50IGxmdENoaWxkID0gcGFyZW50ICoyOwoJCWludCByaXRDaGlsZCA9IGxmdENoaWxkKzE7CgkJaW50IGNoID0gbGZ0Q2hpbGQ7CgkJaWYocml0Q2hpbGQgPD0gbWluSGVhcFNpemUpewoJCQlpZihtaW5IZWFwW2xmdENoaWxkXSA+IG1pbkhlYXBbcml0Q2hpbGRdKQoJCQkJY2ggPSByaXRDaGlsZDsKCQl9CgkJaWYobWluSGVhcFtwYXJlbnRdID4gbWluSGVhcFtjaF0pewoJCQlzd2FwKGludCwgbWluSGVhcFtwYXJlbnRdLCBtaW5IZWFwW2NoXSk7CgkJCXBhcmVudCA9IGNoOwoJCX0KCQllbHNlCgkJCWJyZWFrOwoJfQoJcmV0dXJuIHRtcDsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqIGFyZ3ZbXSkKewoJaW50IG4sIGEsIGIsIHN1Y2Nlc3NJbnA7CgoJc3VjY2Vzc0lucCA9IHNjYW5mKCIlZCIsICZhKTsKCWlmKHN1Y2Nlc3NJbnAgPT0gRU9GKQoJCXJldHVybiAwOwoJcHJpbnRmKCIlZFxuIiwgYSk7CgoJc3VjY2Vzc0lucCA9IHNjYW5mKCIlZCIsICZiKTsKCWlmKHN1Y2Nlc3NJbnAgPT0gRU9GKQoJCXJldHVybiAwOwoJcHJpbnRmKCIlLjFsZlxuIiwgKGErYikvMi4wKTsKCgltYXhIZWFwWzFdID0gbWluKGEsIGIpOwoJbWluSGVhcFsxXSA9IG1heChhLCBiKTsKCW1heEhlYXBTaXplID0gbWluSGVhcFNpemUgPSAxOwoKCXdoaWxlKHNjYW5mKCIlZCIsICZuKSAhPSBFT0YpewoJCWlmKG4gPCBtYXhIZWFwWzFdKQoJCQltYXhIZWFwSW5zZXJ0KG4pOwoJCWVsc2UKCQkJbWluSGVhcEluc2VydChuKTsKCgkJLy9iYWxhbmNlIGhlYXBzCgkJd2hpbGUobWF4SGVhcFNpemUgLSBtaW5IZWFwU2l6ZSA+PSAyKXsKCQkJaW50IHRtcCA9IG1heEhlYXBSZW1vdmUoKTsKCQkJbWluSGVhcEluc2VydCh0bXApOwoJCX0KCQl3aGlsZShtaW5IZWFwU2l6ZSAtIG1heEhlYXBTaXplID49IDIpewoJCQlpbnQgdG1wID0gbWluSGVhcFJlbW92ZSgpOwoJCQltYXhIZWFwSW5zZXJ0KHRtcCk7CgkJfQoJCQoJCS8vY2FsY3VsYXRlIG1lZGlhbgoJCWlmKChtYXhIZWFwU2l6ZSttaW5IZWFwU2l6ZSklMj09MSl7CgkJCWlmKG1heEhlYXBTaXplID4gbWluSGVhcFNpemUpCgkJCQlwcmludGYoIiUuMWxmXG4iLCAxLjAqbWF4SGVhcFsxXSk7CgkJCWVsc2UKCQkJCXByaW50ZigiJS4xbGZcbiIsIDEuMCptaW5IZWFwWzFdKTsKCQl9CgkJZWxzZXsKCQkJcHJpbnRmKCIlLjFsZlxuIiwgKG1heEhlYXBbMV0rbWluSGVhcFsxXSkvMi4wKTsKCQl9Cgl9CglyZXR1cm4gMDsKfQo=