Comentário por Anita Almeida
Para conferir a prova na íntegra, clique aqui.
Pares de Números
Conhecimento prévio necessário:
Utilizamos as três variáveis $$N, I$$ e $$F$$ para ler a entrada, $$R$$ para ser o resultado final (saída), $$S$$ como a soma de um par de números, $$n1$$ como o primeiro número de um par de números escolhidos, $$n2$$ o segundo número desse mesmo par de números escolhidos e $$MAXN$$ como o tamanho do vetor $$V[]$$.
Para comparar todos os pares que podem ser formados com a sequência de números de entrada utilizamos dois loops a partir do comando $$for()$$ e uma estrutura condicional a partir do comando $$if()$$. A comparação pode ser explicada pelo seguinte exemplo: em uma sequência de termos $$A, B, C$$ e $$D$$, o programa inicialmente declara $$A$$ como $$n1$$ e $$B$$ como $$n2$$ e caso a soma $$S$$ deles siga as restrições, soma-se 1 ao resultado final $$R$$. Depois acontece o mesmo com os pares $$(A,C)$$ e $$(A,D)$$, apenas alterando $$n2$$ para $$C$$ e posteriormente para $$D$$. Em seguida, é o $$n1$$ que é alterado para $$B$$ para comparar os pares $$(B,C)$$ e $$(B,D)$$, alterando $$n2$$ então para $$C$$ e $$D$$. Por último, $$n1$$ vira $$C$$ e é comparado o par $$(C,D)$$, sendo $$n2$$ equivalente a $$D$$. E assim por diante caso existissem mais números nessa sequência.
Complexidade: $$O(N)$$
Segue o código comentado para melhor compreensão da solução:
https://gist.github.com/anitainfo/0de994c5149ba7313d32a0d1ddcf1806
Parcelamento sem Juros
Conhecimento prévio necessário:
Utilizamos as duas variáveis $$V$$ e $$P$$ para ler a entrada, $$quo$$ como o quociente da divisão de $$V$$ por $$P$$ ($$V/P$$), $$resto$$ como o resto da divisão de $$V$$ por $$P$$ ($$V$$%$$P$$) e $$cont$$ como uma variável auxiliar para os loops responsáveis por imprimir os resultados
Para determinar quantas parcelas devem ser alteradas, ou seja, em quais deve ser adicionada uma parte do resto da divisão de $$V$$ por $$P$$ ou não, utilizamos dois loops a partir do comando $$for()$$ e da variável $$cont$$. O número de parcelas que devem ser alteradas é equivalente ao $$resto$$, então o primeiro loop imprimi $$quo+1$$ (parcela + resto) até $$cont=resto$$. O segundo loop imprimi $$quo$$ (parcela normal) nas demais parcelas até $$cont=P – resto$$ (ou $$P – $$ número de parcelas alteradas).
Complexidade: $$O(P)$$
Segue o código comentado para melhor compreensão da solução:
https://gist.github.com/anitainfo/f9b6c5e67b233111917a6a6f71632e40
Manchas de Pele
Conhecimento prévio necessário:
Utilizamos as variáveis $$N$$ e $$M$$ para ler a primeira linha de entrada, as variáveis $$i$$ $$j$$ como variáveis auxiliares que irão dizer em qual pixel estamos (por exemplo o último pixel é o $$pixel[8][9]$$), o vetor de vetores $$pixel[i][j]$$ para salvar todos os demais números de entrada (1 ou 0) que correspondem aos pixels, a variável $$manchas$$ para contabilizar o número de manchas, os vetores auxiliares $$va$$ e $$vb$$ para ajudar a checar todos os vizinhos de um pixel a partir de suas coordenadas, $$k$$, $$newa$$ e $$newb$$ como variáveis auxiliares para checar os 4 vizinhos de um pixel (cima,baixo,dir,esq) e montar um novo par de coordenadas caso um deles não tenha sido checado, uma fila para checar os pixels e seus vizinhos um a um, um bool de um vetor de vetores $$visit[i][j]$$ que determina se um pixel já foi analisado ou não e as variáveis $$MAXN$$ e $$MAXM$$ para definir o tamanho do vetor de algumas variáveis no início.
A ideia nesse problema é montar um $$grafo$$ a partir da imagem de números 0 ou 1 que é dada. Iniciamos lendo o tamanho dessa imagem pelo $$N$$ e $$M$$, depois lemos todos os pixels por dois loops do comando $$for()$$ que comandam as coordenas desse pixel e, novamente com dois loops do comando $$for()$$ que comandam as coordenadas desse pixel e com uma condição pelo comando $$if()$$, checamos se esse pixel ainda não foi analisado, mas faz parte de uma mancha. Se essa condição for satisfeita, soma-se 1 no resultado final $$manchas$$ e vamos para a $$void BFS()$$, de acordo com o par de coordenadas do pixel que estamos vendo i e j, para analisar seus vizinhos atravessando todo o grafo.
Na $$void BFS()$$, adicionamos os par de coordenadas no topo na fila e ficamos em loop enquanto essa fila não estiver vazia, comando !$$fila.empty()$$, atribuímos o valor do $$i$$ ao $$a$$ e o valor do $$j$$ ao $$b$$ e apagamos o par da fila (que já está salvo nas variáveis citadas). Em seguida começamos a checar seus 4 vizinhos (cima,baixo,dir,esq) a partir dos vetores auxiliares $$va$$ e $$vb$$ que possuem valores pré-definidos, que serão somados ao $$a$$ e ao $$b$$ formando novas variávies ($$newa$$ e $$newb$$). Por fim, temos a condição de que se esse pixel vizinho ainda não foi analisado e é um pedaço de mancha (ou seja, 1), ele é definido com já analisado no vetor de vetores $$visit[i][j]$$ (=true) e é adicionado na fila para checar os seus vizinhos também para agilizar o processo de verificação.
Complexidade: $$O(N*M)$$
Segue o código comentado para melhor compreensão da solução:
https://gist.github.com/anitainfo/17a2b425101b31ef569f58621d6dba1b