Educational Codeforces Round 70 A topic You Are Given Two Binary Strings…

subject ：http://codeforces.com/contest/1202/problem/A

General meaning ：

Here are two binary numbers x,y, Let you choose a number k, There is a formula sk = x + y * 2^k , Definition revk yes sk In reverse order , Seeking energy bring revk Dictionary order is the smallest Of k value .

Ideas ：

The topic looks very difficult at first glance, Yazi , Actually 2^k It has a wonderful use , From a binary point of view , In fact, you chose k What is the value , Is to make y It's just how many bits to the left . Then we can find out , In fact, just let y The last one in the string 1( Left to right ), De alignment x The nearest one in the string 1 Just fine . Here's an example ：

Input x by 10001, y by 110,

We can see y The last 1 Aim at x Of 0, Because of our y The string can only be moved left , That is to add 0. and y The last one in the string 1 distance x String the nearest one 1 Still bad 3 distance , So we put y Shift the string left 3 position , That is to say k Value taking 3 You can see the following ：

At this time, we get it through the formula revk It's the smallest dictionary order .

Code section ：

#include<iostream>
#include<string.h>
#include<cstdio>
#include<cstdlib>
using namespace std;

int main() {
    
	int t;
	while(~scanf("%d",&t)) {
    
		while(t--) {
    
			char s1[100005], s2[100005];
			scanf("%s %s",s1,s2);
			int lens1 = strlen(s1);
			int lens2 = strlen(s2);
			int add1, add2;
			for(int i = lens2 - 1; i >= 0; i--) {
    
				if(s2[i] == '1') {
    
					add2 = i;
					break;
				}
			}
			int count = 0;
			for(int i = add2 + lens1 - lens2; i >= 0; i--) {
    
				if(s1[i] != '1')
					count++;
				else 
					break;
			}
			printf("%d\n", count);
		}
	}
	return 0;
}