codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1202A.md (2934B)


      1 Source: https://codeforces.com/problemset/problem/1202/A
      2 
      3 A. You Are Given Two Binary Strings...
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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$.
     22 
     23 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).
     24 
     25 It's guaranteed that, with given constraints, $k$ exists and is finite.
     26 
     27 Input
     28 
     29 The first line contains a single integer $T$ ($1 \le T \le 100$) — the number of queries.
     30 
     31 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.
     32 
     33 The second line contains one binary string $y$, consisting of no more than $10^5$ characters. Each character is either 0 or 1.
     34 
     35 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$.
     36 
     37 Output
     38 
     39 Print $T$ integers (one per query). For each query print such $k$ that $rev_k$ is lexicographically minimal.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 1010
     48 11
     49 10001
     50 110
     51 1
     52 1
     53 1010101010101
     54 11110000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1
     61 3
     62 0
     63 0
     64 ```
     65 
     66 Note
     67 
     68 The first query was described in the legend.
     69 
     70 In the second query, it's optimal to choose $k = 3$. The $2^3 = 1000_2$ so $s_3 = 10001_2 + 110_2 \cdot 1000_2 = 10001 + 110000 = 1000001$ and $rev_3 = 1000001$. For example, if $k = 0$, then $s_0 = 10111$ and $rev_0 = 11101$, but $rev_3 = 1000001$ is lexicographically smaller than $rev_0 = 11101$.
     71 
     72 In the third query $s_0 = 10$ and $rev_0 = 01$. For example, $s_2 = 101$ and $rev_2 = 101$. And $01$ is lexicographically smaller than $101$.
     73 
     74 The quote from Wikipedia: "To determine which of two strings of characters comes when arranging in lexicographical order, their first letters are compared. If they differ, then the string whose first letter comes earlier in the alphabet comes before the other string. If the first letters are the same, then the second letters are compared, and so on. If a position is reached where one string has no more letters to compare while the other does, then the first (shorter) string is deemed to come first in alphabetical order."