301023: CF193C. Hamming Distance

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Hamming Distance

题意翻译

定义函数 $h(s,t)$ 为: - 两个长度相等的字符串 $s,t$ 中满足 $s_i \neq t_i$ 的 $i$ 的个数。 现在给出六个数 $a,b,c,d,e,f$,要你构造出**四个长度相等的仅由字符 $\texttt{ab}$ 构成的字符串** $s_1,s_2,s_3,s_4$,满足: - $h(s_1,s_2)=a$,$h(s_1,s_3)=b$,$h(s_1,s_4)=c$,$h(s_2,s_3)=d$,$h(s_2,s_4)=e$,$h(s_3,s_4)=f$。 - 它们长度尽可能小。 构造出一个合法的方案,无解输出 $-1$。 数据范围 $0 \leq a,b,c,d,e,f \leq 10^5$,$\max\{a,b,c,d,e,f\}>0$。 ### 输入格式 第一行三个整数 $a, b, c$; 第二行两个整数 $d, e$; 第三行一个整数 $f$。 ### 输出格式 第一行,一个整数表示字符串长度 $len$。 接下来四行,每行一个长度为 $len$ 的字符串 $s_i$ 本题包含 SPJ,所以不用担心多解的问题

题目描述

Hamming distance between strings $ a $ and $ b $ of equal length (denoted by $ h(a,b) $ ) is equal to the number of distinct integers $ i $ $ (1<=i<=|a|) $ , such that $ a_{i}≠b_{i} $ , where $ a_{i} $ is the $ i $ -th symbol of string $ a $ , $ b_{i} $ is the $ i $ -th symbol of string $ b $ . For example, the Hamming distance between strings "aba" and "bba" equals $ 1 $ , they have different first symbols. For strings "bbba" and "aaab" the Hamming distance equals $ 4 $ . John Doe had a paper on which four strings of equal length $ s_{1} $ , $ s_{2} $ , $ s_{3} $ and $ s_{4} $ were written. Each string $ s_{i} $ consisted only of lowercase letters "a" and "b". John found the Hamming distances between all pairs of strings he had. Then he lost the paper with the strings but he didn't lose the Hamming distances between all pairs. Help John restore the strings; find some four strings $ s'_{1} $ , $ s'_{2} $ , $ s'_{3},s'_{4} $ of equal length that consist only of lowercase letters "a" and "b", such that the pairwise Hamming distances between them are the same as between John's strings. More formally, set $ s'_{i} $ must satisfy the condition ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF193C/3413638c969044ade5763c6910513ebbb84f06f5.png). To make the strings easier to put down on a piece of paper, you should choose among all suitable sets of strings the one that has strings of minimum length.

输入输出格式

输入格式


The first line contains space-separated integers $ h(s_{1},s_{2}) $ , $ h(s_{1},s_{3}) $ , $ h(s_{1},s_{4}) $ . The second line contains space-separated integers $ h(s_{2},s_{3}) $ and $ h(s_{2},s_{4}) $ . The third line contains the single integer $ h(s_{3},s_{4}) $ . All given integers $ h(s_{i},s_{j}) $ are non-negative and do not exceed $ 10^{5} $ . It is guaranteed that at least one number $ h(s_{i},s_{j}) $ is positive.

输出格式


Print -1 if there's no suitable set of strings. Otherwise print on the first line number $ len $ — the length of each string. On the $ i $ -th of the next four lines print string $ s'_{i} $ . If there are multiple sets with the minimum length of the strings, print any of them.

输入输出样例

输入样例 #1

4 4 4
4 4
4

输出样例 #1

6
aaaabb
aabbaa
bbaaaa
bbbbbb

Input

题意翻译

定义函数 $h(s,t)$ 为: - 两个长度相等的字符串 $s,t$ 中满足 $s_i \neq t_i$ 的 $i$ 的个数。 现在给出六个数 $a,b,c,d,e,f$,要你构造出**四个长度相等的仅由字符 $\texttt{ab}$ 构成的字符串** $s_1,s_2,s_3,s_4$,满足: - $h(s_1,s_2)=a$,$h(s_1,s_3)=b$,$h(s_1,s_4)=c$,$h(s_2,s_3)=d$,$h(s_2,s_4)=e$,$h(s_3,s_4)=f$。 - 它们长度尽可能小。 构造出一个合法的方案,无解输出 $-1$。 数据范围 $0 \leq a,b,c,d,e,f \leq 10^5$,$\max\{a,b,c,d,e,f\}>0$。 ### 输入格式 第一行三个整数 $a, b, c$; 第二行两个整数 $d, e$; 第三行一个整数 $f$。 ### 输出格式 第一行,一个整数表示字符串长度 $len$。 接下来四行,每行一个长度为 $len$ 的字符串 $s_i$ 本题包含 SPJ,所以不用担心多解的问题

加入题单

上一题 下一题 算法标签: