This page is still under construction.

Parts of this page are still being built. What you see may change.

Number Pairs

Time limit1sMemory limit128 MB

Summary
For a given N, list all pairs (X, Y) with X + Y = N where deleting one digit from X yields Y, and count them.
Level

Medium6 of 10

Topics
Math, Brute force, Implementation, String matching
Solved
No attempts yet

Problem

Given a natural number NN, write a program that finds every pair of numbers (X,Y)(X, Y) such that X+Y=NX + Y = N. Here YY must be a number obtained by deleting exactly one digit from the decimal representation of XX.

  • XX is a natural number with at least two digits and may not start with 00.
  • YY has at least one digit; if the deleted digit was the leading one, YY may start with 00. Consequently YY always has exactly one fewer digit than XX.

For example, deleting the leading digit 33 from X=301X = 301 gives Y=01Y = 01, and 301+01=302301 + 01 = 302.

Input

The first line contains a natural number NN. (10≤N≤10910 \le N \le 10^9)

Output

On the first line, print the number of distinct pairs that satisfy the condition.

From the next line, print each valid pair on its own line in increasing order of XX. Each line has the form X + Y = N, where XX, YY, and NN are replaced by the actual numbers and exactly one space surrounds each + and = sign. Print YY exactly as it appears after the digit deletion, so it may keep a leading 00 when the deleted digit was the first one.

Examples1

  1. Example 1

    Input
    302
    
    Expected output
    5
    251 + 51 = 302
    275 + 27 = 302
    276 + 26 = 302
    281 + 21 = 302
    301 + 01 = 302