Consider a currency system in which there are notes of six denominations, namely, Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100.
If the sum of Rs. N is input, write a program to computer smallest number of notes that will combine to give Rs. N.

-----Input-----

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N. 

-----Output-----
For each test case, display the smallest number of notes that will combine to give N, in a new line.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 1000000

-----Example-----
Input
3 
1200
500
242

Output
12
5
7

Source: codechef | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
t = int(input())
notes = [100, 50, 10, 5, 2, 1]
for i in range(t):
	n = int(input())
	count = 0
	for x in notes:
		count += n // x
		n %= x
	print(count)


notas = [100, 50, 10, 5, 2, 1]
t = int(input())
for i in range(t):
	s = int(input())
	numeros_notas = 0
	for note in notas:
		num = s // note
		s -= num * note
		numeros_notas += num
	print(numeros_notas)


li = [100, 50, 10, 5, 2, 1]
for i in range(int(input())):
	x = int(input())
	b = 0
	for j in li:
		if j <= x:
			b = b + x // j
			x = x % j
	print(b)


def notes(a):
	Q = [100, 50, 10, 5, 2, 1]
	(x, b) = (0, 0)
	for i in Q:
		b = a // i
		x += b
		a = a - i * b
	return x
n = int(input())
for i in range(n):
	m = int(input())
	print(notes(m))


n = int(input())
for i in range(n):
	notes = int(input())
	sum = 0
	for x in [100, 50, 10, 5, 2, 1]:
		y = notes // x
		notes = notes - y * x
		sum = sum + y
	print(sum)


t = int(input())
for i in range(t):
	P = [100, 50, 10, 5, 2, 1]
	n = int(input())
	count = 0
	for i in P:
		if n >= i:
			count = count + n // i
			n = n % i
	print(count)


n = int(input())
demo = [100, 50, 10, 5, 2, 1]
for i in range(0, n):
	x = int(input())
	coins = 0
	j = 0
	while x > 0:
		if x < demo[j]:
			j = j + 1
		else:
			coins = coins + 1
			x = x - demo[j]
	print(coins)


n = int(input())
for i in range(n):
	a = int(input())
	note = 0
	while a != 0:
		if a >= 100:
			a -= 100
		elif a >= 50:
			a -= 50
		elif a >= 10:
			a -= 10
		elif a >= 5:
			a -= 5
		elif a >= 2:
			a -= 2
		else:
			a -= 1
		note += 1
	print(note)


n = int(input())
for i in range(n):
	x = int(input())
	a = x % 100
	b = a % 50
	c = b % 10
	d = c % 5
	e = d % 2
	f = e % 1
	print(x // 100 + a // 50 + b // 10 + c // 5 + d // 2 + e // 1 + f)


t = int(input())
for i in range(t):
	N = int(input())
	notes = [100, 50, 10, 5, 2, 1]
	count = 0
	for i in notes:
		while N >= i:
			N -= i
			count += 1
	print(count)


t = int(input())
deno = [100, 50, 10, 5, 2, 1]
for i in range(t):
	n = int(input())
	coin = 0
	id = 0
	while n > 0:
		if n < deno[id]:
			id += 1
		else:
			coin += 1
			n = n - deno[id]
	print(coin)


for T in range(int(input())):
	n = int(input())
	a = n // 100
	a1 = n - 100 * a
	b = a1 // 50
	b1 = a1 - 50 * b
	c = b1 // 10
	c1 = b1 - 10 * c
	d = c1 // 5
	d1 = c1 - 5 * d
	e = d1 // 2
	e1 = d1 - 2 * e
	f = e1 // 10
	f1 = e1 - 10 * f
	print(a + b + c + d + e + f + f1)


t = int(input())
deno = [100, 50, 10, 5, 2, 1]
for i in range(t):
	n = int(input())
	idx = 0
	count = 0
	while n > 0:
		if n < deno[idx]:
			idx += 1
		else:
			count += 1
			n = n - deno[idx]
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	lst = [100, 50, 10, 5, 2, 1]
	c = 0
	for j in lst:
		c += n // j
		n = n % j
		if n == 0:
			break
	print(c)


t = int(input())
for i in range(t):
	s = 0
	n = int(input())
	l = [100, 50, 10, 5, 2, 1]
	k = n
	while k != 0:
		for j in range(len(l)):
			s = s + k // l[j]
			k = k % l[j]
		print(s)


t = int(input())
for i in range(t):
	n = int(input())
	cnt = 0
	while n > 0:
		cnt = cnt + 1
		if n >= 100:
			n = n - 100
		elif n >= 50:
			n = n - 50
		elif n >= 10:
			n = n - 10
		elif n >= 5:
			n = n - 5
		elif n >= 2:
			n = n - 2
		else:
			n = n - 1
	print(cnt)


t = int(input())
d = [100, 50, 10, 5, 2, 1]
for _ in range(t):
	n = int(input())
	coins = 0
	idx = 0
	while n > 0:
		if n < d[idx]:
			idx += 1
		else:
			coins += 1
			n = n - d[idx]
	print(coins)


for _ in range(int(input())):
	l = [100, 50, 10, 5, 2, 1]
	n = int(input())
	c = 0
	for i in l:
		if n >= i:
			r = n / i
			if type(r) == int:
				print(r)
				break
			else:
				r = int(r)
				c += r
				n = n - i * r
		if n == 0:
			break
	print(c)


n = int(input())

def count(x):
	m = 0
	if x - 100 >= 0:
		m = int(x / 100)
		x = x % 100
	if x - 50 >= 0:
		m = int(x / 50) + m
		x = x % 50
	if x - 10 >= 0:
		m = int(x / 10) + m
		x = x % 10
	if x - 5 >= 0:
		m = int(x / 5) + m
		x = x % 5
	if x - 2 >= 0:
		m = int(x / 2) + m
		x = x % 2
	if x - 1 >= 0:
		m = 1 + m
	return m
for i in range(n):
	x = int(input())
	p = count(x)
	print(p)


def count(n):
	notes = [100, 50, 10, 5, 2, 1]
	c = 0
	for note in notes:
		while n >= note:
			n -= note
			c += 1
	return c
t = int(input())
for i in range(t):
	n = int(input())
	print(count(n))


l = [100, 50, 10, 5, 2, 1]
for _ in range(int(input())):
	s = int(input())
	coins = 0
	i = 0
	while s > 0:
		if s < l[i]:
			i += 1
		else:
			coins += 1
			s = s - l[i]
	print(coins)


T = int(input())
deno = [100, 50, 10, 5, 2, 1]
for i in range(0, T):
	a = int(input())
	count = 0
	idx = 0
	while a > 0:
		if a < deno[idx]:
			idx += 1
		else:
			count += 1
			a = a - deno[idx]
	print(count)


t = int(input())
for i in range(t):
	ct = 0
	l = [1, 2, 5, 10, 50, 100]
	n = int(input())
	for i in range(len(l) - 1, -1, -1):
		while n >= l[i]:
			ct += 1
			n = n - l[i]
	print(ct)


t = int(input())
array = [100, 50, 10, 5, 2, 1]
for i in range(t):
	n = int(input())
	coins = 0
	index = 0
	while n > 0:
		if n < array[index]:
			index = index + 1
		else:
			coins = coins + 1
			n = n - array[index]
	print(coins)


T = int(input())
a = [100, 50, 10, 5, 2, 1]
for _ in range(T):
	n = int(input())
	b = 0
	for x in a:
		if x <= n:
			b = b + n // x
			n = n % x
	print(b)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = [100, 50, 10, 5, 2, 1]
	i = 0
	c = 0
	while n > 0:
		if n < a[i]:
			i += 1
		else:
			c += 1
			n = n - a[i]
	print(c)


T = int(input())
notes = [100, 50, 10, 5, 2, 1]
for i in range(T):
	N = int(input())
	coins = 0
	index = 0
	while N > 0:
		if N < notes[index]:
			index += 1
		else:
			coins += 1
			N = N - notes[index]
	print(coins)


def Countcurrency(amount):
	count = 0
	notes = [100, 50, 10, 5, 2, 1]
	for i in notes:
		if amount >= i:
			count = count + amount // i
			amount = amount % i
	print(count)
t = int(input())
while t > 0:
	n = int(input())
	Countcurrency(n)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	count = 0
	while N > 0:
		if N >= 100:
			count += 1
			N -= 100
		elif N >= 50:
			count += 1
			N -= 50
		elif N >= 10:
			count += 1
			N -= 10
		elif N >= 5:
			count += 1
			N -= 5
		elif N >= 2:
			count += 1
			N -= 2
		elif N >= 1:
			count += 1
			N -= 1
	print(count)


n = int(input())
for i in range(n):
	a = int(input())
	if a % 100 == 0:
		print(a // 100)
	else:
		n1 = a % 100
		n2 = n1 % 50
		n3 = n2 % 10
		n4 = n3 % 5
		n5 = n4 % 2
		print(a // 100 + n1 // 50 + n2 // 10 + n3 // 5 + n4 // 2 + n5)


n = int(input())
lst = [100, 50, 10, 5, 2, 1]
for i in range(n):
	a = int(input())
	i = 0
	count = 0
	while a > 0:
		if a >= lst[i]:
			count += 1
			a = a - lst[i]
		else:
			i += 1
	print(count)


n = int(input())
l1 = []
for i in range(0, n):
	l1.append(int(input()))
for item in l1:
	num1 = 0
	a = item % 100
	if a == 0:
		num1 += item / 100
	else:
		num1 += (item - a) / 100
		b = a % 50
		if b == 0:
			num1 += a / 50
		else:
			num1 += (a - b) / 50
			c = b % 10
			if c == 0:
				num1 += b / 10
			else:
				num1 += (b - c) / 10
				d = c % 5
				if d == 0:
					num1 += c / 5
				else:
					num1 += (c - d) / 5
					e = d % 2
					if e == 0:
						num1 += d / 2
					else:
						num1 += (d - e) / 2
						f = e % 1
						if f == 0:
							num1 += e
	print(int(num1))


T = int(input())
a = [100, 50, 10, 5, 2, 1]
for i in range(T):
	count = 0
	ind = 0
	n = int(input())
	while n != 0 and ind <= 5:
		if n >= a[ind]:
			n -= a[ind]
			count += 1
		else:
			ind += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	lst = [100, 50, 10, 5, 2, 1]
	count = 0
	for j in lst:
		rem = n // j
		count += rem
		n %= j
	print(count)


for i in range(int(input())):
	x1 = int(input())
	a = x1 % 100
	b2 = a % 50
	c = b2 % 10
	d = c % 5
	e = d % 2
	f = e % 1
	print(x1 // 100 + a // 50 + b2 // 10 + c // 5 + d // 2 + e // 1 + f)


t = int(input())
cl = [1, 2, 5, 10, 50, 100]
l = len(cl)
for i in range(t):
	a = int(input())
	n = 0
	w = 1
	while a % cl[-w] != 0:
		n = n + a // cl[-w]
		a = a % cl[-w]
		w = w + 1
	n = n + a // cl[-w]
	print(n)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	for x in [100, 50, 10, 5, 2, 1]:
		y = n // x
		n -= y * x
		c += y
	print(c)


b = int(input())
l = [100, 50, 10, 5, 2, 1]
for i in range(b):
	count = 0
	a = int(input())
	for i in l:
		while i <= a:
			a -= i
			count += 1
		else:
			i += 1
	print(count)


t = int(input())
l = [100, 50, 10, 5, 2, 1]
for _ in range(t):
	c = 0
	n = int(input())
	i = 0
	while n:
		c += n // l[i]
		n = n % l[i]
		i = i + 1
	print(c)


t = int(input())
l = [100, 50, 10, 5, 2, 1]
for k in range(t):
	c = 0
	s = 0
	n = int(input())
	for j in range(6):
		s = int(n / l[j])
		c = c + s
		n = n - s * l[j]
	print(c)


for i in range(int(input())):
	ar = [100, 50, 10, 5, 2, 1]
	i = 0
	c = 0
	n = int(input())
	while n != 0:
		c = c + n // ar[i]
		n = n % ar[i]
		i += 1
	print(c)


t = int(input())
for i in range(t):
	a = int(input())
	notes = [100, 50, 10, 5, 2, 1]
	c = 0
	while a >= 1:
		for i in notes:
			c = c + a // i
			a = a % i
	print(c)


T = int(input())
notes = [100, 50, 10, 5, 2, 1]
for i in range(T):
	N = int(input())
	x = 0
	for j in range(len(notes)):
		if N != 0:
			x += N // notes[j]
			N %= notes[j]
	print(x)


for i in range(int(input())):
	x = int(input())
	y = x
	count = 0
	a = [100, 50, 10, 5, 2, 1]
	for i in a:
		if y % i != i and y != 0:
			div = int(y / i)
			count += div
			y = y - div * i
		else:
			count += 0
	print(count)


t = int(input())
while t != 0:
	n = int(input())
	ct = 0
	notes = [100, 50, 10, 5, 2, 1]
	i = 0
	while n:
		ct += n // notes[i]
		n = n % notes[i]
		i += 1
	print(ct)
	t = t - 1


n = int(input())
notes = [100, 50, 10, 5, 2, 1]
for i in range(n):
	count = 0
	index = 0
	num = int(input())
	while num > 0:
		count = count + num // notes[index]
		num = num % notes[index]
		index += 1
	print(count)


n = int(input())
for i in range(0, n):
	a = int(input())
	m = 0
	for j in [100, 50, 10, 5, 2, 1]:
		b = a // j
		a -= b * j
		m += b
	print(m)


for i in range(int(input())):
	num = int(input())
	cnt = 0
	lst = [100, 50, 10, 5, 2, 1]
	for i in range(len(lst)):
		cnt += num // lst[i]
		num = num % lst[i]
	print(cnt)


n = int(input())
for i in range(n):
	p = int(input())
	q = p // 100
	q = q + p % 100 // 50
	q = q + p % 100 % 50 // 10
	q = q + p % 100 % 50 % 10 // 5
	q = q + p % 100 % 50 % 10 % 5 // 2
	q = q + p % 100 % 50 % 10 % 5 % 2
	print(q)


for i in range(int(input())):
	n = int(input())
	j = 0
	while n != 0:
		j += 1
		if n >= 100:
			n -= 100
		elif n >= 50:
			n -= 50
		elif n >= 10:
			n -= 10
		elif n >= 5:
			n -= 5
		elif n >= 2:
			n -= 2
		elif n >= 1:
			n -= 1
	print(j)


T = int(input())
for tc in range(T):
	n = int(input())
	count = 0
	while n:
		count += n // 100
		n = n % 100
		count += n // 50
		n = n % 50
		count += n // 10
		n = n % 10
		count += n // 5
		n = n % 5
		count += n // 2
		n = n % 2
		count += n // 1
		n = n % 1
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	ds = [100, 50, 10, 5, 2, 1]
	notes_count = 0
	for d in ds:
		notes_count += N // d
		N %= d
		if N == 0:
			break
	print(notes_count)
l = 2542524354325324665


T = int(input())
avail = [100, 50, 10, 5, 2, 1]
for i in range(T):
	N = int(input())
	notes = []
	for note in avail:
		if note > N:
			continue
		else:
			c = N // note
			notes.append(c)
			N = N % note
	print(sum(notes))


TC = int(input())
coins = [100, 50, 10, 5, 2, 1]
while TC > 0:
	N = int(input())
	ans = 0
	for i in coins:
		ans += N // i
		N = N % i
		if N == 0:
			break
	print(ans)
	TC -= 1


T = int(input())
for i in range(T):
	N = int(input())
	a = 0
	for x in [100, 50, 10, 5, 2, 1]:
		y = N // x
		N -= y * x
		a += y
	print(a)


T = int(input())
x = [100, 50, 10, 5, 2, 1]
for _ in range(T):
	n = int(input())
	y = 0
	for i in x:
		if i <= n:
			y = y + n // i
			n = n % i
	print(y)


t = int(input())
for i in range(t):
	s = 0
	n = int(input())
	l = [100, 50, 10, 5, 2, 1]
	k = n
	it = 0
	total = 0
	l1 = []
	while sum(l1) != n:
		r = k // l[it]
		total = total + r
		if r != 0:
			l1.append(r * l[it])
			k = k % l[it]
		it += 1
	print(total)


x = int(input())
lst = [1, 2, 5, 10, 50, 100]
for i in range(x):
	y = int(input())
	c = 5
	a = 0
	while y > 0:
		if y >= lst[c]:
			y = y - lst[c]
			a = a + 1
		else:
			c = c - 1
	print(a)


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	sum = 0
	if n >= 100:
		c = c + n // 100
		n = n % 100
	if n >= 50:
		c = c + n // 50
		n = n % 50
	if n >= 10:
		c = c + n // 10
		n = n % 10
	if n >= 5:
		c = c + n // 5
		n = n % 5
	if n >= 2:
		c = c + n // 2
		n = n % 2
	if n >= 1:
		c = c + n // 1
	print(c)


n = int(input())
l = [100, 50, 10, 5, 2, 1]
for i in range(0, n):
	note = int(input())
	count = 0
	for i in range(0, 6):
		if note == 0:
			break
		else:
			rem = note // l[i]
			note = note - rem * l[i]
			count += rem
	print(count)


q = int(input())
for i in range(q):
	count = 0
	n = int(input())
	count += n // 100
	n = n % 100
	count += n // 50
	n = n % 50
	count += n // 10
	n = n % 10
	count += n // 5
	n = n % 5
	count += n // 2
	n = n % 2
	count += n // 1
	n = n % 1
	print(count)


de = [100, 50, 10, 5, 2, 1]
T = int(input())
for i in range(T):
	N = int(input())
	num = 0
	for o in de:
		ns = N // o
		num += ns
		N -= ns * o
	print(num)


def compute(numb):
	cnt = 0
	currs = [100, 50, 10, 5, 2, 1]
	for cur in currs:
		cnt = cnt + numb // cur
		numb = numb % cur
	print(cnt)
t = int(input())
for _ in range(t):
	numb = int(input())
	compute(numb)


curr = [100, 50, 10, 5, 2, 1]
t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	idx = 0
	while n > 0:
		if n < curr[idx]:
			idx += 1
		else:
			count += 1
			n = n - curr[idx]
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	l = [100, 50, 10, 5, 2, 1]
	sum = 0
	for i in l:
		sum += n // i
		n = n % i
	print(sum)
	t = t - 1


def main():
	t = input()
	for i in range(int(t)):
		n = int(input())
		notes = 0
		if n >= 100:
			remain = n % 100
			notes = notes + (n - remain) // 100
			n = remain
		if n >= 50:
			remain = n % 50
			notes = notes + (n - remain) // 50
			n = remain
		if n >= 10:
			remain = n % 10
			notes = notes + (n - remain) // 10
			n = remain
		if n >= 5:
			remain = n % 5
			notes = notes + (n - remain) // 5
			n = remain
		if n >= 2:
			remain = n % 2
			notes = notes + (n - remain) // 2
			n = remain
		if n >= 1:
			remain = n % 1
			notes = notes + (n - remain) // 1
			n = remain
		print(notes)
main()


for i in range(int(input())):
	num = int(input())
	list = [100, 50, 10, 5, 2, 1]
	count = 0
	index = 0
	while num > 0:
		if num >= list[index]:
			num -= list[index]
			count += 1
		else:
			index += 1
	print(count)


t = int(input())
while t > 0:
	n = int(input())
	notes = 0
	ls = [100, 50, 10, 5, 2, 1]
	for i in ls:
		notes = notes + n // i
		n = n % i
	print(notes)
	t = t - 1


t = int(input())
for i in range(t):
	N = int(input())
	l = [1, 2, 5, 10, 50, 100]
	c = 0
	for i in range(len(l) - 1, -1, -1):
		y = N // l[i]
		N = N - y * l[i]
		c += y
	print(c)


t = int(input())
i = 0
while i < t:
	n = int(input())
	c = 0
	z = 0
	if n >= 100:
		a = n // 100
		n = n - 100 * a
		z = a
	if n >= 50:
		b = n // 50
		n = n - 50 * b
		z = z + b
	if n >= 10:
		c = n // 10
		n = n - 10 * c
		z = z + c
	if n >= 5:
		d = n // 5
		n = n - 5 * d
		z = z + d
	if n >= 2:
		e = n // 2
		n = n - 2 * e
		z = z + e
	if n == 1:
		print(z + 1)
	else:
		print(z)
	i += 1


for t in range(int(input())):
	n = int(input())
	a = n // 100
	r1 = n % 100
	a2 = r1 // 50
	r2 = r1 % 50
	a3 = r2 // 10
	r3 = r2 % 10
	a4 = r3 // 5
	r4 = r3 % 5
	a5 = r4 // 2
	r5 = r4 % 2
	print(a + a2 + a3 + a4 + a5 + r5)


for i in range(int(input())):
	cnt = 0
	amt = int(input())
	while amt != 0:
		if amt >= 100:
			cnt += amt // 100
			amt -= amt // 100 * 100
		elif amt >= 50:
			cnt += amt // 50
			amt -= amt // 50 * 50
		elif amt >= 10:
			cnt += amt // 10
			amt -= amt // 10 * 10
		elif amt >= 5:
			cnt += amt // 5
			amt -= amt // 5 * 5
		elif amt >= 2:
			cnt += amt // 2
			amt -= amt // 2 * 2
		else:
			cnt += amt
			amt -= amt
	print(cnt)