Minimálny počet mincí pri rozmieňaní sumy (c++)

Created: 2008-11-10 - 22:24

Mince

Úloha

Predstavte si, že žijete v krajine, v ktorej sa používa n typov mincí s nominálnymi hodnotami a1,a2...an. Nám blízkym príkladom je n=11 a hodnoty 1,2,5,10,20,50,100,200,500,1000,5000.
Akým minimálnym počtom mincí vieme v takejto mene zaplatiť hodnotu M ?

Vstup

Prvý riadok vstupu obsajuje jedno kladné celé číslo P, určujúce počet testovacích sád.
  • Prvý riadok testovacej sady obsahuje číslo n, (1≤n≤50).
  • Druhý riadok obsahuje n medzerou oddelených prirodzených čísel, určujúcich nominálne hodnotych jednotlivých typov mincí. Každá z týchto hodnôt je menšia ako 100 000.
  • Tretí riadok obsahuje počet hodnôt, ktoré chceme zaplatiť q, (1≤q≤1000).
  • Ďalej bude nasledovať q prirodzených čísel určujúcich hodnoty, ktoré chceme v tejto mene zaplatiť. Každá z týchto hodnôt je menšia ako 100 000.
Môžete predpokladať, že jedna z mincí má nominálnu hodnotu 1.

Výstup

Výstupom každej testovacej sady má byť q čísel, každé v samostatnom riadku, kde i-te číslo zodpovedá minimálnemu počtu mincí, ktorými sa dá v danej mene zaplatiť i-ta hodnota zo vstupu. Jednotlivé sady musia byť na výstupe oddelené prázdnym riadkom (za poslednou sadou už prázdny riadok nenasleduje).

Príklad vstupu

2
11
1 2 5 10 20 50 100 200 500 1000 5000
5
2043
24
25
28
4678
2
1 2
5
1
2
3
4
5

Príklad výstupu

6
3
2
4
11

1
1
2
2
3
time limit: 10 seconds
points: 4

#include <cstdio>
#include <algorithm>

using namespace std;

int main(void){
int p;
scanf("%d\n",&p);
int i=0;
while(i<p){
	int n;
	scanf("%d\n",&n);
	int nominalneHodnoty[n];
	//sort(nominalneHodnoty,nominalneHodnoty+n);
	int hodnoty[100001];	
	hodnoty[0]=0;
	for(int j=0;j<n;j++){
	        int tmp;
		scanf("%d ",&tmp);
		nominalneHodnoty[j]=tmp;
	}
	for(int j=1;j<100001;j++){
	        int min = 100001;
	        for(int k=0;k<n;k++){
	                if(nominalneHodnoty[k]<=j){
	                        if(1+hodnoty[j-nominalneHodnoty[k]]<min){
	                        min = 1+hodnoty[j-nominalneHodnoty[k]];	                        
	                        }
	                }
	        }
	        hodnoty[j]=min;
	}
	int pocetCisel;
	scanf("%d\n",&pocetCisel);
	for(int j=0;j<pocetCisel;j++){
		int ciselko;
		scanf("%d\n",&ciselko);
		printf("%d\n",hodnoty[ciselko]);
	}
	if(i!=p-1)
	printf("\n");
	i++;
}
return 0;
}