From 2a6909b3e81f3895bd12f83946254949fd369c07 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= <anton@sijanec.eu>
Date: Sat, 30 Dec 2023 18:07:17 +0100
Subject: aps1uni funkcije.c

---
 "\305\241ola/aps1/funkcije.c" | 100 ++++++++++++++++++++++++++++++++++++++++++
 "\305\241ola/aps1/in.txt"     |   5 +++
 2 files changed, 105 insertions(+)
 create mode 100644 "\305\241ola/aps1/funkcije.c"
 create mode 100644 "\305\241ola/aps1/in.txt"

diff --git "a/\305\241ola/aps1/funkcije.c" "b/\305\241ola/aps1/funkcije.c"
new file mode 100644
index 0000000..49fe6f1
--- /dev/null
+++ "b/\305\241ola/aps1/funkcije.c"
@@ -0,0 +1,100 @@
+#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;
+	}
+
+}
diff --git "a/\305\241ola/aps1/in.txt" "b/\305\241ola/aps1/in.txt"
new file mode 100644
index 0000000..3c8084e
--- /dev/null
+++ "b/\305\241ola/aps1/in.txt"
@@ -0,0 +1,5 @@
+4 42
+440 460
+999999990 1000000000
+160 180
+100 110
-- 
cgit v1.2.3