Exercícios da OBI 2018 Resolvidos - Segunda Fase - Nível 2 e Universitário
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