Programação Competitiva

A divisão de Suprimentos de Botas e Calçados do Exército comprou um grande número de pares de botas de vários tamanhos para seus soldados. No entanto, por uma falha de empacotamento da fábrica contratada, nem todas as caixas entregues continham um par de botas correto, com duas botas do mesmo tamanho, uma para cada pé. O sargento mandou que os recrutas retirassem todas as botas de todas as caixas para reembalá-las, desta vez corretamente.

Quando o sargento descobriu que você sabia programar, ele solicitou com a gentileza habitual que você escrevesse um programa que, dada a lista contendo a descrição de cada bota entregue, determina quantos pares corretos de botas poderão ser formados no total.

Entrada

A primeira linha de um caso de teste contém um inteiro N indicando o número de botas individuais entregues. Cada uma das N linhas seguintes descreve uma bota, contendo um número inteiro M e uma letra L, separados por um espaço em branco. M indica o número do tamanho da bota e L indica o pé da bota: L = ‘D’ indica que a bota é para o pé direito, L = ‘E’ indica que a bota é para o pé esquerdo.

Saída

Para cada caso de teste imprima uma linha contendo um único número inteiro indicando o número total de pares corretos de botas que podem ser formados.

Restrições

•2 ≤ N ≤ 10^4
•N é par
•30 ≤ M ≤ 60
•L ∈{D,E}

Exemplo

Solução em C/C++

#include<stdio.h>

int main(){
	int D[61], E[61];
	int i,N,M,r;
	char L;

        //enquanto existem valores sendo fornecidos
	while(scanf("%d", &N)>=0){
		r=0;
		//preenche os dois vetores com zeros
		for(i=0; i<61; i++){
			D[i] = 0;
			E[i] = 0;
		}
		//enquanto tiver botas (N > 0) faça
		while(N--){
			scanf("%d %c", &M, &L);
			if(L=='E') {
                            E[M]++;
                        } else {
                    	    D[M]++;
                        }
			if(E[M] && D[M]){
			    E[M]--;
			    D[M]--;
			    r++;
			}
		}
		printf("%d\n", r);
	}

	return 0;
}

Veja essa execução online: http://ideone.com/66GW5g

Solução em Python

D = [0]*61
E = [0]*61

N = int(input())
while N >= 0:
    r=0
    #preenche os dois vetores com zeros
    for i in range(61):
        D[i] = 0;
        E[i] = 0;

    #enquanto tiver botas (N > 0) faça
    while N:
        N = N - 1
        M = int(input())
        L = raw_input()
        
        if L=='E':
            E[M] = E[M] + 1
        else:
            D[M] = D[M] + 1

        if E[M] and D[M]:
            E[M] = E[M] - 1
            D[M] = D[M] - 1
            r = r + 1

    print r
    N = int(input())

Veja essa execução online: http://www.codeskulptor.org/#user40_Zxz2BgEPa0_0.py