Exercícios da OBI 2018 Resolvidos - Segunda Fase - Nível 2 e Universitário

Programação Competitiva

Fala galera,

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

Os problemas da Programação Nível 2 são normalmente problemas com difículdade média com alguns problemas mais avançados. Os problemas avançado são necessários, pois os melhores alunos da Programação Nível 2 representam o Brasil na fase mundial, por isso é necessário garantir que eles tenham o conhecimento necessário para participar da International Olympiad in Informatics (IOI).

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.

Fuga

Código em C++

#include <iostream>
using namespace std;

int L, C, li, lf, ci, cf;
int G[15][15];
int custo;
int resp;

int dl[] = {0,0,-2,2};
int dc[] = {2,-2,0,0};

int limite(int l, int c){
    return l>=1 and c >= 1 and l <= L and c <= C and
            G[l][c]==0;
}

int dfs(int l, int c){
    G[l][c] = 1;
    custo++;
    if( l == lf and c == cf ){
        resp = max(resp, custo);
    }else{
        for(int i = 0; i < 4; i++){
            int ll = l+dl[i];
            int cc = c+dc[i];
            if( limite(ll,cc) ){
                custo++;
                dfs(ll, cc);
                custo--;
            }
        }
    }
    custo--;
    G[l][c] = 0;
}

int main(){
    cin >> L >> C >> li >> ci >> lf >> cf;
    for(int i = 2; i <= L; i+=2)
    for(int j = 2; j <= C; j+=2)
        G[i][j] = 1;

    dfs(li, ci);

    cout << resp << endl;
}



Elevador

Código em C++

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int N;
    int C[10005];

    cin >> N;
    for( int i = 1; i <= N; i++ ){
        cin >> C[i];
    }

    sort(C+1,C+N+1);

    int deuRuim = 0;
    C[0] = 0;
    for(int i = 1; i <= N; i++){
        if( C[i]-C[i-1] > 8 ){
            deuRuim = 1;
        }
    }
    if(deuRuim == 1){
        cout << "N\n";
    }else{
        cout << "S\n";
    }
}



Wifi

Código em C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct evento{
    int x;
    int yi,yf;
    int tipo; //0 - abertura, 1 - finalização
    bool operator < (const evento& t) const {
        return x < t.x;
    }
};

int N;

vector< evento > eventos;

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int xi, xf, yi, yf;
        cin >> xi >> yf >> xf >> yi;
        eventos.push_back({xi, yi,yf, 0});
        eventos.push_back({xf, yi,yf, 1});
    }
    sort( eventos.begin(), eventos.end() );
    int resposta = 0;
    map<int,int> Yocupados;
    for(int i = 0; i < eventos.size(); i++){
        if( eventos[i].tipo == 0 ){
            Yocupados[ eventos[i].yi ] = 0;
            Yocupados[ eventos[i].yf ] = 1;
        }else{
            if( Yocupados[ eventos[i].yi ] == 0 ) resposta++;
            map<int,int>::iterator it = Yocupados.find(eventos[i].yi);
            --it;
            it->second = 1;
            Yocupados.erase( eventos[i].yi );
            Yocupados.erase( eventos[i].yf );
        }
    }
    cout << resposta << endl;
}



Sequência

Código em C++

#include <iostream>
using namespace std;

#define MAXN 100005
#define MAXH 25
#define oo 1000000005

int N;
int L, H;
int s[MAXN];
int cor[MAXN];
int pd[MAXN][MAXH];

int main(){
    cin >> N >> L >> H;
    for(int i = 0; i < N; i++) cin >> s[i];
    for(int i = 0; i < N; i++) cin >> cor[i];

    for(int i=0; i < MAXN;i++)
        for(int j=0;j< MAXH; j++)
            pd[i][j] = -oo;

    //base
    if(cor[0]==1){
        pd[0][0] = 0;//Não peguei
        pd[0][1] = s[0];//Peguei
    }else{
        pd[0][0] = max(s[0], 0);//Posso escolher
    }

    //Programação dinâmica
    int resp=-oo;
    if(L==0) resp = pd[0][0];
    if(L<=1 and H >=1) resp = max(resp, pd[0][1]);

    for(int i = 1; i < N; i++){
        for(int j=0; j <= H; j++){
            if( cor[i]==1 ){
                if(j==0){
                    //Não posso pegar
                    pd[i][j] = 0;
                }else{
                    //Tenho que pegar
                    if(pd[i-1][j-1]!=-oo)
                        pd[i][j] = pd[i-1][j-1]+s[i];
                }
            }else{
                if(j==0){
                    //Posso escolher
                    pd[i][j] = max(pd[i-1][j]+s[i],
                                   0);
                }else{
                    //Tenho que pegar
                    if(pd[i-1][j]!=-oo)
                        pd[i][j] = pd[i-1][j]+s[i];
                }
            }
            if(j<=H and j>=L)
                resp = max(resp, pd[i][j]);
        }
    }
    cout << resp << endl;
}

Bons estudos!

Comentários