Soluções da prova de seleção da VTX

seletiva_vtx_sol

Bolei a prova para que fosse feita em média por bons candidatos nos seguintes tempos:
+-----------------------------------------------------------------+
| QUESTÕES  | TEMPO (min)      |   TIPO                           | 
+-----------------------------------------------------------------+
| 1,2       |      30 min      |   Lógica                         |
| 3,5       |      60 min      |   Programação                    |
| 4,6       |      30 min      |   Leitura e Simulação de código  |
| 7         |      ------      |   Confiança nas respostas        |
+-----------------------------------------------------------------+
O intuito era que as questões 1,2,6 fossem fáceis e fossem feitas rápido (nos primeiros 30-40min).
A questão 4 também deveria ser feita rápido, já que o esforço estava apenas em compreender um código não muito extenso.
Assim, idealmente, sobraria 1 hora para 2 questões de programação, um tempo razoável.

1) 
A resposta é {2,2,9}.
Basta você listar todas as triplas de números inteiros cujo produto é igual a 36. 
Dessas triplas, apenas duas tem somas iguais: { {1,6,6}, {2,2,9} }. 
Mas é dito que há uma irmã mais velha, portanto a solução é única e é {2,2,9}.

Fonte: 
http://www.amazon.com/The-Art-Craft-Problem-Solving/dp/0471789011/ref=sr_1_1?ie=UTF8&qid=1365098218&sr=8-1&keywords=art+and+craft+of+problem+solving

2) 
É possível sim. 
Um modo fácil de se resolver o problema (para quem tem pouca imaginaçã) é simplificar o problema:
 A B C
 + + +
 | | |
 + + +
 A B C
Dai, é só arrastar as caixas de modo que a configuração simplificada fique igual à configuração original [A,B,C -> C,B,A].

Fonte: http://www.amazon.com/The-Art-Craft-Problem-Solving/dp/0471789011/ref=sr_1_1?ie=UTF8&qid=1365098218&sr=8-1&keywords=art+and+craft+of+problem+solving

3) 
Uma solução possível é o bubble-sort. O número mínimo de ultrapassagens é a quantidade de swaps realizadas pelo bubble-sort.
Obviamente o array não é ordenado em relação aos valores dos carros, mas em relação aos índices de chegada e saída.

Fonte: http://maratona.ime.usp.br/prim-fase2012/maratona.pdf (questão mais fácil da prova)

4) 
Considerei como corretas pessoas que acusaram erros em tempo de execução, nomeadamente o lançamento da exceção IndexOutOfBounds para certos valores de m, como m = 1.
(Erro em programação)

Isso foi erro meu ao formular a questão.
A resposta que eu tinha em mente era:
1
5
10 9 5 3 3
Seria impresso
2
Quando a resposta correta é 0, pois a primeira pessoas poderia receber as moedas {10,5} e a outra pessoa: {9,3,3}
(Um erro de algoritmo, não de programação)

5) 
Solução 1
---------
Calcular todas as somas possíveis e ir sempre guardando a maior.
Naturalmente, isso seria feito utilizando 2 loops (similar ao bubble-sort)
SOMAS DE POSSÍVEIS DO CONJUNTO {A,B,C}:
{A,B,C}, {A,B}, {B,C}, {A,C}, {A}, {B}, {C}

Solução 2
---------
Bastava observar que não é necessário computar todas as somas.
Efetivamente, a maior soma até o índice i pode ser calculada a partir da soma até o índice anterior:
s[i] = max {s[i-1] + a[i], a[i] }
Veja:
3 -2 1 4

i | S
-----
0 | 3
1 | 3
2 | 3
3 | 5
A maior soma é 5.

6) 
O código simplesmente imprimia o prontuário digitado e imprimia também esse prontuário com o primeiro dígito na última posição.
Logo, se a entrada foi: 123456 a saída será 123456 e 234561.