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)