Novcani sistem
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,5 s | 16 Mb | standardni izlaz | standardni ulaz |
Dat je novčani sistem sa N novčanica, čije su vrednosti d[1], d[2], ... , d[N]. Napisati program koji ispituje da li je moguće isplatiti sumu M pomoću datog sistema. U slučaju kada je sumu moguće ispatiti štamapti i način isplate.
U prvom redu ulaza nalaze se dva prirodna broja N i M, broj novčanica i tražena suma, redom. U naredom redu nalazi se N prirodnih brojeva, koji označavaju vrednosti novčanica.
U prvom izlaza štampati 'DA' ukoliko je moguće isplatiti datu sumu, odnosno 'NE' ukoliko nije.
U slučaju da je moguće ispaltiti datu sumu, u drugom redu ispisati N brojeva, C[1], ..., C [N], dovojenih jednim znakom razmaka, tako da je C [1] * d [1] + ... + C [N] * d [N] = M.
- 1 <= N <= 10
- 1 <= d [i] <= 100, za svako i iz [1, N]
- 0 <= M <= 100
- Elementi niza d su različiti prirodni brojevi.
3 12
2 3 5
DA
2 1 1
Način isplate nije jedinstven, drugim rečima i rešenja sa isplatom "1 0 2" i "0 4 0" su korektna.
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.