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

#define MaxN 1024

int main() {
	char Cislo1[MaxN+1],Cislo2[MaxN+1],Cislo3[MaxN+6];
	int Fib1[MaxN+7],Fib2[MaxN+7],Fib3[MaxN+7];// první 2 číslice jsou rezervovány pro cifry 0 a $-1$
	int index,i,Delka1,Delka2,Delka;		
	printf("Zadej číslo 1:");scanf("%s",Cislo1);
	printf("Zadej číslo 2:");scanf("%s",Cislo2);
	Delka1 = strlen(Cislo1);Delka2 = strlen(Cislo2);
	Delka = ((Delka1<Delka2)?Delka2:Delka1) + 7;
	for (index = 0;index < Delka;index++) 
		Fib1[index] = Fib2[index] = 0;
	for (index = 0;index < Delka1;index++)
		Fib1[Delka1 - index + 1] = (Cislo1[index] == '1');
	for (index = 0;index < Delka2;index++)
		Fib2[Delka2 - index + 1] = (Cislo2[index] == '1');		// a je převedeno na pole
	for (index = 0;index < Delka;index ++)
		Fib3[index] = Fib1[index] + Fib2[index];				// sečteme po bitech
	index = Delka - 6;											// poslední zajímavá cifra
	while (index > 1)					// index je pozice kurzoru
		if ((Fib3[index] >= 1) && (Fib3[index + 1] == 1)) {
			Fib3[index] -= 1;
			Fib3[++index] = 0;
			Fib3[++index] = 1;
		} else
			if (Fib3[index] >= 2) {
				Fib3[index] -= 2;
				Fib3[index - 2] += 1;
				Fib3[++index] = 1;
			} else 
				index--;				// a je sečteno, teď už se jen zbavit cifer 0 a -1
	if (Fib3[1] && !Fib3[2]) {
		Fib3[1] = 0;
		Fib3[2] = 1;		// prohodím cifry 0 a 1
		index = 2;
	} else
		index = 1;
	while (Fib3[index] && Fib3[index + 1]) {
		Fib3[index] = 0;
		Fib3[++index] = 0;
		Fib3[++index] = 1;		// vyhazujeme dvojice jedniček, dokud to jde
	}
	index = Delka-1;			// poslední definovaná cifra
	while ((index > 2) && (Fib3[index] == 0)) 
		index--;				// a odbouráme nuly
	i = 0;
	for (;index > 1;index--) 
		Cislo3[i++] = (Fib3[index])?'1':'0';
	Cislo3[i] = '\0';		// konec řetězce
	printf("Součet je: %s\n",Cislo3);
	return 0;
}