Comentário por Rogério Júnior
Para ver o caderno de tarefas da segunda fase da Programação Nível 2 da OBI 2016, clique aqui.
Este comentário utiliza os objetos cin e cout como métodos de entrada e saída. Eles estão na biblioteca iostream, do C++, e são de muito fácil uso.
Para ler uma variável qualquer a, basta a linha de código: cin >> a;
Para ler uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cin >> a >> b >> c >> ...;
Para imprimir uma variável qualquer a, basta a linha de código: cout << a;
Para imprimir uma sequência de variáveis a, b, c, ... quaisquer, basta a linha de código: cout << a << b << c << ...;
Além disso, também é usada, por simplicidade, a biblioteca "bits/stdc++.h". Ela contêm todas as bibliotecas da STL, e mais algumas úteis. Para mais informações, clique aqui e veja tudo o que ela inclui. Geralmente, elá só funciona em Windows e Linux.
Pô, que mão
Conhecimento prévio necessário
- Ordenação (Aula 5)
Observe que, neste problema, um algoritmo guloso funciona muito bem. Basta que eu sempre tente evoluir o monstrinho que ainda não foi evoluído e tem o menor custo de evolução. Para isso, vou colocar os três custos em um vetor, ordená-lo, e ver qual o maior prefixo dele cuja soma não supera .
Tal algoritmo é bem simples: basta percorrer o vetor, a partir da primeira posição. Se for menor que o valor no vetor, paro de percorrê-lo. Caso contrário, subtraio o valor em , aumento uma unidade na resposta e continuo o loop.
Por fim, imprimo a resposta. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Pô, que mão - F2P2 - OBI 2016 | |
// Rogério Júnior | |
// Complexidade: O(1) | |
#include "bits/stdc++.h" | |
using namespace std; | |
#define PB push_back | |
vector<int> v; | |
int n, cont; | |
int main(){ | |
// leio o valor de n | |
cin >> n; | |
// para cada monstro | |
for(int i=0;i<3;i++){ | |
// leio seu custo de evolução | |
int a; | |
cin >> a; | |
// e o coloco no vetor v | |
v.PB(a); | |
} | |
// ordeno v | |
sort(v.begin(),v.end()); | |
// e o percorro | |
for(int i=0;i<v.size();i++){ | |
// se não posso evoluir o monstro, paro | |
if(n<v[i]) break; | |
// mas enquanto poder, retiro seu custo de N | |
n-=v[i]; | |
// e aumento a resposta em uma unidade | |
cont++; | |
} | |
// por fim, imprimo a resposta | |
cout << cont << "\n"; | |
// e retorno zero | |
return 0; | |
} |
Jardim de Infância
Conhecimento prévio necessário
Essa é uma questão de pura implementação, que não envolve nenhum algoritmo mais aprofundado. Ela simplesmente nos pede que façamos a checagem de oito condições, imprimindo 'S' se forem todas verdadeiras, ou 'N', se alguma delas for falsa.
Basta, portanto, que mostremos como fazer, computacionalmente, cada uma das checagens. Veja:
- é agudo - Pela Lei dos Cossenos, basta checar se d(P_2,P_3)^2" />.
- e têm o mesmo comprimento - Distâncias entre pontos de coordenadas inteiras não são necessariamente inteiros, o que pode acarretar em problemas de precisão, mas seus quadrados são. Deste modo, o ideal é checar se .
- Os pontos e são colineares - Basta checar se e são colineares e, depois, se e também são. Para checar se três pontos e são colineares, olhamos para os vetores por eles definidos. Seja , e , ou seja tem origem em e fim em e tem origem em e fim em . Sabemos que, se é o ângulo formado pelos vetores e , então . Assim, sabemos que , e são colineares se, e somente se, ou , logo, e a colinearidade deles é equivalente a . Logo, basta checar se o produto vetorial de e é zero.
- Os pontos médios dos segmentos e são coincidentes - Basta checar se . Para evitar divisões e erros de precisão basta checar se , ou seja, se e .
- O segmento tem comprimento maior que - Novamente, por questões de precisão, é melhor checar se d(P_4,P_5)^2" />.
- Os segmentos e são perpendiculares ao segmento - Pela checagem , sabemos que está na reta , logo . Assim, pelo caso particular da Leis dos Cossenos que cai no Teorema de Pitágoras, basta checarmos se . De maneira análoga, , logo, basta checarmos se .
- e têm o mesmo comprimento - Novamente, o ideal é checar se .
- Os pontos e devem estar separados pela reta - Note que isso só irá acontecer se e forem um côncavo e um convexo. De maneira semelhante ao check , o é convexo ou côncavo se a magnitude de for positiva ou negativa, respectivamente, logo, basta checarmos se , pois devem ser um negativo e o outro positivo.
No código, usaremos as seguintes funções:
- long long dist2(ii a, ii b) - retorna a distância ao quadrado entre os pontos, representados como pares, a e b.
- long long cross(ii a, ii b, ii c) - retorna a magnitude do produto vetorial entre b-a e c-a.
- bool col(ii a, ii b, ii c) - retorna true se os pontos a, b e c forem colineares, e false caso contrário.
- long long sinal(long long x) - retorna 1 se x>0, -1 se x<0 e 0 se x=0.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Jardim de infância - F2P2 - OBI 2016 | |
// Rogério Júnior | |
// Complexidade: O(1) | |
#include "bits/stdc++.h" | |
using namespace std; | |
#define F first | |
#define S second | |
typedef long long ll; | |
typedef pair<ll,ll> ii; | |
ii p[10]; | |
// natureza de X | |
ll sinal(ll x){ | |
if(x>0) return 1; | |
if(x<0) return -1; | |
if(x==0) return 0; | |
} | |
// distância ao quadrado entre A e B | |
ll dist2(ii a, ii b){ | |
return (a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S); | |
} | |
// produto vetorial dos pontos A, B e C | |
ll cross(ii a, ii b, ii c){ | |
// defino X=B-A e Y=C-A | |
ii x=ii(b.F-a.F,b.S-a.S),y=ii(c.F-a.F,c.S-a.S); | |
// e retorno XxY | |
return (x.F*y.S)-(y.F*x.S); | |
} | |
// testa a colinearidade de A, B e C | |
bool col(ii a, ii b, ii c){ | |
return (cross(a,b,c)==0); | |
} | |
// Cada um dos checks do problema | |
bool check1(){ | |
return (dist2(p[1],p[2])+dist2(p[1],p[3])>dist2(p[2],p[3])); | |
} | |
bool check2(){ | |
return (dist2(p[1],p[2])==dist2(p[1],p[3])); | |
} | |
bool check3(){ | |
return (col(p[2],p[3],p[4]) and col(p[2],p[3],p[5])); | |
} | |
bool check4(){ | |
return (p[2].F+p[3].F==p[4].F+p[5].F and p[2].S+p[3].S==p[4].S+p[5].S); | |
} | |
bool check5(){ | |
return (dist2(p[2],p[3])>dist2(p[4],p[5])); | |
} | |
bool check6(){ | |
return(dist2(p[4],p[6])+dist2(p[4],p[2])==dist2(p[2],p[6]) and dist2(p[5],p[7])+dist2(p[5],p[3])==dist2(p[3],p[7])); | |
} | |
bool check7(){ | |
return (dist2(p[4],p[6])==dist2(p[5],p[7])); | |
} | |
bool check8(){ | |
return (sinal(cross(p[2],p[3],p[1]))*sinal(cross(p[2],p[3],p[6]))==-1); | |
} | |
// função que checa todos os checks | |
bool check(){ | |
return (check1() and check2() and check3() and check4() and check5() and check6() and check7() and check8()); | |
} | |
int main(){ | |
// leio as coordenadas dos pontos | |
for(int i=1;i<=7;i++) cin >> p[i].F >> p[i].S; | |
// e testo se todas as condições são atendidas | |
cout << char(check()?'S':'N') << "\n"; | |
// por fim, retorno zero | |
return 0; | |
} |
Quase primo
Solução de Carlos Vinícius
Conhecimento prévio necessário:
- Princípio da Inclusão-Exclusão
- Vetores (Aula 3)
- Funções (Aula 4)
Este é um problema que mistura bem habilidades em matemática e em programação. Enunciar a solução é simples: basta usar o PIE (Princípio da Inclusão-Exclusão). Seja o conjunto dos números menores que que são múltiplos do primo de índice , fornecido na entrada.
Note que queremos o valor de , onde . Pelo PIE, sabemos que , onde é a soma dos módulos de todos os conjuntos formados pela interseção de exatamente dentre os conjuntos .
Assim, basta fazer um programa que, para cada , calcula o valor de , o adicionando à resposta se for ímpar, e subtraindo se for par.
Para calcular o valor de , seja o conjunto das maneiras de escolher números de a . Cada número desse representará o índice de um dos primos, que devem estar em ordem crescente. Cada conjunto de índices pode ser representado como uma sequência de termos (os índices). Desta maneira, haverá conjuntos de índices .
Assim, basta usarmos uma função recursiva que, assim como o knapsack, percorrerá todas as possibilidades de escolha de alguns dos números. Note que cada produto deles é único, pois são todos primos. A recursão deve passar por cada primo, testando colocá-lo ou não. Se, ao colocarmos o primo, o produto ultrapassar , nem precisamos testar tal possibilidade. Quando tivermos um determinado produto , fruto da escolha de alguns primos, esse produto será divisor do piso de números que não superam , logo, pelo princípio da inclusão exclusão, adicionamos esses números se a escolha tiver uma quantidade ímpar de primos e subtraímos caso a quantidade seja par.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Quase primo - F2P2 - OBI 2016 | |
// Carlos Vinícius | |
// Complexidade: O(f(N,K)) | |
// obs* f(a,b) é a quantidade de formas de escolher | |
// até K primos cujo produto não supera N | |
#include <bits/stdc++.h> | |
using namespace std; | |
#define MAXK 45 | |
int n, k, prime[MAXK]; | |
// Função recursiva que gera todos os subconjuntos dos primos da entrada | |
// idx = índice do primo que estamos analizando no momento; | |
// prod = produto dos elementos do subconjunto atual; | |
// qtd = quantidade de elementos no subconjunto atual | |
int solve(int idx = 0, int prod = 1, int qtd = 0){ | |
// Se já passei por todos os elementos... | |
if(idx == k){ | |
// n/prod é a quantidade de múltiplos menores ou iguais a n do produto acumulado | |
int ret = n/prod; | |
// Se a quantidade de elementos for ímpar, a quantidade de múltiplos será retirada da resposta | |
if(qtd%2 == 1){ | |
ret = -ret; | |
} | |
// Retorno o resultado | |
return ret; | |
} | |
// O elemento da posição idx pode ou não entrar no subconjunto; | |
// Primeiramente, não insiro o elemento atual no subconjunto | |
int ret = solve(idx + 1, prod, qtd); | |
// Agora, considero a possibilidade de inseri-lo. Observe que se o produto passar de N, não é necessário continuar. | |
if(prod*1LL*prime[idx] <= n){ | |
ret += solve(idx + 1, prod*prime[idx], qtd + 1); | |
} | |
// Retorno o resultado | |
return ret; | |
} | |
int main(){ | |
// leio N e a quantidade de primos | |
cin >> n >> k; | |
// leio os primos | |
for(int i = 0; i < k; i++) cin >> prime[i]; | |
// e calculo o resultado recursivamente | |
cout << solve() << "\n"; | |
// por fim, retorno zero | |
return 0; | |
} |
Falta uma
Conhecimento prévio necessário
- Estruturas da STL (Aula 7)
Vamos transformar cada permutação da entrada em um vector e adicioná-lo a um set, para que ele contenha todas as permutações da entrada. Isso é válido porque o vector tem os operadores <, > e == implementados. Feito isso, basta criarmos um outro vector com os números de 1 a N (nesta ordem) e usar a função next_permutation para que este vector percorra todas as permutações possíveis, até encontrar uma que não está no set. Quando encontrá-la, basta imprimi-la.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Falta uma - F2P2 - OBI 2016 | |
// Rogério Júnior | |
// Complexidade: O(N!*N*log(N!)) | |
#include "bits/stdc++.h" | |
using namespace std; | |
#define PB push_back | |
set< vector<int> > s; | |
vector<int> v; | |
int n, fat=1; | |
int main(){ | |
// leio o valor de N | |
cin >> n; | |
// calculo N! para saber quantas permutações estarão na entrada | |
for(int i=1;i<=n;i++) fat*=i; | |
// para cada uma das N!-1 permutações | |
for(int i=1;i<fat;i++){ | |
// a guardo no vector u | |
vector<int> u; | |
for(int j=0;j<n;j++){ | |
// adicionando a ele cada um de seus elementos | |
int a; | |
cin >> a; | |
u.PB(a); | |
} | |
// e adiciono u em um set s | |
s.insert(u); | |
} | |
// crio um vector com os números de 1 a N | |
for(int i=1;i<=n;i++) v.PB(i); | |
// e crio um loop | |
while(true){ | |
// que só para se v não estiver no set | |
if(s.find(v)==s.end()) break; | |
// e enquanto estiver, transforma v na próxima permutação | |
// e continua para a próxima iteração do loop | |
next_permutation(v.begin(),v.end()); | |
} | |
// quando o loop acabar, v será a permutação que falta | |
// então imprimo seus elementos | |
for(int i=0;i<v.size();i++) cout << v[i] << " \n"[i==n-1]; | |
// por fim, retorno zero | |
return 0; | |
} |
Ciclovias
Conhecimento prévio necessário
Este foi, com certeza, o problema mais difícil da prova. Entretanto, o algoritmo que o soluciona é relativamente simples, ao contrário do que ocorreu ano passado, com um problema extremamente técnico.
No começo, o maior caminho que sai de cada vértice tem tamanho : o próprio vértice. Agora, vamos percorrer o grafo tentando aumentar estes caminhos. Vamos processar os vértices do maior para o menor. Suponha que estejamos no vértice e todos os outros vértices maiores que ele já foram processados. Sejam os vizinhos do vértice , em ordem crescente de índice. Agora, vamos analisar, para cada vizinho , qual o maior caminho que começa em e tem como segundo vértice.
Seja o maior caminho que começa em . Como todos os vértices já processados são maiores que , o de um determinado vértice qualquer faz referência a um caminho que tem o segundo vértice maior que . Deste modo, partindo do vértice e passando por , posso ir para qualquer vértice se, e somente se, i" /> (pois u_i" />, visto que estão ordenados por índice), e então poderei continuar o maior caminho que parte de , pois o próximo vértice é maior que . Logo, o maior caminho que sai de , passa por e segue por tem tamanho , e devo atualizar o valor de .
Então, em cada vértice , devo atualizar seus vizinhos da seguinte forma: , para todos os valores de e com . Entretanto, isso pode ter ma complexidade quadrática, mas resolvemos isso rapidamente ao considerarmos sufixos. Note que, para cada , posso definir a sequência . Deste modo, para cada , o tamanho do maior caminho que começa em e vai para é mais o maior número do sufixo da sequência , e podemos calcular esse valor em se pré-calcularmos, no começo do processamento do vértice , o valor de , para todo , onde , e o maior caminho que começa em e vai para terá comprimento igual a .
Basta aplicarmos este processamento em cada vértice e, toda vez que descubro o maior caminho de que vai para , checo se ele é maior que o maior caminho conhecido que começa em , atualizando seu valor, se este for o caso. Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Ciclovias - F2P2 - OBI 2016 | |
// Rogério Júnior | |
// Complexidade: O(M*(log M)) | |
#include "bits/stdc++.h" | |
using namespace std; | |
#define PB push_back | |
#define MAXN 100100 | |
vector<int> lista[MAXN]; | |
int n, m, resp[MAXN], maior[MAXN]; | |
int main(){ | |
// leio os valores de n e m | |
cin >> n >> m; | |
// no começo, o maior caminho que começa em cada vértice | |
// tem tamanho 1: o próprio vértice | |
for(int i=1;i<=n;i++) resp[i]=1; | |
// leio cada aresta e guardo na lista de adjacencias | |
for(int i=0;i<m;i++){ | |
int a, b; | |
cin >> a >> b; | |
lista[b].PB(a); | |
lista[a].PB(b); | |
} | |
// ordeno os vizinhos de cada vértice | |
for(int i=1;i<=n;i++) sort(lista[i].begin(),lista[i].end()); | |
// processo os vértices do maior para o menor | |
for(int i=n;i>=1;i--){ | |
// primeiro, calculo o maior caminho de cada sufixo | |
maior[lista[i].size()]=0; | |
for(int j=lista[i].size()-1;j>=0;j--){ | |
int v=lista[i][j]; | |
maior[j]=max(resp[v],maior[j+1]); | |
} | |
// depois o maior caminho de cada vizinho cujo segundo vértice é i | |
for(int j=0;j<lista[i].size();j++){ | |
int v=lista[i][j]; | |
// e atualizo resp[v] para cada vizinho | |
resp[v]=max(resp[v],2+maior[j+1]); | |
} | |
} | |
// por fim, imprimo a resposta de cada vértice | |
for(int i=1;i<=n;i++) cout << resp[i] << " \n"[i==n]; | |
// e retorno zero | |
return 0; | |
} |