Difference between revisions of "Problema do tesouro real"

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
(New page: Problema adaptado de RoyalTreasurer do [http://www.topcoder.com/stat?c=problem_statement&pm=10007&rd=13695 TopCoder]. == Dificuldade única == Era uma vez um reino onde a matemática era...)
 
(Dificuldade única)
 
Line 1: Line 1:
Problema adaptado de RoyalTreasurer do [http://www.topcoder.com/stat?c=problem_statement&pm=10007&rd=13695 TopCoder].
+
Problema adaptado de RoyalTreasurer do [http://www.topcoder.com/stat?c=problem_statement&pm=10007&rd=13695 TopCoder].
  
 
== Dificuldade única ==
 
== Dificuldade única ==
Line 7: Line 7:
 
  S=A<sub>0</sub>*B<sub>0</sub>+A<sub>1</sub>*B<sub>1</sub>+...+A<sub>n</sub>*B<sub>n</sub>
 
  S=A<sub>0</sub>*B<sub>0</sub>+A<sub>1</sub>*B<sub>1</sub>+...+A<sub>n</sub>*B<sub>n</sub>
  
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.
+
O reino precisa de um programa para conferir as respostas, 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 ===
 
=== Exemplo 1 ===

Latest revision as of 13:07, 15 July 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 respostas, 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}.