F - Addition and Andition

Contest Duration: 2018-06-03(Sun) 12:00 - 2018-06-03(Sun) 14:10 (local time) (130 minutes) Back to Home

F - Addition and Andition Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $2400$ 点

問題文

高橋君と青木君は計算をするのが大好きです。そこで、二人は計算をして遊ぶことにしました。

まず二人は正整数を $1$ つずつ用意しました。高橋君の用意した数は $X$ 、青木君の用意した数は $Y$ です。そして、以下の手順を $K$ 回繰り返すことで、計算を楽しむことにしました。

高橋君の持っている数と青木君の持っている数の bitwise AND を計算し、それを $Z$ とする。
そして、高橋君と青木君の持っている数それぞれに $Z$ を足す。

しかし、計算の大好きな二人にもこの計算は酷です。そこで彼らの代わりに、高橋君が最終的に持つことになる数と、青木君が最終的に持つことになる数を求めてあげてください。

ただし、入出力は $2$ 進数表記で行われることに注意してください。特に、 $X,Y$ はそれぞれ長さ $N,M$ の0,1 のみからなる文字列 $S,T$ として入力され、 $S,T$ の先頭の文字は 1 であることが保証されています。

制約

$1 ≦ K ≦ 10^6$
$1 ≦ N,M ≦ 10^6$
$S,T$ の先頭の文字は 1 である。

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$   $K$ 
 $S$ 
 $T$

出力

一行目には高橋君の最終的に持つことになる数を、二行目には青木君の最終的に持つことになる数を出力せよ。ただし、それらを $2$ 進数表記で表し、先頭の文字が 1 であるような 0,1 のみからなる文字列として出力せよ。

入力例 1Copy

Copy

2 3 3
11
101

出力例 1Copy

Copy

10000
10010

各操作後の $X,Y$ の値は以下のようになります。

一回目の操作後は $(X,Y)=(4,6)$ になる。
二回目の操作後は $(X,Y)=(8,10)$ になる。
三回目の操作後は $(X,Y)=(16,18)$ になる。

入力例 2Copy

Copy

5 8 3
10101
10101001

出力例 2Copy

Copy

100000
10110100

入力例 3Copy

Copy

10 10 10
1100110011
1011001101

出力例 3Copy

Copy

10000100000010001000
10000100000000100010

Score : $2400$ points

Problem Statement

Takahashi and Aoki love calculating things, so they will play with numbers now.

First, they came up with one positive integer each. Takahashi came up with $X$ , and Aoki came up with $Y$ . Then, they will enjoy themselves by repeating the following operation $K$ times:

Compute the bitwise AND of the number currently kept by Takahashi and the number currently kept by Aoki. Let $Z$ be the result.
Then, add $Z$ to both of the numbers kept by Takahashi and Aoki.

However, it turns out that even for the two math maniacs this is just too much work. Could you find the number that would be kept by Takahashi and the one that would be kept by Aoki eventually?

Note that input and output are done in binary. Especially, $X$ and $Y$ are given as strings $S$ and $T$ of length $N$ and $M$ consisting of 0 and 1, respectively, whose initial characters are guaranteed to be 1.

Constraints

$1 ≤ K ≤ 10^6$
$1 ≤ N,M ≤ 10^6$
The initial characters of $S$ and $T$ are 1.

Input

Input is given from Standard Input in the following format:

 $N$   $M$   $K$ 
 $S$ 
 $T$

Output

In the first line, print the number that would be kept by Takahashi eventually; in the second line, print the number that would be kept by Aoki eventually. Those numbers should be represented in binary and printed as strings consisting of 0 and 1 that begin with 1.

Sample Input 1Copy

Copy

2 3 3
11
101

Sample Output 1Copy

Copy

10000
10010

The values of $X$ and $Y$ after each operation are as follows:

After the first operation: $(X,Y)=(4,6)$ .
After the second operation: $(X,Y)=(8,10)$ .
After the third operation: $(X,Y)=(16,18)$ .

Sample Input 2Copy

Copy

5 8 3
10101
10101001

Sample Output 2Copy

Copy

100000
10110100

Sample Input 3Copy

Copy

10 10 10
1100110011
1011001101

Sample Output 3Copy

Copy

10000100000010001000
10000100000000100010