Exercícios da OBI 2018 Resolvidos - Primeira Fase - Nível 1

Programação Competitiva

Fala galera,

Hoje nós trazemos para vocês as resoluções dos exercícios da primeira fase da Olimpíada Brasileira de Informática de 2018, Programação Nível 1 (P1).

Os problemas da Programação Nível 1 são normalmente problemas com difículdade média, isso quer dizer que você precisa ter algum conhecimento de algoritmos, principalmente conhecer os algoritmos e técnicas clássicas como o mergesort, dijkstra, conhecimento de programação dinâmica, etc.

Todos os problemas já estão disponíveis no Neps Academy. É recomendado que você primeiro tente resolver o problema antes de conferir a resolução a seguir.

Xadrez

Código em C++

#include <iostream>
using namespace std;

int main(){
    int L, C;

    cin >> L >> C;

    cout << (1+(L-1)+(C-1))%2 << endl;
}




Escadinha

Código em C++

#include <iostream>
using namespace std;

int main(){
    int N;
    int vetor[1005];

    cin >> N;
    for(int i = 0;i<N;i++){
        cin >> vetor[i];
    }
    int resposta = 1;
    for(int i = 2; i < N; i++){
        if( (vetor[i]-vetor[i-1]) !=
            (vetor[i-1]-vetor[i-2]) ){
            resposta++;
        }
    }
    cout << resposta << endl;
}



Pirâmide

Código em C++

#include <iostream>
using namespace std;

int N;
int M[105][105];
int dp[105][105];

int solve(int l, int c){
    if(dp[l][c]!=-1) return dp[l][c];
    if( l==1 ) return dp[l][c] = M[l][c];

    int soma = 0;
    for(int i = 0; i < l; i++){
        soma += M[l][c+i];
    }
    return dp[l][c] = soma + min(solve(l-1, c),
                                 solve(l-1, c+1) );
}

int main(){
    cin >> N;
    for(int i = 1; i<=N; i++)
    for(int j = 1; j<=N; j++)
        cin >> M[i][j];

    for(int i = 1; i<=N; i++)
    for(int j = 1; j<=N; j++)
        dp[i][j] = -1;

    cout << solve(N, 1) << endl;
}

Bons estudos!

Comentários