Estou com o mesmo problema.
Estou usando o Python 3.5
valor = int(input())
if (0 < valor < 1000000):
valor100 = valor//100
print ("%i" % valor100, "nota(s) de R$ 100,00")
valor = valor - (valor100 * 100)
valor50 = valor//50
print ("%i" % valor50, "nota(s) de R$ 50,00")
valor = valor - (valor50 *50)
valor20 = valor//20
print ("%i" % valor20, "nota(s) de R$ 20,00")
valor = valor - (valor20 *20)
valor10 = valor//10
print ("%i" % valor10, "nota(s) de R$ 10,00")
valor = valor - (valor10 *10)
valor5 = valor//5
print ("%i" % valor5, "nota(s) de R$ 5,00")
valor = valor - (valor5 * 5)
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor50 = valor//50
print ("%i" % valor50, "nota(s) de R$ 50,00")
valor = valor - (valor50 *50)
valor20 = valor//20
print ("%i" % valor20, "nota(s) de R$ 20,00")
valor = valor - (valor20 *20)
valor10 = valor//10
print ("%i" % valor10, "nota(s) de R$ 10,00")
valor = valor - (valor10 *10)
valor5 = valor//5
print ("%i" % valor5, "nota(s) de R$ 5,00")
valor = valor - (valor5 * 5)
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor20 = valor//20
print ("%i" % valor20, "nota(s) de R$ 20,00")
valor = valor - (valor20 *20)
valor10 = valor//10
print ("%i" % valor10, "nota(s) de R$ 10,00")
valor = valor - (valor10 *10)
valor5 = valor//5
print ("%i" % valor5, "nota(s) de R$ 5,00")
valor = valor - (valor5 * 5)
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor10 = valor//10
print ("%i" % valor10, "nota(s) de R$ 10,00")
valor = valor - (valor10 *10)
valor5 = valor//5
print ("%i" % valor5, "nota(s) de R$ 5,00")
valor = valor - (valor5 * 5)
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor5 = valor//5
print ("%i" % valor5, "nota(s) de R$ 5,00")
valor = valor - (valor5 * 5)
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor2 = valor//2
print ("%i" % valor2, "nota(s) de R$ 2,00")
valor = valor - (valor2 * 2)
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)
elif (0 < valor < 1000000):
valor1 = valor//1
print ("%i" % valor1, "nota(s) de R$ 1,00")
valor = valor - (valor1 * 1)