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:
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:
| // Medalhas – F2PJ – OBI 2016 | |
| // Rogério Júnior | |
| // Complexidade: O(1) | |
| #include "iostream" | |
| using namespace std; | |
| int main(){ | |
| int t1, t2, t3; | |
| cin >> t1 >> t2 >> t3; | |
| // vou descobrir quem é o primeiro colocado: | |
| if(t1<t2 and t1<t3){ // se for o atleta 1, imprimo 1 | |
| cout << "1\n"; | |
| } | |
| if(t2<t1 and t2<t3){ // se for o atleta 2, imprimo 2 | |
| cout << "2\n"; | |
| } | |
| if(t3<t1 and t3<t2){ // se for o atleta 3, imprimo 3 | |
| cout << "3\n"; | |
| } | |
| // agora, vou descobrir quem é o segundo colocado | |
| // nessa pate, devemos ter muito cuidado em colocar os parêntesis | |
| // pois temos vária condições dentro de um mesmo "if" | |
| // os parêntesis devem separar corretamente as condições | |
| // para que o coputador saiba dar a prioridade desejada ao "and" e ao "or" | |
| if((t2>t1 and t1>t3) or (t3>t1 and t1>t2)){ // se for o atleta 1, imprimo 1 | |
| cout << "1\n"; | |
| } | |
| if((t1>t2 and t2>t3) or (t3>t2 and t2>t1)){ // se for o atleta 2, imprimo 2 | |
| cout << "2\n"; | |
| } | |
| if((t1>t3 and t3>t2) or (t2>t3 and t3>t1)){ // se for o atleta 3, imprimo 3 | |
| cout << "3\n"; | |
| } | |
| // por fim, basta descobrir quem é o terceiro | |
| if(t1>t2 and t1>t3){ // se for o atleta 1, imprimo 1 | |
| cout << "1\n"; | |
| } | |
| if(t2>t1 and t2>t3){ // se for o atleta 2, imprimo 2 | |
| cout << "2\n"; | |
| } | |
| if(t3>t1 and t3>t2){ // se for o atleta 3, imprimo 3 | |
| cout << "3\n"; | |
| } | |
| return 0; | |
| } |
Caverna de Ordinskaya
Conhecimento prévio necessário
- 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:
| // Caverna de Ordinskaya – F2PJ – OBI 2016 | |
| // Rogério Júnior | |
| // Complexidade: O(N) | |
| #include "iostream" | |
| #include "algorithm" // min e max | |
| using namespace std; | |
| int main(){ | |
| // declaro as variávei que vou usar | |
| long long n, m, resp=0, ant=0; | |
| // leio os valores de N e M | |
| cin >> n >> m; | |
| // para cada medição feita | |
| for(int i=0;i<n;i++){ | |
| // leio o valor medido | |
| long long a; | |
| cin >> a; | |
| // x é o maior valor possível e y o menor | |
| long long x=max(a,m-a), y=min(a,m-a); | |
| // se possível, uso y | |
| if(y>=ant){ | |
| resp+=y; // adiciono y ao comprimento total | |
| ant=y; // e atualizo o valor de ant | |
| } | |
| // se não, uso x | |
| if(y<ant and x>=ant){ | |
| resp+=x; // adiciono x ao comprimento total | |
| ant=x; // e atualizo o valor de ant | |
| } | |
| // se nem x for possível, é impossível | |
| if(x<ant){ | |
| resp=-1; // a respsota será -1 | |
| break; // e dou um break no loop | |
| } | |
| } | |
| // por fim, imprimo a resposta | |
| cout << resp << "\n"; | |
| // e retorno zero | |
| return 0; | |
| } |
Arco e Flecha
Conhecimento prévio necessário
- 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:
| // Arco e Flecha – F2P1 – OBI 2016 | |
| // Rogério Júnior | |
| // Complexidade: O(N log N) | |
| #include "iostream" | |
| #include "algorithm" | |
| using namespace std; | |
| #define MAXN 100100 | |
| // defino o tipo ll como long long | |
| typedef long long ll; | |
| // vetores da função merge_sort | |
| ll aux[MAXN], v[MAXN]; | |
| ll merge_sort(int ini, int fim){ // declaro a função merge_sort, que agora retorna um ll | |
| if(ini==fim) return 0; // se o intervalo tiver um único elemento, ele não tem inversões | |
| // caso o contrário, declaro a variável invers, que começa com a soma das inversões das duas metades | |
| ll invers=merge_sort(ini, (ini+fim)/2) + merge_sort((ini+fim)/2+1, fim); // observe que chamei a recursão e ordenei as metades | |
| int tam=0, j=(ini+fim)/2+1; // declaro tam e j, como feito no código anterior do merge_sort | |
| for(int i=ini; i<=(ini+fim)/2; i++){ // para cada posição da metade da esquerda | |
| while(j<=fim && v[j]<v[i]){ // procuro os elementos da metade da direita menores que i | |
| // os adiciono ao vetor aux | |
| aux[tam]=v[j]; | |
| tam++; | |
| j++; // passo para o próximo elemento | |
| invers+=(ini+fim)/2-i+1; // e adicino o número de inversões em metades diferentes com o elemento j | |
| } | |
| // adiciono o elemento i | |
| aux[tam]=v[i]; | |
| tam++; | |
| } | |
| // adiciono o resto dos elementosda segunda metade | |
| while(j<=fim){ | |
| aux[tam]=v[j]; | |
| tam++; | |
| j++; | |
| } | |
| for(int i=ini; i<=fim; i++) v[i]=aux[i-ini]; // e troco os valores do vetor original pelos ordenados | |
| return invers; // retorno o número de inversões calculado | |
| } | |
| int main(){ | |
| // declaro e leio o valor de n | |
| ll n; | |
| cin >> n; | |
| // para cada flecha | |
| for(int i=1;i<=n;i++){ | |
| // leio suas coordenadas | |
| ll x, y; | |
| cin >> x >> y; | |
| // e guardo, em v, o quadrado de sua distância ao centro | |
| v[i]=x*x+y*y; | |
| } | |
| // por fim, imprimo a resposta, | |
| // o número de pares em v menos o número de inversões | |
| cout << (n*(n-1)/2) – merge_sort(1,n) << "\n"; | |
| // e retorno zero | |
| return 0; | |
| } |
Caminhos do reino
Conhecimento prévio necessário
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:
| // Caminhos do Reino – F2P1 – OBI 2016 | |
| // Rogério Júnior | |
| // Complexidade: O(N+Q) | |
| #include "iostream" | |
| #include "algorithm" | |
| #include "vector" | |
| using namespace std; | |
| #define PB push_back | |
| #define MAXN 100100 | |
| int n, q, v, son[MAXN], pos[MAXN], h[MAXN]; | |
| bool in_cyc[MAXN]; | |
| vector<int> invers[MAXN], cycle; | |
| // função para calcular a distância no ciclo | |
| int mod(int x){ | |
| // se x for negativo | |
| // tenho q dar a volta pelo "outro lado" | |
| if(x<0) x+=cycle.size(); | |
| // e retorno x | |
| return x; | |
| } | |
| // DFS que calcula o "pai" do vértice no ciclo | |
| // e sua distância dele | |
| void dfs(int v){ | |
| // para cada filho de v no grafo inverso | |
| for(int i=0;i<invers[v].size();i++){ | |
| int u=invers[v][i]; | |
| // se ele já estiver no ciclo, ignoro | |
| if(in_cyc[u]) continue; | |
| // se não, ele recebe a posição de v | |
| pos[u]=pos[v]; | |
| // e sua profundidade mais um | |
| h[u]=h[v]+1; | |
| // e chamo a DFS nele | |
| dfs(u); | |
| } | |
| } | |
| int main(){ | |
| // leio o valor de N | |
| cin >> n; | |
| // leio cada aresta | |
| for(int v=1;v<=n;v++){ | |
| int u; | |
| cin >> u; | |
| // a salvo no grafo direto | |
| son[v]=u; | |
| // e no grafo inverso | |
| invers[u].PB(v); | |
| } | |
| // percorro os vértices procurando algum no ciclo | |
| for(int v=1;v<=n;v++){ | |
| // se ele tem grau maior que um no cico inverso | |
| // há dois caminhos que chegam nele, logo ele está no ciclo | |
| if(invers[v].size()>1){ | |
| // o adiciono ao ciclo | |
| cycle.PB(v); | |
| in_cyc[v]=true; | |
| // e sigo seu caminho de filhos até completar todo o ciclo | |
| int u=son[v]; | |
| while(u!=v){ | |
| // marco que o cada vértice está no ciclo | |
| in_cyc[u]=true; | |
| // o adiciono no vetor cycle | |
| cycle.PB(u); | |
| // e olho o seu filho | |
| u=son[u]; | |
| } | |
| // quando encontro o ciclo, posso parar o for | |
| break; | |
| } | |
| } | |
| // para cada vértice no ciclo | |
| for(int i=0;i<cycle.size();i++){ | |
| int v=cycle[i]; | |
| // salvo sua posição no ciclo | |
| pos[v]=i; | |
| // e salvo a altura e posição no ciclo | |
| // de cada vértice do caminho que sai dele | |
| dfs(v); | |
| } | |
| // leio o valor de Q | |
| cin >> q; | |
| for(int i=0;i<q;i++){ | |
| // leio os vértices da pergunta | |
| int a, b; | |
| cin >> a >> b; | |
| // se os dois estão no mesmo caminho periférico | |
| // basta imprimir a diferença entre suas alturas | |
| if(pos[a]==pos[b]) cout << max(h[a]-h[b],h[b]-h[a]) <<" \n"; | |
| // se não | |
| else{ | |
| // calculo o tempo para que se encontrem no pai de A e de B | |
| int da, db; | |
| da=max(h[a],h[b]+mod(pos[a]-pos[b])); | |
| db=max(h[b],h[a]+mod(pos[b]-pos[a])); | |
| // e imprimo o menor deles | |
| cout << min(da,db) << "\n"; | |
| } | |
| } | |
| // por fim, retorno zero | |
| return 0; | |
| } |
