Nível 2 - Fase 2

0 Flares Facebook 0 0 Flares ×

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:

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

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:

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:

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>i (pois u_j>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:

 

 

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: