# coding=utf-8
# La première ligne sert pour python (et ipython) 2, qui n'aiment pas
# les caractères non ASCII.

# Dans ipython :
# run seance4.py

# Version «Pythonique» : produit de chaîne et entier.
def pythonic_asterisk_line (n):
    return '*' * n

# Version non Pythonique.
def asterisk_line (n):
    s = ''
    for i in range (n):
        s = s + '*'
    return s

def draw_asterisk_square (n):
    for i in range (n):
        print (asterisk_line (n))

def draw_asterisk_triangle (n):
    for i in range (1, n + 1):
        print (asterisk_line (i))

def draw_asterisk_triangle2 (n):
    for i in range (n):
        print (asterisk_line (i + 1))

def power_natural_exponent (base, exponent):
    p = 1
    for i in range (exponent):
        p = p * base
    return p

def power (base, exponent):
    if exponent < 0:
        tmp = power_natural_exponent (base, - exponent)
        return 1.0 / tmp
    else:
        return power_natural_exponent (base, exponent)

def has (list, element):
    for e in list:
        if e == element:
            return True
    return False

def count_vowels (s):
    c = 0
    for i in range (len (s)):
        if is_vowel (s[i]):
            c = c + 1
    return c

def count_vowels2 (s):
    c = 0
    for i in range (len (s)):
        c = c + count_vowels_in_character (s[i])
    return c

# Je vais ignorer le contrôle
# if len (c) != 1:
#     error
def is_vowel1 (c):
    if c == 'a':
        return True
    elif  c == 'e':
        return True
    elif  c == 'i':
        return True
    elif  c == 'o':
        return True
    elif  c == 'u':
        return True
    elif  c == 'y':
        return True
    else:
        return False
def is_vowel2 (c):
    if c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' or c == 'y':
        return True
    else:
        return False
def is_vowel3 (c):
    return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u' or c == 'y'
# Version pythonique imperfecte
def is_vowel4 (c):
    if c in ['a', 'e', 'i', 'o', 'u', 'y']:
        return True
    else:
        return False
# Version pythonique
def is_vowel5 (c):
    return c in ['a', 'e', 'i', 'o', 'u', 'y']

# Version encore plus pythonique
def is_vowel (c):
    return c in 'aeiouy'

def count_vowels_in_character (c):
    if is_vowel (c):
        return 1
    else:
        return 0

# Very verbose version
def last (list):
    size = len (list)
    e = list[size - 1]
    return e

def last1 (list):
    size = len (list)
    return list[size - 1]

def last2 (list):
    return list[len (list) - 1]

def nondestructively_invert1 (list):
    r = []
    for e in list:
        r = [e] + r
    return r

# Un indice i du résultat correspond à un indice
# (size - i - 1 du) paramètre.
def nondestructively_invert2 (list):
    r = []
    size = len (list)
    for i in range (size):
        r = r + [ list[ size - i - 1] ]
    return r

def nondestructively_invert3 (list):
    r = []
    size = len (list)
    for i in range (size):
        r.append (list[size - i - 1])
    return r

def is_prime (n):
    for candidate_divisor in range (2, n):
        if n % candidate_divisor == 0:
            return False
    return True

def print_all_primes ():
    n = 2
    while True:
        if is_prime (n):
            print (n)
        n = n + 1

# This destructively modified the list referred by candidate_divisors if
# n is prime with respect to its elements.
def is_prime_with_respect_to (n, candidate_divisors):
    for candidate_divisor in candidate_divisors:
        if n % candidate_divisor == 0:
            return False
    candidate_divisors.append (n)
    return True

def print_all_primes1 ():
    n = 2
    primes = [2]
    while True:
        if is_prime_with_respect_to (n, primes):
            print (n)
        n = n + 1

def flatten (list_of_lists):
    r = []
    for e in list_of_lists:
        r = r + e
    return r

def min (a, b):
    if a < b:
        return a
    else:
        return b

def max (a, b):
    if a > b:
        return a
    else:
        return b

# Calculer le mininum *et* le maximum des éléments d'une liste.  C'est interdit
# d'utiliser plus que *une* boucle.  Les minimum et le maximum sont renvoyés dans
# une tuple.  On fait l'hypothèse que la liste ne soit pas vide.
def min_and_max_of (list):
    current_min = list[0]
    current_max = list[0]
    for i in range (1, len(list)):
        current_min = min (current_min, list[i])
        current_max = max (current_max, list[i])
    return (current_min, current_max)

def bubble_sort (list):
    for i in range (len (list)):
        index_of_min = index_of_min_in_from (list, i)
        swap_elements (list, index_of_min, i)

def index_of_min_in_from (list, start_index):
    cm = start_index
    for i in range (start_index + 1, len (list)):
        if list[i] < list[cm]:
            cm = i
    return cm

def swap_elements (list, i1, i2):
    e1 = list[i1]
    e2 = list[i2]
    list[i1] = e2
    list[i2] = e1

existing_euros = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]

# Pay amount with the minimum number of coins.  Return the list of paid coins.
def minimum_coins (amount, existing_coins):
    r = []
    # This destructive effect may not be acceptable, but it's late
    existing_coins.sort ()
    while amount > 0:
        first_coin = best_coin (amount, existing_coins)
        amount = amount - first_coin
        r.append (first_coin)
    return r

def best_coin (amount, existing_coins):
    # Assume that existing_coins is sorted.
    for i in range (len (existing_coins) - 1, -1, -1):
        if existing_coins[i] <= amount:
            return existing_coins[i]
    error # There are no suitable coins

# In my opinion this is less readable than the first one using an auxiliary function,
# even ignoring the "no suitable coin" problem, which here is not checked explicitly.
def minimum_coins_without_auxiliary (amount, existing_coins):
    r = []
    # This destructive effect may not be acceptable, but it's late
    existing_coins.sort ()
    while amount > 0:
        # Compute first_coin:
        i = len (existing_coins) - 1
        while existing_coins[i] > amount: # This is gonna fail if no suitable coins exist
            i = i - 1
        first_coin = existing_coins[i]
        amount = amount - first_coin
        r.append (first_coin)
    return r