Room Number
InterviewTime limit1sMemory limit256 MB
Find natural numbers A and B with A + B = N, no leading zeros, and no digit repeated across both numbers, minimizing A.
- Level
Medium6 of 10
- Topics
- Brute force, Math, Implementation, Backtracking
- Solved
- No attempts yet
Problem
Taekhee moved into room of the Yonsei Building in Yonsei-dong. He wants to put the room number on his door with digit stickers, but the sticker set holds exactly one sticker for each digit from 0 to 9. If the same digit appears twice in the room number, he cannot spell it out.
Instead of spelling itself, Taekhee decided to put up two natural numbers and with . Every digit used in and must be different, so each digit from 0 to 9 can appear at most once across the two numbers. The stickers have an unusual shape, so a 6 cannot be turned upside down and used as a 9. Both and are natural numbers written without leading zeros.
Take the room number 555. The split 123 + 432 fails because 2 and 3 are each used twice, and 99 + 456 fails because 9 is used twice. The split 512 + 43 uses no digit twice, so it works. A room number usually admits several such splits.
The room number is fairly large, so Taekhee cannot find and quickly. Help him.
Input
The first line contains the room number . ()
Output
If no and satisfy the condition, print -1 on the first line.
Otherwise, among all pairs that satisfy the condition, take the one with the smallest and print it in the form A + B, that is, , a space, a plus sign, a space, then . Since , exactly one answer follows this rule.