Rezultati

Up. imeNalogaJezikRezultatČas oddaje
finalsolution-2018 Niz C 100/100OK 19. apr '18 @ 16:26

Test Točke Porabljen spomin Porabljen čas Status
#1 10/10 1,465 MiB 0,005 s OK
#2 10/10 1,488 MiB 0,000 s OK
#3 10/10 4,984 MiB 0,016 s OK
#4 10/10 5,012 MiB 0,004 s OK
#5 10/10 4,984 MiB 0,000 s OK
#6 10/10 4,980 MiB 0,004 s OK
#7 10/10 4,980 MiB 0,004 s OK
#8 10/10 4,980 MiB 0,004 s OK
#9 10/10 4,980 MiB 0,010 s OK
#10 10/10 4,980 MiB 0,010 s OK

Ocenjevani program (niz.c):
#include <stdio.h>

int N = 0;
char S[100002];
int M[100002][2];

static int recurse(int i, int o) {
    if (i + 1 >= N) return 0;
    if (M[i][o]) return M[i][o] - 1;
    if (o || S[i] != '1' || S[i+1] != '0') {
        int v = recurse(i + 1, S[i] - '0');
        M[i][o] = v + 1;
        return v;
    }
    int v1 = recurse(i + 2, 0) + 1;
    int v2 = recurse(i + 2, 1) + 1;
    if (v2 < v1) v1 = v2;
    M[i][o] = v1 + 1;
    return v1;
}

int main() {
    scanf("%d %s", &N, S);
    printf("%d\n", recurse(1, S[0] - '0'));
    return 0;
}