50 x 50 != 250 P21459


Statement
 

pdf   zip

html

In the ACM-ICPC World Finals 2012, the UPC team made as usual a nice set of mistakes. One of them was the original assumption that 50 × 50 = 250. Observe that this equation has two interesting properties:

  1. The right-hand side of the equation is the result of removing one digit from the real result (in the example, 2500).
  2. At least one of the two numbers of the left-hand side of the equation has at least one digit such that, if removed, makes the equation correct (in the example, 5 × 50 = 250).

Let us call an equation x × y = z a fail when it fulfills properties 1 and 2, and an epic fail when it only fulfills property 1. For instance, 50 × 50 = 200 is an epic fail. Please write a program to count the number of fails and epic fails that the UPC teams can make at the ACM-ICPC World Finals. [Footnote: The real number is of course ∞, but let us use the simplifications of the statement. ]

Input

Input consists of several cases. Every case has two numbers x and y with the same number of digits n. Those numbers can have leading zeroes. Assume 2 ≤ n ≤ 1000.

Output

For every case, print the number of different fails and epic fails of the kind x × y = z. Note that z must have length exactly 2n − 1, if necessary by adding leading zeroes.

Public test cases
  • Input

    50 50
    002 003
    9999 9999
    0000 0000
    100 111
    0123456789 9876543210
    21212121212121 40000000000000
    

    Output

    1 2
    2 0
    0 4
    1 0
    2 1
    2 16
    15 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Final
    Date
    2012-09-15