Difference between revisions of "Problema do colecionador de moedas"

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
Line 1: Line 1:
== Dificuldade Única ==
 
 
  Problema adaptado de http://www.topcoder.com/stat?c=problem_statement&pm=9933&rd=13506
 
  Problema adaptado de http://www.topcoder.com/stat?c=problem_statement&pm=9933&rd=13506
 
+
== Dificuldade Única ==
 
Um colecionador de moedas tem o objetivo de colecionar o maior número possível de moedas diferentes (qualida ou valor não são importantes).
 
Um colecionador de moedas tem o objetivo de colecionar o maior número possível de moedas diferentes (qualida ou valor não são importantes).
  
Faça um programa que recebendo um vetor V com o valor das moedas e um vetor C com as moedas que o colecionar possui informe qual o número máximo de moedas diferentes que o colecionador pode conseguir.
+
Faça um programa que, recebendo um vetor V com o valor das moedas e um vetor C com as moedas que o colecionar possui, informe qual o número máximo de moedas diferentes que o colecionador pode conseguir.
 +
 
 +
Considere que o colecionador só consegue dinheiro para compra outras moedas se vender as moedas que possui.
 +
 
 +
A entrada do vetor V será dada da seguinte forma:
 +
*Uma primeira linha com um Nv inteiro (1<=Nv<=100) identificando a quantidade de elementos de V.
 +
*Nv linhas com números inteiros Kv (1<=Kv<=50). Cada elemento Kv representará o valor de mercado de cada moeda cujo nome é a posição de K a partir do zero (veja exemplo).
 +
 
 +
A entrada do vetor C se dará logo após à entrada do vetor V e será da seguinte forma:
 +
*Uma primeira linha com um Nc inteiro (1<=Nc<=Nv).
 +
*Nc linhas com números inteiros Kc (0<=Kc<=Nv-1). Cada elemento Kc representará o nome de uma moeda que o colecionador possui.
  
Considere que só é possível conseguir dinheiro para compra vendendo as moedas que possui.
 
  
 
=== Exemplo ===
 
=== Exemplo ===
 
==== Entrada ====
 
==== Entrada ====
  Vetor V
+
  5
  9 (o valor da moeda "0" é $9)
+
  9  
  4 (o valor da moeda "1" é $4)
+
  4
  7 (o valor da moeda "2" é $7)
+
  7
  8 (o valor da moeda "3" é $8)
+
  8
  17 (o valor da moeda "4" é $17)
+
  17
 
+
  2
  Vetor C
+
 
  4
 
  4
 
  0
 
  0
  
(O colecionador possui a moeda "0" e "4", que custam respectivamente $9 e $17 conforme consta no vetor V).
+
Neste exemplo:
 +
*Nv=5.
 +
*Nc=2.
 +
*Conforme o vetor V, o valor da moeda "0" é $9, da moeda "1" é $4, da moeda "2" é $7, da moeda "3" é $8, da moeda "4" é $17.
 +
*Conforme o vetor C, o colecionador possui a moeda "0" e "4", que custam respectivamente $9 e $17 conforme consta no vetor V.
  
=== Saída ===
+
==== Saída ====
 
  3
 
  3

Revision as of 00:40, 5 May 2009

Problema adaptado de http://www.topcoder.com/stat?c=problem_statement&pm=9933&rd=13506

Dificuldade Única

Um colecionador de moedas tem o objetivo de colecionar o maior número possível de moedas diferentes (qualida ou valor não são importantes).

Faça um programa que, recebendo um vetor V com o valor das moedas e um vetor C com as moedas que o colecionar possui, informe qual o número máximo de moedas diferentes que o colecionador pode conseguir.

Considere que o colecionador só consegue dinheiro para compra outras moedas se vender as moedas que possui.

A entrada do vetor V será dada da seguinte forma:

  • Uma primeira linha com um Nv inteiro (1<=Nv<=100) identificando a quantidade de elementos de V.
  • Nv linhas com números inteiros Kv (1<=Kv<=50). Cada elemento Kv representará o valor de mercado de cada moeda cujo nome é a posição de K a partir do zero (veja exemplo).

A entrada do vetor C se dará logo após à entrada do vetor V e será da seguinte forma:

  • Uma primeira linha com um Nc inteiro (1<=Nc<=Nv).
  • Nc linhas com números inteiros Kc (0<=Kc<=Nv-1). Cada elemento Kc representará o nome de uma moeda que o colecionador possui.


Exemplo

Entrada

5
9 
4
7
8
17
2
4
0

Neste exemplo:

  • Nv=5.
  • Nc=2.
  • Conforme o vetor V, o valor da moeda "0" é $9, da moeda "1" é $4, da moeda "2" é $7, da moeda "3" é $8, da moeda "4" é $17.
  • Conforme o vetor C, o colecionador possui a moeda "0" e "4", que custam respectivamente $9 e $17 conforme consta no vetor V.

Saída

3