**Problem statement**

A numeric string, , is beautiful if it can be split into a sequence of two or more positive integers, , satisfying the following conditions:

- for any (i.e., each element in the sequence is more than the previous element).
- No contains a leading zero. For example, we can split into the sequence , but it is not beautiful because and have leading zeroes.
- The contents of the sequence cannot be rearranged. For example, we can split into the sequence , but it is not beautiful because it breaks our first constraint (i.e., ).

The diagram below depicts some beautiful strings:

You must perform queries, where each query consists of some string . For each query, print whether or not the string is beautiful on a new line. If it’s beautiful, print `YES x`

, where is the first number of the increasing sequence (if there are multiple such values of , choose the smallest); otherwise, print `NO`

instead.

**Input Format**

The first line contains an integer denoting (the number of strings to evaluate).

Each of the subsequent lines contains some string for a query.

**Constraints**

Each character in is a decimal digit from to (inclusive).

**Output Format**

For each query, print its answer on a new line (i.e., either `YES x`

where is the smallest first number of the increasing sequence, or `NO`

).

**Sample Input 0**

1 2 3 4 5 6 7 8 |
7 1234 91011 99100 101103 010203 13 1 |

**Sample Output 0**

1 2 3 4 5 6 7 |
YES 1 YES 9 YES 99 NO NO NO NO |

**Explanation 0**

The first three numbers are beautiful (see the diagram above). The remaining numbers are not beautiful:

For , all possible splits violate the first and/or second conditions.

For , it starts with a zero so all possible splits violate the second condition.

For , the only possible split is , which violates the first condition.

For , there are no possible splits because only has one digit.

**Solution**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
public class SeparateTheNumbers { /** * Convert String to int */ private static long strToLong(String str) { long ans = 0; double d = str.length() - 1; for (int i = 0; i < str.length(); i++) { long digit = (long) (str.charAt(i) - '0'); if (digit != 0l) { long pow = (long) Math.pow(10, d); ans += digit * pow; } d--; } return ans; } private static long solve(String str, int startIdx, long prevNum, long diff) { if (str.length() == 1) { return -1; } if (startIdx == str.length() && diff == 1) { return prevNum; } else { if (startIdx == str.length() || str.charAt(startIdx) == '0') { return -1; } for (int len = 1; len <= str.length() - startIdx; len++) { String nextSubStr = str.substring(startIdx, startIdx + len); long next = strToLong(nextSubStr); long result = -1; if (next - prevNum == 1 || startIdx == 0) { result = solve(str, startIdx + len, next, next - prevNum); } if (result > 0) { return next; } } return -1; } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt")); Scanner in = new Scanner(System.in); int queries = in.nextInt(); for (int q = 0; q < queries; q++) { String str = in.next(); long res = solve(str, 0, 0, 0); System.out.println(res > 0 ? "YES " + res : "NO"); } } } |