Separate the Numbers


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:

Perform  queries where each query consists of some integer string . For each query, print whether or not the string is beautiful on a new line. If it is 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.

Function Description

Complete the separateNumbers function in the editor below.

separateNumbers has the following parameter:

s: an integer value represented as a string
Prints
- string: Print a string as described above. Return nothing.

Input Format

The first line contains an integer q, the number of strings to evaluate.
Each of the next q lines contains an integer string s to query.

Constraints

1  <=   q  <=  10
1  <=  | s |  <=  32



Solution :



title-img


                            Solution in C :

In  C++  :








#pragma comment(linker, "/STACK:1000000000")
#include <cstdio>
#include <iostream>
#include <ctime>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#include <fstream>
#include <deque>
#include <stack>
#include <climits>
#include <string>
#include <queue>
#include <memory.h>
#include <map>
#include <unordered_map>

#define ll long long
#define ld double
#define pii pair <ll, ll>
#define mp make_pair

using namespace std;

int main() {
int q;

cin >> q;

while (q--) {
string s;

cin >> s;

if (s[0] == '0') {
cout << "NO\n";
continue;
}

ll now = 0;

bool st = false;

for (int i = 0; i < (int)s.size(); i++) {
now *= 10;
now += s[i] - '0';

ll res = 0;

if (s[i + 1] == '0') {
continue;
}

int cnt = 1;

for (int j = i + 1; j < (int)s.size(); j++) {
res *= 10;
res += s[j] - '0';

if (res == now + cnt) {
if (j + 1 == (int)s.size()) {
st = true;
break;
}

if (s[j + 1] == '0') {
break;
}

res = 0;
cnt++;
}
}

if (st) {
break;
}
}

if (st) {
cout << "YES " << now << endl;
} else {
cout << "NO\n";
}
}

return 0;
}









In  Java  :






import java.io.*;
import java.util.StringTokenizer;


public class Main {
private void solve() {
int n = rw.nextInt();
main:
for (int i = 0; i < n; ++i) {
String s = rw.next();
if (s.startsWith("0") || s.length() == 1) {
rw.println("NO");
continue;
}
long x, cur;
cy:
for (int j = 1; j <= s.length() / 2; ++j) {
x = Long.parseLong(s.substring(0, j));
cur = x + 1;
int c = j;
while (c < s.length()) {
String p = String.valueOf(cur);
cur += 1;
if (s.startsWith(p, c)) {
c += p.length();
} else {
continue cy;
}
}
rw.println("YES" + " " + x);
continue main;
}
rw.println("NO");
}

}

private RW rw;
private String FILE_NAME = "file";

public static void main(String[] args) {
new Main().run();
}

private void run() {
rw = new RW(FILE_NAME + ".in", FILE_NAME + ".out");
solve();
rw.close();
}

private class RW {
private StringTokenizer st;
private PrintWriter out;
private BufferedReader br;
private boolean eof;

RW(String inputFile, String outputFile) {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));

File f = new File(inputFile);
if (f.exists() && f.canRead()) {
try {
br = new BufferedReader(new FileReader(inputFile));
out = new PrintWriter(new FileWriter(outputFile));
} catch (IOException e) {
e.printStackTrace();
}
}
}

private String nextLine() {
String s = "";
try {
s = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return s;
}

private String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
eof = true;
return "-1";
}
}
return st.nextToken();
}

private long nextLong() {
return Long.parseLong(next());
}

private int nextInt() {
return Integer.parseInt(next());
}

private void println() {
out.println();
}

private void println(Object o) {
out.println(o);
}

private void print(Object o) {
out.print(o);
}

private void close() {
try {
br.close();
} catch (IOException e) {
e.printStackTrace();
}
out.close();
}
}
}









In    C  :






#include <stdio.h>
#include <string.h>


typedef unsigned long long int Long;
char s[33];
int q;
Long x;

int isZeroLead(int i) { return s[i] == '0'; }
Long read(int i, int sz) {
    char *pt = s + i;
    Long ans = 0;
    while(sz-- && *pt) {
        ans = ans*10 + (*pt - '0');
        pt++;
    }
    return ans;
}

int digs(Long x) {
    int ll = 0;
    while(x) {
        ll++;
        x /= 10;
    }
    return ll;
}

int check(Long fst, int len) {
    Long last = fst, curr;
    int lsz = digs(fst);
    for(int i = lsz; i < len; i += lsz) {
        if(isZeroLead(i)) return 0;
        if(digs(last + 1) != digs(last)) { lsz++; }
        
        curr = read(i, lsz);
        if(curr - last != 1) return 0;
        last = curr;
    }
    
    return 1;
}

int main() {
    scanf("%d",&q);
    while(q--) {
        scanf("%s", s);
        Long x = -1, fst;
        for(int i = 1, len = strlen(s); i <= (len>>1); i++) {
            fst = read(0, i);
            if(check(fst, len)) {
                x = fst;
                break;
            }
        }
        
        if(x == -1) puts("NO");
        else printf("YES %lld\n", x);
    }
    
    return 0;
}








In   Python3 :






for _ in range(int(input())):
    s = input().strip()
    n = len(s)
    x = ''
    for i in s[:-1]:
        x += i
        y = int(x)
        z = ''
        while len(z) < n:
            z += str(y)
            y += 1
        if n == len(z) and z == s:
            print("YES", x)
            break
    else:
        print("NO")
                        








View More Similar Problems

Polynomial Division

Consider a sequence, c0, c1, . . . , cn-1 , and a polynomial of degree 1 defined as Q(x ) = a * x + b. You must perform q queries on the sequence, where each query is one of the following two types: 1 i x: Replace ci with x. 2 l r: Consider the polynomial and determine whether is divisible by over the field , where . In other words, check if there exists a polynomial with integer coefficie

View Solution →

Costly Intervals

Given an array, your goal is to find, for each element, the largest subarray containing it whose cost is at least k. Specifically, let A = [A1, A2, . . . , An ] be an array of length n, and let be the subarray from index l to index r. Also, Let MAX( l, r ) be the largest number in Al. . . r. Let MIN( l, r ) be the smallest number in Al . . .r . Let OR( l , r ) be the bitwise OR of the

View Solution →

The Strange Function

One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting

View Solution →

Self-Driving Bus

Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever

View Solution →

Unique Colors

You are given an unrooted tree of n nodes numbered from 1 to n . Each node i has a color, ci. Let d( i , j ) be the number of different colors in the path between node i and node j. For each node i, calculate the value of sum, defined as follows: Your task is to print the value of sumi for each node 1 <= i <= n. Input Format The first line contains a single integer, n, denoti

View Solution →

Fibonacci Numbers Tree

Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T

View Solution →