Under construction

Still being built. Things may change

Pride and Prejudice and Zombies

Time limit1sMemory limit128 MB

Summary
For each number up to 18 digits, decide whether its digits split into two equal-length factors with no leading or consecutive zeros.
Level

Medium6 of 10

Topics
Brute force, Backtracking, Math
Solved
No attempts yet

Problem

Pride and Prejudice and Zombies, by Jane Austen and Seth Grahame-Smith, reimagines the famous 1813 satire of marriage and social convention, now interrupted by zombies, skunks, ghouls, chipmunks, and ninjas. Most critics praised the novel as clever and insightful, though not everyone agreed.

A little-known fact: the book's release was delayed by some eight years because of heated disagreements between the author and the editors at the small Philadelphia publishing house that eventually printed it. The most impassioned argument centered on the controversial "Vampire Number" chapter, in which Mrs. Bennett -- desperate to rally the countryside's interest in matrimony -- stages a social event where 50 men and 50 women each draw a slip of paper from a large, feathery hat.

On each slip is a single three-digit number. The goal of the event: each woman must find the man whose three-digit number, when multiplied by her own, produces a six-digit number that reuses the digits of the two multiplicands in some order. The chapter was eventually cut, and its existence surfaced only recently.

Vampire numbers

A vampire number is a positive integer with an even number of digits -- say 2n2n -- such that its 2n2n digits can be split into two nn-digit numbers whose product equals the original number. None of the three numbers may have leading zeros, and neither of the two nn-digit numbers may contain two consecutive zeros anywhere.

For example:

  • 125460=204×615125460 = 204 \times 615, so 125460125460 is a vampire number.
  • 16758243290880=1982736×845208016758243290880 = 1982736 \times 8452080, so it is a vampire number.
  • 353353 has an odd number of digits, so it cannot be a vampire number.
  • 34213421 cannot be split into two valid factors, so it is not a vampire number.

Given a series of numbers (each at most 18 digits), decide for each whether it is a vampire number.

Input

The input consists of an arbitrary number of values, one per line, each with no leading zeros and no extra whitespace. Each number has at most 18 digits. The input ends with a single line containing 0, which must not produce any output.

Output

For each input number, print the number, then a colon, then a space, then yes if the number is a vampire number or no if it is not.

Examples2

  1. Example 1

    Input
    1260
    6880
    8680
    102510
    108135
    110758
    115672
    116725
    125248
    12054060
    13078260
    46847902
    46847921
    1001795850
    315987404670
    472812953760
    10174695862032
    10174695862037
    2512099504480801
    8186379410403769
    170147428389340249
    189598345243224241
    968781726110944201
    968781726110944203
    698781726110944201
    0
    
    Expected output
    1260: yes
    6880: yes
    8680: no
    102510: yes
    108135: yes
    110758: yes
    115672: yes
    116725: yes
    125248: yes
    12054060: yes
    13078260: yes
    46847902: no
    46847921: no
    1001795850: yes
    315987404670: yes
    472812953760: yes
    10174695862032: yes
    10174695862037: no
    2512099504480801: yes
    8186379410403769: yes
    170147428389340249: yes
    189598345243224241: yes
    968781726110944201: yes
    968781726110944203: no
    698781726110944201: no
    
  2. Example 2

    Input
    1260
    1395
    1435
    1530
    1827
    2187
    6880
    3421
    99
    0
    
    Expected output
    1260: yes
    1395: yes
    1435: yes
    1530: yes
    1827: yes
    2187: yes
    6880: yes
    3421: no
    99: no