path: root/šola/aps1/funkcije.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LD long double
LD inverz (int smer, LD y, void * ctxt, LD (* f)(LD, void *), LD a, LD b, LD epsilon) { // za strogo NARAŠČAJOČE funkcije je smer 1, za strogo PADAJOČE je smer -1. iščemo x za funkcijsko vrednost y na intervalu (a,b). ustrezen x je tak, da v epsilonski okolici dejanskega f^-1(y).
	if (smer == 1) {
		if (y > f(b, ctxt))
			return INFINITY;
		if (y < f(a, ctxt))
			return -INFINITY;
	} else {
		if (y > f(a, ctxt))
			return -INFINITY;
		if (y < f(b, ctxt))
			return INFINITY;
	}
	LD x = (a+b)/2;
	if (b-a < epsilon)
		return x;
	LD v = f(x, ctxt);
	if (y > v) {
		if (smer == 1)
			return inverz(smer, y, ctxt, f, x, b, epsilon);
		return inverz(smer, y, ctxt, f, a, x, epsilon);
	}
	if (smer == 1)
		return inverz(smer, y, ctxt, f, a, x, epsilon);
	return inverz(smer, y, ctxt, f, x, b, epsilon);
}
LD fja (LD x, void * atype) {
	LD a = *((LD *) atype);
	return x*powl(logl(x)/logl(2), a);
}
int levo_od (LD y, const int * a, const int * b, LD * inverzi, int N) {
	int r = 0;
	for (int i = 0; i < N; i++) {
		LD potenca = ((LD) i+1)/N;
		inverzi[i] = inverz(1, y, &potenca, fja, a[i], b[i], 0.01);
		fprintf(stderr, "\tlevo_od: %d\t%Lf\n", i, inverzi[i]);
		if (inverzi[i] == INFINITY)
			r += b[i]-a[i]+1;
		else if (inverzi[i] == -INFINITY)
			;
		else
			r += ceill(inverzi[i])-a[i];
	}
	return r;
}
int main (void) {
	char buf[512];
	fgets(buf, sizeof buf, stdin);
	char * c;
	int N = strtol(buf, &c, 10);
	int k = strtol(++c, NULL, 10);
	int a[N];
	int b[N];
	LD l = 0;
	LD d = 0;
	for (int i = 0; i < N; i++) {
		fgets(buf, sizeof buf, stdin);
		a[i] = strtol(buf, &c, 10);
		b[i] = strtol(++c, NULL, 10);
		LD potenca = ((LD) i+1)/N;
		if (fja(b[i], &potenca) > d) {
			fprintf(stderr, "new max=%Lf for d at i=%d\n", fja(b[i], &potenca), i);
			d = fja(b[i], &potenca);
		}
	}
	/// debug vvvvv
	LD potenca = ((LD) 2/4);
	fprintf(stderr, "DEBUG: %Lf\n", fja(1000000000, &potenca));
	/// debug ^^^^^
	fprintf(stderr, "l=%Lf, d=%Lf, k=%d, N=%d\n", l, d, k, N);
	while (1) {
		LD pivot = (l+d)/2;
		LD inverzi[N];
		int levo = levo_od(pivot, a, b, inverzi, N);
		fprintf(stderr, "pivot = %Lf\tlevo = %d\tl=%Lf\td=%Lf\n", pivot, levo, l, d);
		if (levo == k) {
			fprintf(stderr, "NAŠEL FUNKCIJSKO VREDNOST pri K, ki je %Lf.\n", pivot);
			LD best = NAN;
			for (int i = 0; i < N; i++) {
				LD potenca = ((LD) i+1)/N;
				LD v = floorl(fja(floorl(inverzi[i]), &potenca));
				if (v > pivot)
					continue;
				if (isnan(best) || pivot-v < pivot-best)
					best = v;
				fprintf(stderr, "bestsearch: i=%d, v=%Lf\n", i, v);
			}
			printf("%d\n", (int) best);
			break;
		}
		if (levo < k)
			l = pivot;
		else
			d = pivot;
	}

}