test-36 solutions hacker rank
1)
#include <stdio.h>
#include <math.h>
int n;
double ans = -1e100;
double mx[3000010],mn[3000010];
int main()
{
int i;
double v;
mx[0] = mn[0] = cos(0);
mx[1] = mn[1] = cos(0.5);
for(i=2;i<=3000000;i++)
{
v = cos(i/2.0);
mx[i] = v > mx[i-2] ? v : mx[i-2];
mn[i] = v < mn[i-2] ? v : mn[i-2];
}
scanf("%d",&n);
for(i=1;i<=n-2;i++)
{
v = 2*sin((n-i)/2.0);
v *= v > 0 ? mx[n-i-2] : mn[n-i-2];
v += sin(i);
ans = ans > v ? ans : v;
}
printf("%.9f",ans);
return 0;
}
2)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long long merge(int *a, int left, int division, int right)
{
int *a1 = malloc(sizeof(int) * (division - left));
int *a2 = malloc(sizeof(int) * (right - division + 1));
int i, j, k;
int n = right - left + 1;
long long c = 0;
for (i = left; i < division; i++)
a1[i - left] = a[i];
for (i = division; i < right + 1; i++)
a2[i - division] = a[i];
for (k = left, i = 0, j = 0; k <= right && i < division - left && j < right + 1 - division; k++) {
if (a1[i] <= a2[j]) {
a[k] = a1[i];
i++;
} else {
c += division - left - i;
a[k] = a2[j];
j++;
}
}
while (i < division - left) {
a[k++] = a1[i++];
}
while (j < right + 1 - division)
a[k++] = a2[j++];
free(a1);
free(a2);
//printf("ret %d\n", c);
return c;
}
long long do_merge_sort(int *a, int left, int right)
{
int p;
long long c = 0;
if (right <= left)
return 0;
p = (left + right) / 2;
c += do_merge_sort(a, left, p);
c += do_merge_sort(a, p + 1, right);
c += merge(a, left, p + 1, right);
return c;
}
long long solve(int *a, int n)
{
return do_merge_sort(a, 0, n - 1);
}
int main()
{
int n;
int i, j;
scanf("%d", &n);
while (n-- > 0) {
int n;
long long c;
int *a;
int i;
scanf("%d", &n);
a = malloc(sizeof(int) * n);
for (i = 0; i < n; i++)
scanf("%d", a + i);
c = solve(a, n);
printf("%lld\n", c);
free(a);
}
return 0;
}
3)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#define HEAP_SIZE 100100
typedef struct {
int array[HEAP_SIZE];
int count;
} Heap;
Heap *heap_new() {
Heap *heap = (Heap *)malloc(sizeof(Heap));
heap->count = 0;
return heap;
}
void minheap_bubble_up(Heap *heap, int index) {
int elt = heap->array[index];
int i = index;
int p = (i-1)/2; // parent of i
while (i > 0 && elt < heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = elt;
}
void maxheap_bubble_up(Heap *heap, int index) {
int elt = heap->array[index];
int i = index;
int p = (i-1)/2; // parent of i
while (i > 0 && elt > heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = elt;
}
void minheap_bubble_down(Heap *heap, int index) {
int elt = heap->array[index];
int i = index;
while (1) {
int next = -1;
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break; // no children
if (heap->array[left] < elt) {
next = (right < heap->count && heap->array[right] < heap->array[left]) ? right : left;
} else if (right < heap->count && heap->array[right] < elt) {
next = right;
} else { // elt is no greater than both children, so stop.
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = elt;
}
void maxheap_bubble_down(Heap *heap, int index) {
int elt = heap->array[index];
int i = index;
while (1) {
int next = -1;
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break; // no children
if (heap->array[left] > elt) {
next = (right < heap->count && heap->array[right] > heap->array[left]) ? right : left;
} else if (right < heap->count && heap->array[right] > elt) {
next = right;
} else { // elt is no greater than both children, so stop.
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = elt;
}
void minheap_push(Heap *heap, int x) {
assert(heap->count < HEAP_SIZE);
heap->array[heap->count++] = x;
minheap_bubble_up(heap, heap->count-1);
}
void maxheap_push(Heap *heap, int x) {
assert(heap->count < HEAP_SIZE);
heap->array[heap->count++] = x;
maxheap_bubble_up(heap, heap->count-1);
}
int minheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int last = heap->array[--heap->count];
heap->array[0] = last;
minheap_bubble_down(heap, 0);
return result;
}
int maxheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int last = heap->array[--heap->count];
heap->array[0] = last;
maxheap_bubble_down(heap, 0);
return result;
}
// Could probably do better than O(n + log n) but I'm
// starting to think this is already overcomplicated.
void minheap_remove(Heap *heap, int x) {
for (int i = 0; i < heap->count; i++) {
if (heap->array[i] == x) {
int last = heap->array[--heap->count];
if (i == heap->count) return;
heap->array[i] = last;
int p = (i-1)/2;
if (last < heap->array[p]) minheap_bubble_up(heap, i);
else minheap_bubble_down(heap, i);
return;
}
}
printf("invalid call to minheap_remove\n");
assert(0);
}
void maxheap_remove(Heap *heap, int x) {
for (int i = 0; i < heap->count; i++) {
if (heap->array[i] == x) {
int last = heap->array[--heap->count];
if (i == heap->count) return;
heap->array[i] = last;
int p = (i-1)/2;
if (last > heap->array[p]) maxheap_bubble_up(heap, i);
else maxheap_bubble_down(heap, i);
return;
}
}
printf("invalid call to maxheap_remove\n");
assert(0);
}
void rebalance_heaps(Heap *maxheap, Heap *minheap) {
while (maxheap->count < minheap->count) {
maxheap_push(maxheap, minheap_pop(minheap));
}
while (minheap->count < maxheap->count - 1) {
minheap_push(minheap, maxheap_pop(maxheap));
}
}
int main(void) {
int n, d;
scanf("%d %d", &n, &d);
int count = 0, exp[n];
Heap *maxheap = heap_new();
Heap *minheap = heap_new();
for (int i = 0; i < n; i++) {
scanf("%d", &exp[i]);
// Remove expired elements if necessary.
if (i > d) {
int old = exp[i-d-1];
if (old <= maxheap->array[0]) {
maxheap_remove(maxheap, old);
} else {
minheap_remove(minheap, old);
}
rebalance_heaps(maxheap, minheap);
}
if (i >= d) {
// Compute the median.
int twice_median;
if (maxheap->count == minheap->count) {
twice_median = maxheap->array[0] + minheap->array[0];
} else {
twice_median = 2*maxheap->array[0];
}
if (exp[i] >= twice_median) count++;
}
// Add in the newest element.
if (maxheap->count == 0 || exp[i] < maxheap->array[0]) {
maxheap_push(maxheap, exp[i]);
} else {
minheap_push(minheap, exp[i]);
}
rebalance_heaps(maxheap, minheap);
}
printf("%d\n", count);
return 0;
}
Comments :
Post a Comment