Difference between revisions of "Problema do tesouro real"

Revision as of 13:06, 25 February 2009

Problema adaptado de RoyalTreasurer do TopCoder.

Dificuldade única

Era uma vez um reino onde a matemática era um grande problema. Quando um posto para trabalhar nas finanças reais necessitava ser preenchido apresentava-se aos candidatos o seguinte problema:

Dado dois vetores de inteiros positivos A e B com N elementos e a função S abaixo, reordene os números em A de forma que o valor de S seja o menor possível. Não é permitido mudar a ordem dos elementos de B:

S=A0*B0+A1*B1+...+An*Bn

O reino precisa de um programa para conferir as resposas, assim, pede-se um programa que dado um N (2<=N<=100), um vetor A e um vetor B (com N elementos dentro do limite fechado de 1 e 1000) seja capaz de retornar o menor valor possível de S.

Exemplo 1

Entrada

3
1
10
8
7
56
13

Saída

230

Possível resposta: A={10,1,8}.

Exemplo 2

Entrada

5
12
3
53
8
91
74
2
3
4
64

Saída

1123

Possível resposta: A={3,91,53,12,8}.

Exemplo 3

Entrada

5
1
1
1
6
0
2
7
8
3
1

Saída

18

Possível resposta: A={1,1,0,1,6}.

Exemplo 4

Entrada

9
5
15
100
31
39
0
0
3
26
11
12
13
2
3
4
5
9
1

Saída

528

Possível resposta: A={3,0,0,39,31,26,15,5,100}.