Comentário por Thiago Mota
Para conferir a prova na íntegra, clique aqui.
Calçada Imperial
Conhecimento prévio necessário:
Vamos escolher dois valores arbitrários no vetor, como por exemplo os valores $$2$$ e $$10$$ no caso da imagem fornecido pela prova. Para descobrir a resposta para esses dois valores basta pecorrer e vetor e sempre que acharmos o valor $$2$$ ou o valor $$10$$ checaremos se ele foi colocado como último, se ele foi então teremos que ignorá-lo, caso não seja o último adicionaremos ele a resposta. Isso pode ser feito em $$O(N)$$.
Como o $$N$$ só vai até $$500$$ podemos fazer um algoritmo em uma complexidade de $$O(N^3)$$, logo podemos testar para cada par de valores possíveis e fazer o algoritmo descrito acima para obter a melhor respota, segue o código:
https://gist.github.com/Thiago4532/a6217a82c3a4ff89cd95d3c27686c1bb
A idade da Dona Mônica
Conhecimento prévio necessário:
Diremos que $$A$$, $$B$$ e $$C$$ são as idades dos $$3$$ filhos de Dona Mônica. Como $$A + B + C = M$$ temos que $$C = M – A – B$$, logo conseguimos facilmente calcular a idade do terceiro filho, com isso basta utilizar IF para descobrir qual é o mais velho. Segue o código:
NÃO ESQUECER DO CASO EM QUE OS FILHOS TEM IDADES IGUAIS.
https://gist.github.com/Thiago4532/1302d89eb74bb74ded594ccc92217bd4
Soma
Conhecimento prévio necessário:
Para resolver este problema usaremos as funções lower_bound() e upper_bound() do C++, caso você não conheça essas funções é recomendado você acessar esse link, mas não é necessário para a resolução do problema, apenas será utilizada no código.
A solução consiste em montar o vetor de prefixos do dado pela questão, o vetor de prefixos é basicamente um vetor $$pref$$ que é definido da seguinte forma: $$pref(i) = pref(i-1) + v(i)$$, ou seja, o valor na posição $$pref(x)$$ é na verdade a soma acumulada de todos os valores de $$1$$ até $$x$$ no vetor original. Por exemplo, para o vetor $$v = [1, 3, 4, 5, 8, 9]$$, $$pref = [1, 4, 8, 13, 21, 30]$$, com isso conseguimos calcular a soma de um intervalo $$[l, r]$$ fazendo $$pref(r) – pref(l-1)$$.
Solução em $$O(n^2)$$: Podemos olhar para cada posição $$i$$ do vetor e procurar quantos caras nesse vetor começando na posição $$i$$ soma vai ser $$k$$, no final basta somar as respostas para cada cara.
Solução em $$O(n \log n)$$: Utilizando a mesma ideia da solução anterior, podemos notar que o vetor de prefixo apenas cresce ou permanece do mesmo tamanho já que não temos valores negativos, logo para cada cara podemos fazer uma busca binária procurando em que posição $$x$$ a soma de $$i$$ até $$x$$ a soma seja $$k$$. Como temos valores $$0$$ temos que ter cuidado pois vai existir valores repetidos no prefixo, para isso basta procurar o primeiro cara que a soma da $$k$$ e o último cara que a soma da $$k$$, a resposta começando em $$i$$ vai ser o número de elementos no intervalo do último menos o primeiro.
Iremos utilizar upper_bound() e lower_bound() no vetor de prefixos para acharmos o maior e o menor cara. Não esqueça do long long.
https://gist.github.com/Thiago4532/be2f6db80d1c6a82410b03e1767aa378
Chuva
Conhecimento prévio necessário:
A solução é uma aplicação clara de DFS, basta apenas chamar uma função $$dfs(i, j)$$ sendo $$(i, j)$$ a gota na primeira linha, com isso basta expandir as gotas para os locais permitidos utilizando as condições dada pelo próprio enunciado. Segue o código para melhor entendimento:
https://gist.github.com/Thiago4532/24f9daf77d1902d71f1b0d8708cd8764