summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--šola/aps1/funkcije.c100
-rw-r--r--šola/aps1/in.txt5
2 files changed, 105 insertions, 0 deletions
diff --git a/šola/aps1/funkcije.c b/šola/aps1/funkcije.c
new file mode 100644
index 0000000..49fe6f1
--- /dev/null
+++ b/šola/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/šola/aps1/in.txt b/šola/aps1/in.txt
new file mode 100644
index 0000000..3c8084e
--- /dev/null
+++ b/šola/aps1/in.txt
@@ -0,0 +1,5 @@
+4 42
+440 460
+999999990 1000000000
+160 180
+100 110