Difference between revisions of "Problema do tesouro real"
(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]. | |
== 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 | + | 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.
Contents
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}.