Numerology P50084


Statement
 

pdf   zip

html

[r]

According to the Bible, 666 is the “number of the beast”. Indeed, in Revelation 13: 18 it is said:

…count the number of the beast: for it is the
number of a man; and his number is 666.

Many theologists have associated 666 with the Antichrist. Believe it or not, 666 has many interesting numerological properties. For instance,

     
666  =   36 − 26 + 16          
 =   1 + 2 + 3 + ⋯ + 6 · 6          
 =   22 + 32 + 52 + 72 + 112 + 132 + 172 .          

Another curious property is that it is possible (there are exactly two ways) to insert ‘+’ signs into the number 123456789 to get 666:

666   =   1 + 2 + 3 + 4 + 567 + 89   =   123 + 456 + 78 + 9 ,

and it is also possible (there is exactly one way) to do the same with the number 987654321:

666   =   9 + 87 + 6 + 543 + 21 .

Let’s play numerology. Write a program such that, given two numbers n and m, prints all the ways to insert ‘+’ signs into m so that the sum is n.

Input

Input consists of several cases. Every case has two strictly positive natural numbers n and m, each not larger than 1012. Assume that the leftmost digit of n and of m is never zero.

Output

For every case, print all the ways to get n by adding the digits of m as explained above. The solutions must appear in lexicographical order. If no solution exists, state so.

Public test cases
  • Input

    666 987654321
    5 321
    4 1003
    

    Output

    666 = 9 + 87 + 6 + 543 + 21
    No solution for 5 321.
    4 = 1 + 0 + 0 + 3
    4 = 1 + 0 + 03
    4 = 1 + 00 + 3
    4 = 1 + 003
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Segon Concurs de Programació de la UPC - Segona Semifinal
    Date
    2004-09-15