306467: CF1202A. You Are Given Two Binary Strings...
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
You Are Given Two Binary Strings...
题意翻译
题目描述 给你两个二进制字符串$x$和$y$,将$y$左移$k$位,再与$x$相加,得到字符串$s_k$,最后将其反转得到$res_k$。求当$res_k$字典序最小时的$k$。 $PS:s_k = f(x) + f(y) * 2 ^ k$($f(a)$为$a$的十进制形式) 输入格式 第一行为一个整数$T$——数据组数 接下来$2T$行每两行为一组数据,第一行为二进制字符串$x$,第二行为二进制字符串$y$。 字符串的长度均小于$10^5$且只由$1$或$0$构成,$1≤f(x)≤f(y)$ 输出格式 共$T$行,每行一个整数$k$,即当$res_k$字典序最小时的$k$。题目描述
You are given two binary strings $ x $ and $ y $ , which are binary representations of some two integers (let's denote these integers as $ f(x) $ and $ f(y) $ ). You can choose any integer $ k \ge 0 $ , calculate the expression $ s_k = f(x) + f(y) \cdot 2^k $ and write the binary representation of $ s_k $ in reverse order (let's denote it as $ rev_k $ ). For example, let $ x = 1010 $ and $ y = 11 $ ; you've chosen $ k = 1 $ and, since $ 2^1 = 10_2 $ , so $ s_k = 1010_2 + 11_2 \cdot 10_2 = 10000_2 $ and $ rev_k = 00001 $ . For given $ x $ and $ y $ , you need to choose such $ k $ that $ rev_k $ is lexicographically minimal (read notes if you don't know what does "lexicographically" means). It's guaranteed that, with given constraints, $ k $ exists and is finite.输入输出格式
输入格式
The first line contains a single integer $ T $ ( $ 1 \le T \le 100 $ ) — the number of queries. Next $ 2T $ lines contain a description of queries: two lines per query. The first line contains one binary string $ x $ , consisting of no more than $ 10^5 $ characters. Each character is either 0 or 1. The second line contains one binary string $ y $ , consisting of no more than $ 10^5 $ characters. Each character is either 0 or 1. It's guaranteed, that $ 1 \le f(y) \le f(x) $ (where $ f(x) $ is the integer represented by $ x $ , and $ f(y) $ is the integer represented by $ y $ ), both representations don't have any leading zeroes, the total length of $ x $ over all queries doesn't exceed $ 10^5 $ , and the total length of $ y $ over all queries doesn't exceed $ 10^5 $ .
输出格式
Print $ T $ integers (one per query). For each query print such $ k $ that $ rev_k $ is lexicographically minimal.
输入输出样例
输入样例 #1
4
1010
11
10001
110
1
1
1010101010101
11110000
输出样例 #1
1
3
0
0