Aquecimento para a OBI – Editorial

Neste sábado ocorreu um contest no URI, o Aquecimento para a OBI.

Eu contribui com quatro problemas, e vou escrever um editorial aqui com a solução deles e dos outros aqui. Com o tempo posso adicionar alguns códigos e comentários complementares.

Para ver o editorial, clique no link abaixo.

A – Feedback

 – [link]

Para resolver este exercício basta criar quatro condições, uma para cada inteiro entre 1 e 4, e imprimir o nome da pessoa correspondente.

Mostrar código

#include <stdio.h>
...
// lemos o tipo de feedback
scanf("%d", &k);

if(k == 1) {
    printf("Rolien\n");
} else if(k == 2) {
    printf("Naej\n");
} else if( ...

Obs: Acha os nomes esquisitos? Leia-os de trás para frente  🙂

B – Adivinha

 – [link]

Há vários valores, e deseja-se saber qual deles é o mais próximo de um valor S. É importante notar que, se dois valores são igualmente próximos a S, deseja-se saber aquele que apareceu antes (o mais à esquerda).

Mostrar código

#include <stdio.h>
#include <stdlib.h>
...
int v[11];
int q, s;
scanf("%d %d", &q, &s);

// nesta variável salvaremos o indice do valor mais próximo
// ela é inicializada com o valor de um indice válido, que pode ou não ser substituído
int prox = 1;

for(int i=1; i<=q; i++) {
    scanf("%d", &v[i]);

    // o método abs retorna o valor absoluto do argumento
    // logo não precisamos nos preocupar com valores negativos, apenas com a diferença
    if(abs(v[i]-s) < abs(v[prox]-s)) {
        prox = i;
    }
}

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

C – Fila do Recreio

 – [link]

Vou citar uma das maneiras de se resolver este exercício.

Iterativamente, buscamos pela maior nota entre as pessoas da fila, e verificamos se a pessoa que tem essa nota está na primeira posição da fila. Caso esteja, o nosso resultado final aumenta.

Em seguida, atribuimos -1 à nota dessa pessoa (para que ela não seja mais a maior), e buscamos novamente pela maior nota entre as pessoas da fila. Verificamos então se ela está na segunda posição da fila. Repetimos esse processo M vezes.

Mostrar código

// retorna o indice da pessoa com maior nota
int maior_nota(int * nota, int m) {
    int maior = 0;

    for(int i=1; i<m; i++) {
        if(nota[i] > nota[maior]) maior = i;
    }

    nota[maior] = -1;
    return maior;
}

int main() {
    ...

    int total = 0;
    for(int i=1; i<=m; i++) {
        if(maior_nota() == i) total++;
    }
}

D – Dividindo a Coca

 – [link]

Este problema envolve o conhecimento de geometria para o cálculo de volume, assim como do conceito de Busca Binária para que o valor possa ser aproximado.

Coincidentemente, ainda essa semana eu comentei sobre uma maneira de descobrir a raiz quadrada de um valor sem usar nenhuma biblioteca. Esta mesma estratégia pode ser usada para resolver esse exercício em particular, com algumas modificações.
Leia a respeito aqui: http://crbonilha.com/pt/descobrindo-a-raiz-quadrada/

Update
Há também como derivar a fórmula para se resolver este exercício sem aproximações. Para mais detalhes, leiam os comentários.

E – Inversão

 – [link]

Este exercício requer que exploremos todas as possibilidades. O truque está em explorar as possibilidades concorrentemente e em velocidade igual, ou seja, em vez de apertar o primeiro botão várias vezes, depois apertar o segundo e então o primeiro outras várias vezes, o certo seria ao mesmo tempo explorar o resultado de se apertar o primeiro botão e o segundo botão, e para cada um desses resultados novamente explorar o resultado em se apertar o primeiro e o segundo botão, e assim por diante.

Isso também é conhecido como Busca em Largura (BFS – Breadth First Search), muito utilizado no contexto de grafos e também útil em diversos contextos, tal como esse.

Utilizando uma fila, o algoritmo ficaria mais ou menos assim:

Mostrar código

#include <queue>
#include <vector>
#include <string.h>
typedef pair<int, int> ii;

// para evitar estados repetidos
bool visitado[11000];
...

// cada elemento da fila tem dois parâmetros: valor e distância
// valor nada mais é que o valor atual
// distância significa quantos botões foram apertados desde A até valor
queue q;
q.push(ii(a, 0));

// marcamos todos os valores como não visitados
memset(visitado, false, sizeof(visitado));

while(!q.empty()) {
    ii aux = q.front();
    q.pop();

    // se o valor for muito alto, provavelmente não vai ser de grande ajuda, e me daria runtime error
    if(u.first >= 11000) continue;

    // se visitado, descartamos o valor atual
    if(visitado[u.first] == true) continue;

    // se não visitado, foi visitado agora, e o marcamos
    visitado[u.first] = true;

    if(u.first == b) {
        printf("%d\n", u.second);
        break;
    }

    // primeito botão
    q.push(ii( u.first+1, u.second+1 ));

    // segundo botão
    q.push(ii( inverter(u.first), u.second+1 ));
    // só falta implementar o método inverter
}

Update
Há um detalhe que é bom ser levado em consideração em exercícios como esse: estados repetidos. Diversas vezes um mesmo valor vai aparecer, e se você continuar explorando o resultado de valores repetidos a quantidade de valores sendo tratados vai ser muito grande, diminuindo a eficiência do algoritmo.

Basta notar, por exemplo, o que acontece com o valor 55. Se você invertê-lo, vai ter denovo o valor 55. Quando você recebe denovo o valor 55, vai invertê-lo, fazendo-o aparecer pela terceira vez, e pela quarta, e assim por diante.

Precisamos prevenir esses casos repetidos, pois se o exploramos uma vez, a segunda é irrelevante.
Eu adicionei o código que trata essas repetições acima.

F – Frase Completa

 – [link]

Este exercício pode ser resolvido utilizando o conceito de contagem. Temos exatamente 26 letras, e precisamos contar quantas delas aparece ao menos uma vez.

Como há um número baixo de diferentes caracteres (26), podemos criar um vetor com 26 posições e inicialmente atribuir todas essas posições com 0. Sempre que uma letra aparecer, fazemos com que a posição dela no vetor seja incrementada, significando que ela apareceu no texto.

No final contamos quantas posições desse vetor são diferentes de 0.

Mostrar código

char frase[1001];
int cont[26], n;

scanf("%d", &n);

// essa chamada é crucial caso se utilize gets em seguida
getchar();

for(int teste=0; teste<n; teste++) {
    // usa-se gets pois ele lê também espaços em branco
    gets(frase);

    int tamanho = strlen(frase); // include string.h

    // para atribuir 0 a todas as posições de cont
    memset(cont, 0, sizeof(cont));

    for(int i=0; i<tamanho; i++) {
        if(frase[i] != ',' && frase[i] != ' ') {
            // aqui está sendo feita a conversão do valor
            // do caractere da tabela ascii para inteiro
            cont[ frase[i]-'a' ]++;
        }
    }

    int total = 0;
    for(int i=0; i<26; i++) {
        if(cont[i] >= 1) total++;
    }

    ...
}

G – Resgate em Queda Livre

 – [link]

[Em breve]

H – Perguntas mais Frequentes

 – [link]

Este exercício pode ser resolvido utilizando o conceito de contagem. Precisamos contar quantas vezes cada pergunta foi feita.

Como há um número limitado de perguntas, e esse número é baixo (P <= 100), podemos montar um vetor de 100 posições, onde cada posição vai ser inicializado com 0, e conforme cada pergunta vai sendo feita tal posição vai sendo incrementada em 1.
No final, basta verificar cada posição desse vetor, e contar quantas posições contém um valor maior ou igual a K.

Mostrar código

int cont[101];

// para atribuir 0 a todas as posições de cont
// necessita de include string.h
memset(cont, 0, sizeof(cont));
...
for(int i=0; i<m; i++) {
    scanf("%d", &p);
    cont[p]++;
}

int total = 0;
for(int i=1; i<101; i++) {
    if(cont[i] >= k) total++;
}

I – Bilhar N+1

 – [link]

Este exercício requer que se calcule a distância euclidiana entre a bola branca e todas as outras. A bola que tiver a menor distância é a escolhida, e seu indice deve ser impresso. Note que se duas bolas tem a menor distância, imprima a de menor indice.

Mostrar código

#include <stdio.h>
#include <math.h>
...
int branca_x, branca_y;
scanf("%d %d", &branca_x, &branca_y);

int bola_x[60], bola_y[60];

// nesta variável salvaremos o indice da bola mais próxima
// ela é inicializada com o valor de um indice válido, que pode ou não ser substituído
int prox = 1;
for(int i=1; i<=n; i++) {
    scanf("%d %d", &bola_x[i], &bola_y[i]);

    // a distância euclidiana das bolas pode também ser vista como
    // a hypotenusa de um triângulo.
    // O método hypot abaixo, da biblioteca math.h, nos retorna esse valor.
    if(hypot(bola_x[i]-branca_x, bola_y[i]-branca_y) <
    hypot(bola_x[prox].branca_x, bola_y[prox]-branca_y) {
        prox = i;
    }
}

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

J – Funções

 – [link]

Para resolver este exercício basta ter algum conhecimento de interpretação de funções matemáticas.
Após resolver cada função, podemos comparar o resultado de cada uma e ver quem ganhou.

Mostrar código

// utilizarei aqui uma funçãs da biblioteca math.h
// pow = potência. O primeiro argumento elevado ao segundo.
int rafael = (int)pow(3*x, 2) + (int)pow(y, 2);
int beto = 2*(int)pow(x, 2) + (int)pow(5*y, 2);
int carlos = (int)pow(y, 3) - 100*x;

if(rafael > beto && rafael > carlos) printf("Rafael ganhou\n");
else if(...