1069 - Diamantes e Areia

Extremamente parecido com o problema 1068 - Balanço de Parênteses I...

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Problema muito parecido com o 1068 - Balanço de Parênteses I, que também pode ser resolvido com a ajuda tanto de uma variável acumuladora quanto de uma pilha.

A diferença entre os dois problemas é que agora não existem entradas inválidas, tudo o que importa agora são quantos pareamos diferentes podemos fazer.

Alternativa 1 - Usando uma variável para acumular

C99

#include <string.h>
#include <stdio.h>

int main(){
    char expressao[1001];
    int N, tam, resposta, parenteses;

    scanf("%d\n", &N);
    
    for(int k = 0; k < N; ++k){
        scanf("%s\n", &expressao);

        resposta = 0;
        parenteses = 0;
        tam = strlen(expressao);
        for(int i = 0; i < tam; ++i){
            if(expressao[i] == '<'){
                ++parenteses;
            }else if(expressao[i] == '>' && parenteses > 0){
                --parenteses;
                ++resposta;
            }
        }

        printf("%d\n", resposta);
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9

Alternativa 2 - Usando pilha

C99

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

struct pilhaNo{
    char valor;
    struct pilhaNo* abaixo;
};

struct pilha{
    int tamanho;
    struct pilhaNo* topo;
};

void push(struct pilha* p, char valor){
    p->tamanho += 1;
    struct pilhaNo* novoTopo = (struct pilhaNo*) malloc(sizeof(struct pilhaNo));

    novoTopo->valor = valor;
    novoTopo->abaixo = p->topo;
    p->topo = novoTopo;
}

void pop(struct pilha* p){
    if(p->tamanho > 0){
        p->tamanho -= 1;
        struct pilhaNo* velhoTopo = p->topo;
        p->topo = p->topo->abaixo;
        free(velhoTopo);
    }
}

char top(struct pilha* p){
    return p->topo->valor;
}

int size(struct pilha* p){
    return p->tamanho;
}

int empty(struct pilha* p){
    return p->tamanho == 0;
}

void inicializa(struct pilha* p){
    p->tamanho = 0;
    p->topo = NULL;
}

void destroi(struct pilha* p){
    while(!empty(p)){
        pop(p);
    }
}

int main(){
    struct pilha p;
    int N, tam, resposta;
    char expressao[1001];

    scanf("%d\n", &N);

    for(int k = 0; k < N; ++k){
        scanf("%s\n", &expressao);

        resposta = 0;
        inicializa(&p);
        tam = strlen(expressao);

        for(int i = 0; i < tam; ++i){
            if(expressao[i] == '<'){
                push(&p, '<');
            }else if(expressao[i] == '>'){
                if(!empty(&p)){
                    ++resposta;
                    pop(&p);
                }
            }
        }

        printf("%d\n", resposta);

        destroi(&p);
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9