# A http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0809/06ora/bolgar oldalon található
# probléma megoldása Ruby-ban.
# Írta: Kriván Bálint @ 2008/10/25

# Partíciók generálása a konstruktorban megadott +n+ szám alapján
class PartitionGenerator
    # Incializálás, első partíció generálása
    def initialize( n )
        @n = n
        @t = [n]
        @t[0] = n
        1.upto(n-1) do |i|
            @t[i] = 0
        end
    end

    # Igaz, amíg van új partíció, közben lejátszunk egy bolgár szolitert
    def has_next_partition
        # egy adott partícióval játszunk
        bs = BulgarianSolitaire.new(@t, @length)
        bs.play
    
        @t.each do |item|
            return true unless (item == 1) # ha már minden elem 1-es, akkor az összes partíciót megvizsgáltuk
        end
        return false
    end

    # Az adott partícióból következő következő partíció keresése
    def next_partition
        # [q,(length-q-1)] intervallumot kell kicserélni valami másra
        # t[q] = x+1 -> t[q] = x, többi is x és a végére még valami (maradék).
        sum = 0
        0.upto(@q-1) do |i|
            sum += @t[i]
        end
        # tehát amit eloszthatunk az n-sum
        available = @n-sum
        x = @t[@q]-1 # ilyenekre akarjuk eldarabolni
        i = @q # megjegyezzük, hogy honnan kezdjük el feltölteni
        @q = if @q > 0 then @q-1 else 0 end # a következő körre megjegyezzük, hogy legalább a @q-1-től kell majd kezdeni
        while available != 0 do
            if( available > x ) then # amíg van mit elosztani addig elosztjuk
                @t[i] = x
                available -= x
            else # ha nincs, akkor megy a maradék
                @t[i] = available
                available = 0
            end
            if( @t[i] != 1 ) then
                @q = i
            end
            i += 1
        end
        # beállítjuk a többit 0-sra, hiszen mindig egyazon @t-n dolgozunk.
        @length = i
        i.upto(@n-1) do |j|
            @t[j] = 0
        end
    end

    # partíció generálás
    def generate
        @q = 0
        @length = 1
        while has_next_partition do
            next_partition
        end
    end
end

# Bolgár szoliter játszása, a megadott kupac elrendezéstől kezdve
class BulgarianSolitaire
    def initialize( t, length )
        @t = t[0..length-1] # csak a tényleg használt intervallum kell
        @ts = Array.new
        @cycle_start = -1
        @cycle_length = 0
    end

    # Igaz, amíg nem találunk ciklust a játékban
    def no_cycle
        if( @cycle_start != -1 ) then
            # ha már valahol találtunk ciklus kezdeményt, akkor innen ellenőrizzük
            if( @ts[@cycle_start] == @t ) then
                # vége a ciklusnak, ha visszaértünk a ciklus kezdő kavicsfelosztásra
                return false
            elsif( @ts[@cycle_start+@cycle_length] == @t ) then
                # ha folytatódik a ciklus, akkor növeljük a hosszt
                @cycle_length += 1
            else
                # nem ciklust talátunk, kezdjük előlről
                @cycle_start = -1
                @cycle_length = 0
            end
        else
            @ts.length.times do |i|
                if( @ts[i] == @t ) then
                    @cycle_start = i
                    @cycle_length = 1
                    break
                end
            end
        end
        @ts.insert(-1, @t)
        return true
    end

    # Maga a játék, folyamatosan pakolgatunk, amíg nem találunk ciklust
    # majd ezt kiírjuk
    def play
        print("Kezdeti kupacok: ")
        print("{#{@t.join(",")}}\n")
        
        while no_cycle do
            v = Array.new
            @t.length.times do |i|
                if( @t[i] > 1 ) then
                    v[v.length] = @t[i]-1 # mindenhonnan leveszünk egy kavicsot, ahonnan van értelme
                end
            end
            v[v.length] = @t.length # végére beszúrjuk a levett kavicsokat

            @t = v
        end

        # output generálás

        cycle = @ts[@cycle_start..@cycle_start+@cycle_length-1]
        print( "#{cycle.length}: ")
        print( "{" )
        cycle.each_index do |i|
            print("#{cycle[i].join("")}")
            print(", ") if ( i+1 < cycle.length )
        end
        print( "}\n\n" )
    end
end

print("kavicsok száma? ")
s = $stdin.readline($/)
n = s.to_i
if( n == 0 ) then
    print("pozitív egész számnak kell lennie a kavicsok számának!")
else
    # generáljuk az n pozitív egész szám partícióit
    # és minden partícióra játszunk egy bolgár szolitert
    pg = PartitionGenerator.new(n)
    pg.generate()
end