diff options
Diffstat (limited to 'inf/zotksd/4.c')
-rw-r--r-- | inf/zotksd/4.c | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/inf/zotksd/4.c b/inf/zotksd/4.c new file mode 100644 index 0000000..4c3113a --- /dev/null +++ b/inf/zotksd/4.c @@ -0,0 +1,96 @@ +// todo: pazi na težave s prvim elementom +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> +#define S 1600002 +#define ABS(x) ((x) > 0 ? (x) : -(x)) +int main (void) { + int ukazov = 0; + char buf[S]; + fgets(buf, S, stdin); + int n = strtol(buf, NULL, 10); + fgets(buf, S, stdin); + char * cp = buf; + int * arr = calloc(n, sizeof *arr); + int * repr = calloc(10e6, sizeof *arr); + int najrepr = 0; + int najreprval = 0; + for (int i = 0; i < n; i++) { + arr[i] = strtol(cp, &cp, 10); + if (++repr[arr[i]] > najreprval) { + najreprval = repr[arr[i]]; + najrepr = arr[i]; + } + cp++; + } + free(repr); + int razd_od_centr = INT_MAX; + int center = 0; + if (najreprval == 1) { + najrepr = arr[n/2]; + center = n/2; + } + for (int i = 0; i < n; i++) { + if (arr[i] == najrepr && ABS(n/2-i) < razd_od_centr) { + razd_od_centr = ABS(n/2-i); + center = i; + } + } + if (najreprval == 1) { + center = n/2; + } +#ifndef EVAL + fprintf(stderr, "najrepr je število %d, ki ima toliko pojavitev: %d\n", najrepr, najreprval); +#endif + int levo = 0; + int desno = n-1; + s: + while (arr[levo] == najrepr) { + if (levo == n-1) + goto k; + levo++; + } + while (arr[desno] == najrepr) { + if (desno == 0) + goto k; + desno--; + } + if (levo == desno) { + ukazov++; + goto k; + } + if (center > levo && center < desno) { + ukazov++; + arr[levo] = najrepr; + arr[desno] = najrepr; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. cached center\n", levo, center, desno); +#endif + goto s; + } + center = 0; + for (int i = levo+1; i < desno; i++) { + if (arr[i] == najrepr) { + center = i; + arr[levo] = najrepr; + arr[desno] = najrepr; + ukazov++; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. našel center, en ukaz\n", levo, center, desno); +#endif + goto s; + } + } + if (center == 0) { + ukazov += 2; + arr[levo] = najrepr; + arr[desno] = najrepr; + arr[(center = levo+(desno-levo)/2)] = najrepr; +#ifndef EVAL + fprintf(stderr, "(%d, %d, %d) .. ni bilo centra, dva ukaza\n", levo, center, desno); +#endif + goto s; + } + k: + printf("%d\n", ukazov); +} |