1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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;
}
}
|
