OBI 2017 - Game-10

Essa é a resolução da questão 1 da prova da fase Universitária da OBI denotada por “Game-10”. Nessa questão seu objetivo é descobrir o numero de vezes que o jogador precisa apertar o botão para movimentar o avião até a mesma posição do disco voador para atirar.

O primeiro passo é fazer a leitura das variáveis na ordem pedida (números de posições, posição do disco voador e posição do avião) o segundo passo é criar uma estrutura encadeada para checar as possibilidades dos valores inseridos:

1° Caso: O primeiro caso ocorre quando a posição do avião for maior que a posição do disco voador, neste caso, deve subtrair a posição do avião pelo número de posições e depois somar com a posição do disco voador.

if(a>d){

            r = (n-a)+d;

        }

2º Caso: No segundo caso a posição do avião for menor que a posição do disco voador, neste caso simplesmente deve subtrair a posição do disco voador pela posição do avião .

else {

            r = (d-a);

        }

Pronto, agora é só imprimir o resultado!!

OBI 2017 - Palíndroma

Esta é a resolução da questão 2 da prova da fase Universitária da OBI-2017, que consiste em verificar o número mínimo de palíndromas que uma string pode ser dividida. A string é chamada de palíndroma se a sequência de caracteres da esquerda para a direita é igual à sequência da direita pra esquerda. Quando uma palavra não for palíndroma, devemos subdividi-la em partes menores (substrings) que sejam palíndromas.

Primeiramente, criaremos uma função para verificar se a sequência forma uma palíndroma e, caso não for, retornar um valor lógico falso.

int pali(int tam, char *nome){
int i,ok=1,j=tam-1;
for(i=0;i<tam/2;i++){
    if(nome[i]!=nome[j]){
        ok=0;
        break;}
    j--;}
 return ok;
} 

Após isto devemos pensar na subdivisão da entrada em substrings, ou seja, gerar todas as substrings e verificar se formam palíndromas e  armazená-las em uma variável global. Por fim retornará a quantidade total das substrings. A cada repetição do laço, geraremos uma substring e toda vez que ela for palíndroma, armazenaremos ela na matriz palíndroma.

int gera_todas_pali(int tam, char *nome){
int i,j,k=0,r,t;
char aux[tam+1];
for(i=0;i

Agora precisamos encontrar o menor número de conjuntos possíveis. Em nossa primeira condição, iremos comparar se a nossa substring pertence a posição atual da sequência, na segunda verificamos se essa substring é maior, e caso ela for utilizaremos a função 'substring' para verificar se ela encaixa na sequência. Na terceira condição, verificamos se elas são as mesmas. Por fim, incrementamos o contador i com o tamanho da substring e o total.

int verifica_menor_palindroma(int k, int tam, char *str){
int i=0,j,maior,total=0;
char aux[MAX];
while(i<tam){
  maior=0;
  for(j=0;j<k;j++){
    if(palindroma[j][0]==str[i]){
      int t=strlen(palindroma[j]);
      if(t>maior){
       substring(str, aux, i, t);
       int ok=strcmp(aux,palindroma[j]);
 if(!ok){
          maior=t;
        }}}}
    i+=maior;
   total++;}
return total;
}

A função verifica_menor_palindroma utiliza a função substring.

void substring(char *s, char *sub, int p, int l) {
   int c = 0;
 
   while (c < l) {
      sub[c] = s[p+c];
      c++;
   }
   sub[c] = '\0';
}

Pronto terminamos, agora só é preciso fazer as leituras e chamar as funções na função principal main.

Coded by: André da Cunha Ribeiro.

Resumão da OBI 2017

No dia 12 de maio de 2017 ocorreu a XIX Olimpíada Brasileira de Informática, com isso faremos aqui um resumo das questões da prova da modalidade universitária.

No ano de 2017 houve mudanças em relação ao número de questões e o tempo de duração de aplicação da prova. A prova deste ano teve 3 questões e 2 horas de duração, já a de 2016 teve 5 questões e 5 horas de duração. No ano anterior o aluno tinha em 1 hora para resolver cada questão já este ano ele passou a ter 40 minutos, por outro lado o número de questões do ano anterior é maior e isso implica em um maior desgaste do aluno no final da prova. Já este ano o número de questões foi menor assim não havendo tanto desgaste do aluno no final da prova.

Game-10, Palíndromo e Botas Trocadas estes são o nome das questões deste ano, cada uma aborda um tema diferente, sendo que o Game-10 aborda mais o conceito matemático, o Palíndromo aborda a manipulação de string e o Botas Trocadas aborda problemas de contagem.

Game-10

O segredo do game-10 está em descobrir se a posição do avião é maior ou menor que a posição do disco voador. O primeiro caso ocorre quando a posição do avião for maior que a posição do disco voador, neste caso, você deve subtrair a posição do avião pelo número de posições e depois somar com a posição do disco voador. No segundo caso a posição do avião for menor que a posição do disco voador, neste caso você simplesmente deve subtrair a posição do avião pela posição do disco voador.

Palíndromo

Pois bem a questão de maior dificuldade da prova (ou não). Nesta questão temos que verificar o número mínimo de palavras palíndromas em uma cadeia de caracteres. Uma solução para essa questão seria separar todas as substrings palíndroma, após essa divisão você concatenaria as maiores substrings de forma que os mesmos caracteres não se repita e no final dessa concatenação obtenha uma string igual a original. A partir desse processo é só utilizar um contador para contar as strings utilizadas na concatenação.

Botas Trocadas

O seu objetivo em Botas Trocadas é dizer quantos pares de botas (de mesmo tamanho) temos em uma determinada quantidade de botas. Para esse problema pode se criar dois vetores, um para o lado esquerdo e o outro para o direito, os índices será o tamanho das botas, e para cada valor lido adicionarmos na posição do vetor (para isso ambos vetores tem que estar zerado). Por fim é só fazer somatório de todas posições dos dois vetores com menor valor.

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;  
 }