Every change P29230


Statement
 

pdf   zip

thehtml

Write a program such that, for every given natural number n, prints all the different ways to obtain n cents with the euro system of coins (1 cent, 2 cents, 5 cents, 10 cents, 20 cents, and 50 cents).

Input

Input consists of a sequence of natural numbers 1 ≤ n ≤ 50.

Output

For every n, print all the ways to obtain n cents, each one in a different line. The numbers of each line must appear in nonincreasing order. The solutions for every n must appear in reverse lexicographical order. Print an empty line after the output for each case.

Observation

A simple backtracking program that computes the result for every given n (even if repeated) is fast enough for this problem.

Public test cases
  • Input

    1
    7
    2
    

    Output

    1
    
    5 2
    5 1 1
    2 2 2 1
    2 2 1 1 1
    2 1 1 1 1 1
    1 1 1 1 1 1 1
    
    2
    1 1
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++