Comentário NOIC OBI 2016 – Fase 2 – Programação Nível 1

Comentário por Rogério Júnior

Para ver o caderno de tarefas da segunda fase da Programação Nível 1 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 << …;

Medalhas

Conhecimento prévio necessário:

1. Entrada e Saída (Aula 1)
2. Estruturas condicionais (Aula 2)

Devemos imprimir o número do atleta que terminou a prova em cada lugar. Para tal, em cada posição, basta checarmos o tempo de cada atleta e verificar se ele é quem estamos procurando. No início, vamos ler os valores da entrada e guardar nos inteiros t1, t2 e t3. Eles representarão o tempo de cada atleta, respectivamente.

Vamos checar se o primeiro atleta foi o que terminou em primeiro lugar: basta checar se o seu tempo é menor que  dos outros dois (if(t1<t2 and t1<t3)). Não precisamos nos preocupar com igualdades pois o enunciado nos diz que os tempos são, necessariamente, diferentes. Caso o primeiro atleta seja de fato o primeiro colocado, imprimimos seu número (cout << “1\n”;), e repetimos essa checagem com cada atleta.

Agora, basta repetirmos o mesmo processo para descobrirmos quem são o segundo e o terceiro lugar, mudando, logicamente, apenas a condição. O segundo lugar, por exemplo não tem o tempo menor que o dos outros dois, mas está entre os dois colocados, ou seja, se t1 é o segundo colocado, então ou t2>t1>t3 ou t3>t1>t2 (if((t2>t1 and t1>t3) or (t3>t1 and t1>t2))). Por fim, o último colocado deve ter um tempo maior que os outros dois.

Para cada posição, quando descobrimos qual atleta a ocupa, basta imprimirmos o número dele. Segue o código para melhor entendimento:

Caverna de Ordinskaya

Conhecimento prévio necessário

1. Estruturas condicionais (Aula 2)

A solução deste problema segue a ideia geral de um algoritmo guloso: basta sempre tentar construir a fita com o menor número e, caso ele seja menor que a medição anterior, uso a maior, pois só há duas possíveis em cada posição. Caso a maior também seja menor que a anterior, é impossível.

De maneira mais formal, seja $$a_i$$ o i-ésimo número da entrada e suponha que já sabemos que o valor da medição anterior ($$i-1$$) é $$s_{i-1}$$. Seja $$x_i$$ o menor entre $$a_i$$ e $$M-a_i$$ (o menor valor possível), e $$y_i$$ o maior entre $$a_i$$ e $$M-a_i$$ (o maior valor possível). Em outras palavras,  $$x_i=max(a_i,M-a_i)$$ e $$y_i=min(a_i,M-a_i)$$. Se $$y \geq s_{i-1}$$, devemos utilizá-lo, ou seja determinar que $$s_i=y_i$$, pois é o melhor que podemos fazer para minimizar o comprimento da corda. Se isto não for possível, então só nos resta utilizar o valor de $$x_i$$ ($$s_i=x_i$$). Note que, se $$x_i<s_{i-1}$$, então é impossível atribuir algum valor a $$s_i$$, pois $$s_{i-1}$$ foi construído de modo a ter o menor valor possível.

Assim, basta guardarmos a variável resp e a variável ant. No começo, resp=ant=$$0$$. Depois, usamos um for para percorrermos todas as medições. Em cada iteração i, ant será o valor de $$s_{i-1}$$, e resp  o atual comprimento da corda. Se for possível atribuir algum valor a $$s_i$$, somamos seu tamanho a resp. Caso contrário, resp=$$-1$$ e paro o loop. Não podemos esquecer de atualizar o valor de ant para $$s_i$$, para a próxima iteração do loop.

Por fim, basta imprimir o valor salvo em resp. Note que ant começa $$0$$ para que seja sempre possível usar o menor valor na primeira medição. Como a soma total pode ser, num limite bem rude, $$N \times M = 5 \times 10^9$$, usaremos long long. Segue o código para melhor entendimento:

Arco e Flecha

Conhecimento prévio necessário

1. Número de inversões no vetor (Aula 5)

Seja $$d_i$$ a distância ao quadrado da flecha $$i$$ até o centro. Note que se $$d_i > d_j$$, então a flecha $$i$$ está mais distante do centro do alvo que a flecha $$j$$. Usaremos os quadrados das distâncias para não termos que trabalhar com double, o que poderia acarretar em perda de precisão. Seja $$S={d_i, 1 \leq i \leq N}$$, ou seja, $$S$$ é a sequência formada pelas $$N$$ distâncias.

Observe agora o tiro $$i$$. Olhando para todos os tiros $$j$$ anteriores a ele ($$j<i$$), todos os que tiverem distância menor que ele do centro constituem uma penalidade (se $$d_j \leq d_i$$, há uma penalidade), ou seja, os tiros que não irão acrescentar penalidades são todos aqueles anteriores a $$j$$ que são mais distantes do centro que ele ($$d_j>d_i$$). Deste modo, cada tiro anterior a $$i$$ que não resultará em uma penalidade no tiro $$i$$ são aqueles cujo par $$(j,i)$$ é uma inversão na sequência $$S$$ ($$j<i, d_j>d_i$$).

Assim, qualquer par de tiros $$i,j$$, com $$i<j$$ será uma penalidade no momento em que o tiro $$j$$ for dado, a não ser que este par seja uma inversão na sequência. O número total de pares $$(i,j), i \neq j$$ é $$\binom{N}{2}= \frac{N \times (N-1)}{2}$$, do qual seja $$I$$ o número total de inversões em $$S$$. A penalidade total será exatamente $$\binom{N}{2} – I$$.

Para resolvermos o problema, basta usarmos um vetor v para representarmos a sequência $$S$$. Lembre-se que o quadrado da distância de um ponto à origem do plano é, simplesmente, a soma dos quadrados de suas coordenadas. Ou seja, se as coordenadas do ponto $$i$$ são $$X_i$$ e $$Y_i$$, então v[i] = $$d_i$$ = $$X_i^2+Y_i^2$$. Como as coordenadas têm módulo que pode ir até $$10^6$$, usaremos long long para guardarmos os valores do vetor v.

Por fim, basta calcularmos o número de inversões em v, de maneira exatamente igual ao que foi feito no fim da aula de ordenação, e imprimirmos a resposta. Segue o código para melhor entendimento:

Caminhos do reino

Conhecimento prévio necessário

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

Este problema envolve uma implementação minuciosa, dividida em várias etapas. Seja $$d(v,u)$$ o tamanho do caminho que sai de $$v$$ e chega em $$u$$, se existir. Para cada vértice $$v$$ do grafo, devemos calcular os valores de $$pos_v$$ e $$h_v$$. Seja $$c_v$$ a cidade do ciclo interno tal que $$d(v,c_v)$$ é mínimo. Se $$v$$ está no ciclo, $$c_v=v$$. Defina $$h_v$$ como $$d(v,c_v)$$.

O ciclo tem um pai, que é um vértice $$u$$ qualquer pertencente ao ciclo. Se $$k$$ é um vértice qualquer do ciclo, defina $$pos_k$$ como $$d(u,k)$$. Note que $$pos_u=0$$. Agora, para qualquer vértice $$v$$, defina $$pos_v=pos_{c_v}$$.

Agora que já definimos esses valores, calcular o menor tempo de encontro entre duas pessoas nos vértices $$v$$ e $$u$$ do grafo é bem simples. Se ambos os vértices estiverem no mesmo caminho periférico, ou seja, $$c_v=c_u$$, a distância entre eles é $$\mid h_v-h_u \mid$$, pois basta que a pessoa na cidade de maior “profundidade” caminhe até chegar na cidade mais próxima do ciclo.

Entretanto, se os vértices estiverem em caminhos periféricos diferentes, a conta é ligeiramente mais complicada. Primeiramente, note que os dois vão, necessariamente, se encontrar em algum vértice do ciclo. Quando um dos dois chega no ciclo, não vale a pena que os dois se movam nele, pois qualquer movimento de um distancia-se do outro, visto que só podem andar em uma direção, logo um dos dois, digamos $$v$$, não se movimentará no ciclo e o ideal será que se encontrem no vértice $$c_v$$.

De maneira mais formal, suponha que o vértice ideal de encontro é $$k$$ diferente de $$c_v$$ e $$c_u$$. Sem perda de generalidade, digamos que $$d(c_v,k)<d(c_u,k)$$. Neste caso, como o ciclo só tem um sentido, o caminho do $$c_u$$ a $$k$$ necessariamente passa pelo vértice $$c_v$$, sendo melhor que ambos se encontrassem, portanto, em $$c_v$$.

Sabendo agora que o ponto de encontro será $$c_v$$ ou $$c_u$$, basta calcularmos qual dos pontos de encontro é a resposta. Seja $$d_v$$ o tempo em que as pessoas no vértice $$v$$ e $$u$$ se encontram em $$c_v$$. Note que $$d_v=max(d(v,c_v),d(u,c_v))$$, pois veremos quanto tempo cada um demora para chegar em $$c_v$$ e a resposta será o maior deles (o que chega mais rápido espera o outro). Sabemos que $$d(v,c_v)=h_v$$, restando-nos calcular o valor de $$d(u,c_v)$$. Para chegar de $$u$$ a $$c_v$$, primeiro temos que chegar ao ciclo, ou seja chegar em $$c_u$$, e sabemos que $$d(u,c_u)=h_u$$. Feito isso, basta calcularmos o valor de $$d(c_u,c_v)$$, pois sabemos que $$d(u,c_v)=d(u,c_u)+d(c_u,c_v)$$. Se $$pos_{c_v}>pos_{c_u}$$, então $$d(c_u,c_v)=pos_{c_v}-pos_{c_u}$$. No entanto, se $$pos_{c_v}<pos_{c_u}$$, $$d(c_u,c_v)=(pos_{c_v}-pos_{c_u}) \mod m$$, onde $$m$$ é o tamanho do ciclo interno. De qualquer modo, $$d(c_u,c_v)=(pos_{c_v}-pos_{c_u}) \mod m$$. Assim,$$d_v=max(h_v,h_u+((pos_{c_v}-pos_{c_u}) \mod m)$$. De maneira análoga, $$d_u=max(h_u,h_v+((pos_{c_u}-pos_{c_v}) \mod m)$$.

Deste modo, o menor tempo para que pessoas nos vértices $$u$$ e $$v$$ se encontrem é $$min(d_v,d_u)$$. Note que parto do princípio de que $$a \mod b$$ sempre é positivo, ou seja, se $$a>0$$, $$-a \mod b = b-a$$. Agora, basta implementarmos um código que calcule os valores de $$h_v$$ e $$pos_v$$ para todo vértice $$v$$ do grafo.

Primeiramente, vamos identificar todos os vértices que estão no ciclo e guardá-los no vector cycle. Para isso, vamos salvar as arestas em dois grafos: um original, em que son[v] guarda o destino da aresta que sai de v, e um grafo inverso, em que o  vector invers[v] guarda todos os vértices cujas arestas chegam em v.

Agora, para encontrar um cara no ciclo, basta percorrer todos os vértices, procurando por um com grau de entrada maior que $$1$$, ou seja invers[v].size()>1. Quando o encontramos, basta seguirmos o caminho que começa nele no grafo normal, adicionando todos os vértices que passaremos ao ciclo, até que voltemos a v, e então paramos.

Agora, para cada vértice do ciclo, vamos chamar uma DFS no grafo inverso, que irá calcular os valores de h[v] e pos[v] para todos os vértices do grafo. Para o vértice v no ciclo, h[v] já começa $$0$$ e pos[v] será sua posição em cycle.

Agora, suponha que chamamos a DFS para um vértice v qualquer. Para cada vizinho seu u, se ele não estiver no ciclo, o valor de pos[u] será o mesmo de pos[v], pois eles chegam ao mesmo vértice do ciclo, e como o caminho de u a esse vértice consiste em ir de u até v e então ao vértice, temos que h[u]=h[v]+1. Agora que já calculamos esses valores para u, podemos chamar dfs(u).

Depois de chamada a DFS para todos os vértices do ciclo, já teremos os valores de h e pos para qualquer vertice do grafo, logo, basta ler cada uma das perguntas e respondê-las com as fórmulas calculadas anteriormente. Segue o código para melhor entendimento: