Square-Ten Tree

                            Solution in C :

In C++ :



/*
*/

//#pragma comment(linker, "/STACK:16777216")
#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 256

using namespace std;

const int INF = 1e9;
const int N = 500331;

string st1, st2;

vector<int> levels;
vector<pair<int, string> > ans;

bool not_larger(vector<int> &v1, vector<int> &v2)
{
	if (v1.size() != v2.size())
	{
		return v1.size() < v2.size();
	}
	for (int i = v1.size() - 1; i >= 0; --i)
	{
		if (v1[i] != v2[i])
			return v1[i] < v2[i];
	}
	return true;
}

vector<int> get_id(string st)
{
	vector<int> res;
	reverse(st.begin(), st.end());
	for (int i = 0; i < st.size(); i++)
	{
		res.push_back(st[i] - 48);
	}
	return res;
}

string eval(vector<int> v)
{
	string res;
	res.resize(v.size());
	for (int i = 0; i < v.size(); i++)
		res[i]=(v[i] + 48);
	reverse(res.begin(), res.end());
	return res; 
}

vector<int> get_vec(vector<int> v, int ps)
{
	while (v.size() <= ps)
		v.push_back(0);
	v.push_back(0);
	v[ps]++;
	int ost = 0;
	for (int i = 0; i < v.size(); i++)
	{
		v[i] += ost;
		ost = v[i] / 10;
		v[i] %= 10;
	}
	while (v.size()>1 && v.back() == 0)
		v.pop_back();
	return v;
}

vector<int> normalize(vector<int> v, int shi)
{
	vector<int> res;
	for (int i = shi; i < v.size(); i++)
		res.push_back(v[i]);
	if (res.size() == 0)
		res.push_back(0);
	return res;
}

vector<int> get_dif(vector<int> a, vector<int> b)
{
	while (b.size() < a.size())
		b.push_back(0);
	int ost = 0;
	for (int i = 0; i < a.size(); ++i)
	{
		a[i] -= b[i];
		a[i] -= ost;
		if (a[i] < 0)
			ost = 1, a[i] += 10;
		else
			ost = 0;
	}
	while (a.size()>1 && a.back() == 0)
		a.pop_back();
	return a;
}

vector<int> renorm(vector<int> v)
{
	int ost = 0;
	for (int i = 0; i < v.size(); i++)
	{
		v[i] += ost;
		ost = v[i] / 10;
		v[i] %= 10;
	}
	v.push_back(ost);
	while (v.size()>1 && v.back() == 0)
		v.pop_back();
	return v;
}

vector<int> get_next(vector<int> v, int ps)
{
	while (v.size() <= ps)
		v.push_back(0);
	int shit = 0;
	for (int i = 0; i < ps; i++)
	{
		if (v[i] != 0)
			shit = 1;
	}
	if (shit == 0)
	{
		return renorm(v);
	}
	//cout << v.size() << "%" << ps << " " << endl;
	v[ps]++;
	for (int i = 0; i < ps; i++)
		v[i] = 0;
	return renorm(v);
}

vector<int> get_next2(vector<int> v, int ps)
{
	while (v.size() <= ps)
		v.push_back(0);
	int shit = 0;
	for (int i = 0; i < ps; i++)
	{
		if (v[i] != 0)
			shit = 1;
	}
	shit = 1;
	if (shit == 0)
	{
		return renorm(v);
	}
	v[ps]++;
	for (int i = 0; i < ps; i++)
		v[i] = 0;
	return renorm(v);
}
vector<int> min1(vector<int> v)
{
	int q = 0;
	while (v[q] == 0)
	{
		v[q] = 9;
		++q;
	}
	v[q]--;
	while (v.size() > 1 && v.back() == 0)
		v.pop_back();
	return v;
}

void show(vector<int> v)
{
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++)
		cout << v[i];
	cout << endl;
}

void norm_suf(vector<int> &v, int suf)
{
	while (v.size() < suf)
		v.push_back(0);
	for (int i = 0; i < suf; i++)
		v[i] = 0;
	while (v.size()>1 && v.back() == 0)
		v.pop_back();
	return;
}

vector<int> add(vector<int> a, vector<int> b)
{
	while (a.size() < b.size())
		a.push_back(0);
	while (b.size() < a.size())
		b.push_back(0);
	int ost = 0;
	for (int i = 0; i < a.size(); i++)
	{
		a[i] = a[i] + b[i] + ost;
		ost = a[i] / 10;
		a[i] %= 10;
	}
	a.push_back(ost);
	while (a.size()>1 && a.back() == 0)
		a.pop_back();
	return a;
}

vector<pair<int, string> > compress(vector<pair<int, string> > v)
{
	vector<pair<int, string> > res;
	pair<int, string> cur;
	cur = v[0];
	for (int i = 1; i < v.size(); i++)
	{
		if (v[i].first == v[i - 1].first)
		{
			string temp1 = cur.second;
			string temp2 = v[i].second;
			vector<int> v1 = get_id(temp1);
			vector<int> v2 = get_id(temp2);
			v1 = add(v1, v2);
			cur.second = eval(v1);
		}
		else
		{
			res.push_back(cur);
			cur = v[i];
		}
	}
	res.push_back(cur);
	return res;
}
int main(){
	//freopen("fabro.in","r",stdin);
	//freopen("fabro.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin >> st1 >> st2;

/*	st1 = "0";
	st2 = "1";
	for (int i = 1; i <= 1000000; i++)
		st2 += "0";
		*/
	levels.push_back(0);
	for (int i = 0; i <= 20; i++)
	{
		levels.push_back(1 << i);
	}

	vector<int> v1 = get_id(st1);
	v1 = min1(v1);
	vector<int> v2 = get_id(st2);

	for (int i = 0; i+1 < levels.size(); i++)
	{
		//cout << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;

		vector<int> next1 = get_next(v1, levels[i+1]);
		vector<int> next2 = v2;
		/*cout << "#" << i << endl;
		if (i < 5)
		{
			show(next1);
			show(next2);
			show(v1);
		}*/
		if (not_larger(next2, next1))
			continue;
		vector<int> V = get_dif(next1, v1);
		//cout << "@@" << endl;
		//show(V);
		//cout << "%" << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;
		V = normalize(V, levels[i]);
		//cout << "%" << i << " " << clock()*1.0 / CLOCKS_PER_SEC << endl;

		if (V.size() > 1 || V[0] != 0)
		{
			ans.push_back(make_pair(i, eval(V)));
			v1 = next1;
		}
		v1 = next1;
	}
	for (int i = levels.size()-2; i >=0; i--)
	{
		vector<int> next1 = get_next2(v1, levels[i+1]);
		vector<int> next2 = v2;

		norm_suf(next2, levels[i]);

		/*cout << "#" << i << endl;
		if (i < 5)
		{
			show(next1);
			show(next2);
			show(v1);
		}
		*/
		if (not_larger(next2, next1))
			next1 = next2;
		if (!not_larger(v1, next1))
			continue;

		vector<int> V = get_dif(next1, v1);
		V = normalize(V, levels[i]);

		if (V.size() > 1 || V[0] != 0)
		{
			ans.push_back(make_pair(i, eval(V)));
			v1 = next1;
		}
	}

	vector<int> V = get_dif(v2, v1);

	if (V.size()>1 || V[0] != 0)
		ans.push_back(make_pair(0, eval(V)));

	ans = compress(ans);

	cout << ans.size() << endl;

	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i].first << " " << ans[i].second << endl;
	}

	cin.get(); cin.get();
	return 0;
}






In C :




#include<stdio.h>

int powtwo(int x)
{
	if (x < 0)
		return 0;
	return 1 << x;
}

void subtract(char *src, char *dst, int start, int end, int borrow)
{
	while (start < end)
	{
		dst[start] += borrow;
		borrow = 0;
		if (src[start] < dst[start])
		{
			src[start] += 10;
			borrow++;
		}
		src[start] -= dst[start];
		dst[start] = 0;
		start++;
	}
}

void add(char *src, char *dst, int start, int end)
{
	int carry = 0;
	while (start < end || carry)
	{
		src[start] += dst[start] + carry;
		dst[start] = 0;
		carry = src[start] / 10;
		src[start] %= 10;
		start++;
	}
}

int main()
{
	char a[1048577] = {0}, b[1048577] = {0};
	int A, B, i, j, k, l, m, n;
	short int ansA[25] = {0}, ansB[25] = {0}, countA = 0, countB = 0;
	scanf("%s%s", a, b);
	for (A = -1; a[++A]; a[A] -= '0');
	for (B = -1; b[++B]; b[B] -= '0');
	for (i = -1; ++i < A >> 1; a[i] ^= a[A - i - 1] ^= a[i] ^= a[A - i - 1]);
	for (i = -1; ++i < B >> 1; b[i] ^= b[B - i - 1] ^= b[i] ^= b[B - i - 1]);
	if (A == B)
	{
		while (A && a[A - 1] == b[B - 1])
			a[--A] = b[--B] = 0;
	}
	else
	{
		while (A < B)
			a[A++] = 0;
	}
	if (!A)
	{
		printf("1\n0 1\n");
		return 0;
	}
	n = m = 1;
	while (A > n)
	{
		n <<= 1;
		m++;
	}
	a[0] -= 2;
	l = 0;
	for (i = -1; ++i < m - 1;)
	{
		k = powtwo(i) - powtwo(i - 1);
		for (j = -1; ++j < k; l++)
		{
			a[l] = 9 - a[l];
			a[l + 1] -= a[l] / 10;
			a[l] %= 10;
			ansA[i] = ansA[i] || a[l];
			ansB[i] = ansB[i] || b[l];
		}
		countA += ansA[i];
		countB += ansB[i];
	}
	i = powtwo(m - 2);
	subtract(b, a, i, A, 1);
	for (i--; ++i < A;)
		ansB[m - 1] = ansB[m - 1] || b[i];
	countB += ansB[--m];
	while (!ansA[m] && !ansB[m])
		m--;
	if (ansA[m] == ansB[m])
	{
		ansA[m] = 0;
		countA--;
		add(b, a, powtwo(m - 1), powtwo(m));
	}
	printf("%d", countA + countB);
	for (i = -1; ++i <= m;)
	{
		if (ansA[i])
		{
			printf("\n%d ", i);
			k = powtwo(i);
			j = powtwo(i - 1);
			while (!a[--k]);
			while (k >= j)
				printf("%c", '0' + a[k--]);
		}
	}
	while (m >= 0 && !ansB[m])
		m--;
	if (m >= 0)
	{
		printf("\n%d ", m);
		k = powtwo(m);
		j = powtwo(m - 1);
		while (!b[k])
			k--;
		while (k >= j)
			printf("%c", '0' + b[k--]);
		while (m--)
		{
			if (ansB[m])
			{
				printf("\n%d ", m);
				k = powtwo(m);
				j = powtwo(m - 1);
				while (!b[--k]);
				while (k >= j)
					printf("%c", '0' + b[k--]);
			}
		}
	}
	return 0;
}






In Java :





import java.util.*;

public class Solution {
	
	public static class Group {
		public byte[] source;
		public int power;
		
		public Group(byte[] source, int power) {
			this.source = source;
			this.power = power;
		}
		
		public void print() {

			System.out.print(powerToLevel(power));
			System.out.print(" ");
			
			boolean nonZero = false;
			for(int i = 0; i < source.length; i++) {
				int d = source[i];
				if (d != 0) nonZero = true;
				if (nonZero) System.out.print(source[i]);
			}
			
			System.out.println();
		}

	}
	
	
	public static void main(String[] args)
	{		
		String[] input = readInput();

		List<Group> groups = solve(input[0], input[1]);
		
		//Util.validate(strL, strR, groups);

		printGroups(groups);	
		
	}

	public static String[] readInput()
	{
    	try (Scanner in = new Scanner(System.in) ) {
    		String L = in.nextLine().trim();
    		String R = in.nextLine().trim();
    		return new String[]{L, R};
    	}    	
	}	

	public static void printGroups(List<Group> groups)
	{
		System.out.println(groups.size());		
		for(Group group: groups) {
			group.print();
		}		
	}

	public static List<Group> solve(String strL, String strR)
	{
		byte[] L = toArray(strL, strR.length() + 1);
		byte[] R = toArray(strR, strR.length() + 1);
		
		subtract1(L);
		
		//System.out.println(Util.toStr(L) + " " + Util.toStr(R));
		
		eraseCommonPrefix(L, R);
		
		int tens = tens(realLength(R));
		
		byte[] upper = findUpper(L, tens);
		
		byte[] dif = new byte[upper.length];
		subtract(upper, L, dif);
		
		List<Group> groups = new ArrayList<Group>();

		addGroupsL(tens, dif, groups);
		
		byte[] lower = findLower(R, tens);
		
		byte[] dif2 = new byte[R.length];
		subtract(lower, upper, dif2);

		addGroup(groups, dif2, 0, R.length - tens, tens);
		
		byte[] dif3 = new byte[R.length];
		subtract(R, upper, dif3);
		
		addGroupsR(tens, groups, dif3);			
		
		return mergeSimilar(groups);
	}

	
	public static int powerToLevel(int p) {
		
		
		int count = 0;
		while(p > 0) {
			p /= 2;
			count++;
		}
		return count;
		
	}		
	
	public static void addGroupsR(int tens, List<Group> groups, byte[] dif3)
	{
		int c = tens;
		int t = tens;
		while(t > 0) {
			int tu = Math.max(t/2, 1);
			int b = dif3.length - 1 - (c - 1);
			int e = dif3.length - 1 - (c - tu) + 1;
			addGroup(groups, dif3, b, e, t/2);
			c -= tu;
			t /= 2;
		}
	}

	public static byte[] findLower(byte[] R, int tens)
	{
		byte[] lower = new byte[R.length];		
		System.arraycopy(R, 0, lower, 0, R.length - tens);
		return lower;
	}

	public static void addGroupsL(int tens, byte[] dif, List<Group> groups)
	{
		int c = 0;
		int t = 1;
		while(t <= tens) {
			int tu = Math.max(t / 2, 1);
			int b = dif.length - 1 - (c+tu-1);
			int e = dif.length - 1 - (c) + 1;
			addGroup(groups, dif, b, e, t/2);
			c += tu;
			t *= 2;
		}			
	}

	public static void eraseCommonPrefix(byte[] L, byte[] R)
	{
		assert(L.length == R.length);
		
		for(int i = 0; i < L.length; i++) {
			if (L[i] == R[i]) {
				L[i] = 0;
				R[i] = 0;
			} else {
				break;
			}
		}
	}

	public static byte[] findUpper(byte[] L, int tens)
	{		
		byte[] upper = new byte[L.length + 1];
		
		boolean nonZero = false;
		for(int i = 0; i < tens; i++) {
			int li = L.length - 1 - i;
			if (li >= 0 && L[li] > 0) {
				nonZero = true;
			}				 
		}			
		
		int carry = nonZero ? 1 : 0; 
		for(int i = tens; i < upper.length; i++) {
			byte s = 0;
			int lindex = L.length - 1 - i;
			if (lindex >= 0) {
				s = L[lindex];
			}
			int sum = s + carry;
			upper[upper.length - 1 - i] = (byte)(sum % 10);
			carry = sum / 10; 
		}
		
		return upper;
	}

	public static int realLength(byte[] r)
	{
		int i;
		for(i = 0; i < r.length; i++) {
			if (r[i] != 0) {
				break;
			}
		}
		
		return r.length - i;
	}

	public static List<Group> mergeSimilar(List<Group> src)
	{
		List<Group> result = new ArrayList<Group>();
		
		Group current = null;
		for(int i = 0; i < src.size(); i++) {
			Group g = src.get(i);					
			if (null == current) {
				current = g;
			} else {
				if (current.power == g.power) {
					current.source = add(current.source, g.source);
				} else {
					result.add(current);
					current = g;					
				}
			}
		}
		
		if (current != null) {
			result.add(current);
		}
		
		return result;
	}

	public static void addGroup(List<Group> groups, byte[] dif, int b, int e, int power)
	{
		if (!allZeroes(dif, b, e)) {
			Group group = new Group(createCopy(dif, b, e), power);
			groups.add(group);
		}
	}

	public static byte[] createCopy(byte[] dif, int b, int e)
	{		
		byte[] result = new byte[e - b];
		System.arraycopy(dif, b, result, 0, e - b);
		return result;
	}

	public static boolean allZeroes(byte[] dif, int b, int e)
	{
		for(int i = b; i < e; i++) {
			if (dif[i] != 0)
				return false;
		}
		return true;
	}
	
	

	public static byte[] add(byte[] A, byte[] B)
	{		
		int l = Math.max(A.length, B.length) + 1;
		
		byte[] C = new byte[l];
		
		int carry = 0;
		for(int i = 0; i < l; i++) {
			int ia = A.length - 1 - i;
			int ib = B.length - 1 - i;
			int a = ia >= 0 ? A[ia] : 0;
			int b = ib >= 0 ? B[ib] : 0;
			int c = a + b + carry;
			carry = c / 10;
			
			int ic = C.length - 1 - i;
			C[ic] = (byte)(c % 10);
		}
		
		return C;
		
	}


	public static void subtract(byte[] A, byte[] B, byte[] C)
	{
		
		int borrow = 0;
		for(int i = 0; i < A.length; i++) {
			int a = A[A.length - 1 - i] - borrow;
			
			int b;
			if (i < B.length) 
				b = B[B.length - 1 - i];
			else 
				b = 0;
			
			if (b > a) {
				borrow = 1;
				a += 10;
			} else {
				borrow = 0;
			}
			
			C[C.length - 1 - i] = (byte)(a - b);
		}
		
		
	}

	/**
	 * return largest x such that 10^x <= s
	 */
	public static int tens(int len)
	{
		int x = 1;
		int c = len - 1;
		while(c > 0) {
			c /= 2;
			x *= 2;
		}
		return x/2;
	}

	public static byte[] toArray(String s, int len)
	{
		byte[] result = new byte[len];
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(s.length() - 1 - i);
			assert(c >= '0' && c <= '9');
			int d = c - '0';
			result[result.length - 1 - i] = (byte)d;
		}
		return result;
	}

	/**
	 * s = all zeroes not allowed
	 */
	public static void subtract1(byte[] s)
	{		
		for(int i = s.length - 1; i >= 0; i--) {
			int d = s[i];
			if (0 == d) {
				s[i] = 9; 
			} else {
				s[i]--;
				break;
			}
		}		
	}

}






In python3 :




# work with big numbers as strings
L = input()
R = input()

# look for largest possible level
d = len(R)
level = 0
n = 1
tree = [n] # chunk dimension
while d >= n + 1:
    tree.append(n)
    level += 1
    n = 2 ** level

# go backwards from largest level
def breakdown(N, k):
    if k == 0:
        return [int(N)]

    div = tree[k]
    chunks = breakdown(N[-div:], k - 1)
    chunks.append(N[:-div].lstrip('0') or 0)
    return chunks

divL = breakdown(L, level)
divR = breakdown(R, level)
seq = []

# add up to higher level for L
carry = 0
for k, n in enumerate(map(int, divL)):
    if k == 0:
        carry = -1 # add up lowest number

    n += carry
    carry = 0

    if k < level:
        if n > 0:
            n = 10 ** tree[k] - n
            carry = 1
        elif n < 0:
            n = 1 # if lowest was zero

        seq.append((k, n))

# sum up last level of L and R
if n != 0:
    divR[k] = int(divR[k]) - n
    while divR[-1] == 0:
        del divR[-1]
        n = seq.pop()[1]
        if n != 0:
            divR[-1] = int(divR[-1]) + n

# add R in reversed order
seq.extend(reversed(list(enumerate(divR))))

# exclude empty levels
seq = [s for s in seq if s[1] != 0]
print(len(seq))

for s in seq:
    print(*s)