Difference between revisions of "Problema do colecionador de moedas"
From AdonaiMedrado.Pro.Br
| Line 1: | Line 1: | ||
| − | |||
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. | ||
| − | |||
=== Exemplo === | === Exemplo === | ||
==== Entrada ==== | ==== Entrada ==== | ||
| − | + | 5 | |
| − | 9 | + | 9 |
| − | 4 | + | 4 |
| − | 7 | + | 7 |
| − | 8 | + | 8 |
| − | 17 | + | 17 |
| − | + | 2 | |
| − | + | ||
4 | 4 | ||
0 | 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 === | + | ==== 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
