Nível 2 - Fase 2

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 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 abc, ... 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 abc, ... 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

  1. 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 N.

Tal algoritmo é bem simples: basta percorrer o vetor, a partir da primeira posição. Se N for menor que o valor no vetor, paro de percorrê-lo. Caso contrário, subtraio o valor em N, aumento uma unidade na resposta e continuo o loop.

Por fim, imprimo a resposta. Segue o código para melhor entendimento:


// 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;
}

view raw

pokemon.cpp

hosted with ❤ by GitHub

Jardim de Infância

Conhecimento prévio necessário

  1. Produto vetorial
  2. Lei dos cossenos

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:

  1. \angle P_2P_1P_3 é agudo - Pela Lei dos Cossenos, basta checar se d(P_1,P_2)^2+d(P_1,P_3)^2 data-recalc-dims=d(P_2,P_3)^2" />.
  2. \overline{P_1P_2} e \overline{P_1P_3} 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 d(P_1,P_2)^2=d(P_1,P_3)^2.
  3. Os pontos P_2,P_3,P_4 e P_5 são colineares - Basta checar se P_2,P_3 e P_4 são colineares e, depois, se P_2,P_3 e P_5 também são. Para checar se três pontos A,B e C são colineares, olhamos para os vetores por eles definidos. Seja \vec{X}=\vec{B}-\vec{A}, e \vec{Y}=\vec{C}-\vec{A}, ou seja \vec{X} tem origem em A e fim em B e \vec{Y} tem origem em A e fim em C. Sabemos que, se \theta é o ângulo formado pelos vetores \vec{X} e \vec{Y}, então \mid \vec{X} \times \vec{Y} \mid = \mid \vec{X} \mid \times \mid \vec{Y} \mid \times \sin \theta. Assim, sabemos que A, B e C são colineares se, e somente se, \theta=0^o ou \theta=180^o, logo, \sin \theta=0 e a colinearidade deles é equivalente a \mid \vec{X} \times \vec{Y} \mid = 0. Logo, basta checar se o produto vetorial de \vec{X} e \vec{Y} é zero.
  4. Os pontos médios dos segmentos \overline{P_2P_3} e \overline{P_4P_5} são coincidentes - Basta checar se \frac{P_2+P_3}{2}=\frac{P_4+P_5}{2}. Para evitar divisões e erros de precisão basta checar se P_2+P_3=P_4+P_5, ou seja, se X_{P_2}+X_{P_3}=X_{P_4}+X_{P_5} e Y_{P_2}+Y_{P_3}=Y_{P_4}+Y_{P_5}.
  5. O segmento \overline{P_2P_3} tem comprimento maior que \overline{P_4P_5} - Novamente, por questões de precisão, é melhor checar se d(P_2,P_3)^2 data-recalc-dims=d(P_4,P_5)^2" />.
  6. Os segmentos \overline{P_4P_6} e \overline{P_5P_7} são perpendiculares ao segmento \overline{P_2P_3} - Pela checagem 3, sabemos que P_4 está na reta \overleftrightarrow{P_2P_3}, logo \overline{P_4P_6} \perp \overline{P_2P_3} \Leftrightarrow \angle P_2P_4P_6 = 90^o. Assim, pelo caso particular da Leis dos Cossenos que cai no Teorema de Pitágoras, basta checarmos se d(P_2,P_4)^2+d(P_4,P_6)^2=d(P_2,P_6)^2. De maneira análoga, \overline{P_5P_7} \perp \overline{P_2P_3} \Leftrightarrow \angle P_7P_5P_3 = 90^o, logo, basta checarmos se d(P_7,P_5)^2+d(P_5,P_3)^2=d(P_3,P_7)^2.
  7. \overline{P_4P_6} e \overline{P_5P_7} têm o mesmo comprimento - Novamente, o ideal é checar se d(P_4,P_6)^2=d(P_5,P_7)^2.
  8. Os pontos P_1 e P_6 devem estar separados pela reta \overleftrightarrow{P_2P_3} - Note que isso só irá acontecer se \angle P_3P_2P_1 e \angle P_3P_2P_6 forem um côncavo e um convexo. De maneira semelhante ao check 3, o \angle ABC é convexo ou côncavo se a magnitude de (\vec{A}-\vec{B})\times (\vec{C}-\vec{B}) for positiva ou negativa, respectivamente, logo, basta checarmos se ((\vec{P_1}-\vec{P_2})\times(\vec{P_3}-\vec{P_2}))\cdot((\vec{P_3}-\vec{P_2})\times(\vec{P_6}-\vec{P_2})) < 0, 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,  b.
  • long long cross(ii a, ii b, ii c) - retorna a magnitude do produto vetorial entre b-ac-a.
  • bool col(ii a, ii b, ii c) - retorna true se os pontos abforem colineares, e false caso contrário.
  • long long sinal(long long x) - retorna 1 se x>0-1 se x<00 se x=0.

Segue o código para melhor entendimento:


// 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;
}

view raw

jardim.cpp

hosted with ❤ by GitHub

Quase primo

Solução de Carlos Vinícius

Conhecimento prévio necessário:

  1. Princípio da Inclusão-Exclusão
  2. Vetores (Aula 3)
  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 A_i o conjunto dos números menores que N que são múltiplos do primo de índice i, fornecido na entrada.

Note que queremos o valor de N-|S|, onde S=\bigcup\limits_{i=1}^K A_i. Pelo PIE, sabemos que |S|=\sum\limits_{i=1}^K (S_i \times (-1^{i+1})), onde S_i é a soma dos módulos de todos os conjuntos formados pela interseção de exatamente i dentre os conjuntos A_1, A_2,...,A_K.

Assim, basta fazer um programa que, para cada i\leq K, calcula o valor de S_i, o adicionando à resposta se i for ímpar, e subtraindo se i for par.

Para calcular o valor de S_i, seja C o conjunto das K \choose i maneiras de escolher i números de 0 a K-1. Cada número desse representará o índice de um dos K primos, que devem estar em ordem crescente. Cada conjunto de índices pode ser representado como uma sequência de i termos (os i índices). Desta maneira, haverá K \choose i conjuntos de índices C_j.

Assim, basta usarmos uma função recursiva que, assim como o knapsack, percorrerá todas as possibilidades de escolha de alguns dos N 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 N, nem precisamos testar tal possibilidade. Quando tivermos um determinado produto P, fruto da escolha de alguns primos, esse produto será divisor do piso de \frac{N}{P} números que não superam N, 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:


// 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;
}

view raw

primo.cpp

hosted with ❤ by GitHub

Falta uma

Conhecimento prévio necessário

  1. 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 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:


// 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;
}

view raw

falta.cpp

hosted with ❤ by GitHub

Ciclovias

Conhecimento prévio necessário

  1. Vetores (Aula 3)
  2. Grafos (Aula 8)

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 1: 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 v e todos os outros vértices maiores que ele já foram processados. Sejam u_0, u_1, ... u_{k-1} os k vizinhos do vértice v, em ordem crescente de índice. Agora, vamos analisar, para cada vizinho u_i, qual o maior caminho que começa em u_i e tem v como segundo vértice.

Seja max_u o maior caminho que começa em u. Como todos os vértices já processados são maiores que v, o max_u de um determinado vértice u qualquer faz referência a um caminho que tem o segundo vértice maior que v. Deste modo, partindo do vértice u_i e passando por v, posso ir para qualquer vértice u_j se, e somente se, j data-recalc-dims=i" /> (pois u_j data-recalc-dims=u_i" />, visto que estão ordenados por índice), e então poderei continuar o maior caminho que parte de u_j, pois o próximo vértice é maior que v. Logo, o maior caminho que sai de u_i, passa por v e segue por u_j tem tamanho 2+max_{u_j}, e devo atualizar o valor de max_{u_i}.

Então, em cada vértice v, devo atualizar seus vizinhos da seguinte forma: max_{u_i}=max(max_{u_i},2+max_{u_j}), para todos os valores de i e j com i<j. Entretanto, isso pode ter ma complexidade quadrática, mas resolvemos isso rapidamente ao considerarmos sufixos. Note que, para cada v, posso definir a sequência S={s_0, s_1, ..., s_{k-1}}={max_{u_0},max_{u_1},...,max_{u_{k-1}}}. Deste modo, para cada i, o tamanho do maior caminho que começa em u_i e vai para v é 2 mais o maior número do sufixo {s_{i+1}, s_{i+2}, ..., s_{k-1}} da sequência S, e podemos calcular esse valor em O(1) se pré-calcularmos, no começo do processamento do vértice v, o valor de suf_i, para todo i<k, onde suf_i=max(s_i,s_{i+1},...,s_{k-1}), e o maior caminho que começa em u_i e vai para v terá comprimento igual a 2+suf_{i+1}.

Basta aplicarmos este processamento em cada vértice e, toda vez que descubro o maior caminho de u_i que vai para v, checo se ele é maior que o maior caminho conhecido que começa em u_i, atualizando seu valor, se este for o caso. Segue o código para melhor entendimento:


// 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;
}

view raw

ciclovias.cpp

hosted with ❤ by GitHub