OBI 2017 - Botas Trocadas

Essa é a resolução da questão 3 da prova da fase Universitária da OBI denotada por “Botas Trocadas”. Nessa questão seu objetivo é indicar o número total de pares de botas correto que podem ser formados, um par de botas correto seria duas botas onde seu tamanho é igual mas são de pés diferentes. Logo de inicio podemos criar dois vetores um para o pé direito e outro para o pé esquerdo ambos os vetores tem que ser zerados, esses vetores serão usados para mostrar quantos pés de botas de determinado tamanho. Já o tamanho do vetor será de 60-30 que é a variação do tamanho das botas.

 int i;  
 int vetorD[60-30];  
 int vetorE[60-30];  
 for(i = 0;i < 60-30; i++){  
   vetorD[i] = 0;  
   vetorE[i] = 0;  
 }  

Agora teremos que fazer as leituras, a primeira linha contem um valor de n que é o número de botas, e as próximas n linhas serão as botas (tamanho e o pé). Quando lermos uma das n botas adicionaremos mais 1 a posição de tamanho-30 (esse tamanho se da pelo motivo da posição zero ser o tamanho 30 e a posição 30 ser o tamanho 60) do vetor responsável pelo respectivo pé.

 int n;  
 int tamanho;  
 char pe;  
 scanf("%d", &n);  
 for(i = 0 ; i < n; i++){  
   scanf("%d %c", &tamanho, &pe);  
   if(pe == 'D')  
     vetorD[tamanho-30]++;  
   else  
     vetorE[tamanho-30]++;  
 }  

Por fim temos que fazer um somatório onde faremos a soma de todas as posições com o menor valor e imprimindo ela no final.

 int somatorio = 0;  
 for(i = 0 ; i < 60-30; i++){  
   if(vetorD[i] < vetorE[i])  
     somatorio+=vetorD[i];  
   else  
     somatorio+=vetorE[i];  
 }  
 printf("%d\n", somatorio);  

Esse será o código completo.

 #include <stdio.h>  
 int main(void){  
   //PARTE 1  
   int i;  
   int vetorD[60-30];  
   int vetorE[60-30];  
   for(i = 0;i < 60-30; i++){  
     vetorD[i] = 0;  
     vetorE[i] = 0;  
   }  
   //PARTE 2  
   int n;  
   int tamanho;  
   char pe;  
   scanf("%d", &n);  
   for(i = 0 ; i < n; i++){  
     scanf("%d %c", &tamanho, &pe);  
     if(pe == 'D')  
       vetorD[tamanho-30]++;  
     else  
       vetorE[tamanho-30]++;  
   }  
   //PARTE 3  
   int somatorio = 0;  
   for(i = 0 ; i < 60-30; i++){  
     if(vetorD[i] < vetorE[i])  
       somatorio+=vetorD[i];  
     else  
       somatorio+=vetorE[i];  
   }  
   printf("%d\n", somatorio);  
   return 0;  
 }