Minimizing Circular Overlap of Binary Sequences

Given non‐negative integers N, K, and L, construct two binary (0–1) sequences S and T of length N such that:

• The sequence S contains exactly K ones and T contains exactly L ones.
• Define $$ f(S,T)=\max_{r}\;\sum_{i=1}^{N} S_i\,\mathrm{and}\,T_{(i+r)\,\bmod \; N}, $$ where and denotes the bitwise AND operation and the maximum is taken over all cyclic shifts (rotations). The objective is to construct S and T so that f(S,T) is minimized over all valid choices. Note that by an averaging argument the optimum is at least $$ \Big\lceil \frac{K\,L}{N} \Big\rceil. $$

A common approach is to distribute the ones uniformly along the circle. In our solution, we choose the positions for the ones in S by setting $$S\bigl[\;\lfloor \frac{(i+0.5)N}{K}\rfloor \bmod N \bigr] = 1 \quad\text{for}\; i=0,\dots,K-1, $$

and for T we use a similar uniform distribution but with a constant offset (here, 1) to avoid complete alignment:

$$T\bigl[\;\Bigl(\lfloor \frac{(i+0.5)N}{L}\rfloor+1\Bigr) \bmod N\bigr] = 1 \quad\text{for}\; i=0,\dots,L-1. $$

It can be shown that with this construction the maximum overlap over all cyclic shifts is as low as possible (namely, (\lceil K,L/N\rceil)).

inputFormat

The input consists of a single line containing three integers N, K, and L separated by spaces.

\(0 \le K, L \le N\) and N is a positive integer.

outputFormat

Output two lines. The first line is the binary sequence S of length N and the second line is the binary sequence T of length N.

sample

5 2 2

01010
00101

</p>