diff options
| -rw-r--r-- | šola/aps1/funkcije.c | 100 | ||||
| -rw-r--r-- | šola/aps1/in.txt | 5 |
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 |