CodeForces 194E(math）

偏执的太偏执、 2022-06-02 05:12 145阅读 0赞

问题描述:

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 ai ≠ bi, where aiis the i\-th symbol of string a, bi 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 s1, s2, s3 and s4 were written. Each string si 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 ![e80269daeb18b0b48930436124080625_v_1514871673][].

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.

Input

The first line contains space-separated integers h(s1, s2), h(s1, s3), h(s1, s4). The second line contains space-separated integers h(s2, s3) and h(s2, s4). The third line contains the single integer h(s3, s4).

All given integers h(si, sj) are non-negative and do not exceed 105. It is guaranteed that at least one number h(si, sj) is positive.

Output

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.

Input

4 4 4
    4 4
    4

Output

6
    aaaabb
    aabbaa
    bbaaaa
    bbbbbb

题目题意:题目给我们我们h(s1,h2) h(s1,h3) h(s1,s4),,,,,,等等，问我们能不能构成最短的四个串

题目分析:(这道题目问了学校的一个大佬的，他给我讲了方法，当时听了很膜拜！！！）

因为每个串的长度有相同，那么我们竖着看，就有7种情况，可以表示所有的情况

![Center][]

题目给的6个数字其实是六个方程

![Center 1][]

还差一个方程，所以我们就枚举x7,然后算出x1到x6，我们保存x1+,,,x7最小值。

方程有点麻烦，而且除法记得判断一下是否可以整除，这也是判断是否存在的重要参数

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    const int maxn=1e5+10;
    int h[10],x[10],ans[10];
    char str[10][50]={"","aaab","aaba","abaa","baaa","abab","abba","aabb"};
    int main()
    {
        bool flag=false;
        for (int i=1;i<=3;i++) {
            scanf("%d",&h[i]);
        }
        scanf("%d%d%d",&h[4],&h[5],&h[6]);
        int Min=0x3f3f3f3f;
        for ( x[7]=0;x[7]<=maxn;x[7]++) {
            if ((h[5]+h[1]-h[3])%2==0) x[1]=h[5]-x[7]-(h[5]+h[1]-h[3])/2;
            else continue;
            if ((h[4]+h[1]-h[2])%2==0) x[2]=h[4]-x[7]-(h[4]+h[1]-h[2])/2;
            else continue;
            if (x[1]<0||x[2]<0) continue;
            if (((h[4]+h[1]-h[2])/2-(h[5]+h[1]-h[3])/2+h[6]-x[1]-x[2])%2==0)
                x[5]=((h[4]+h[1]-h[2])/2-(h[5]+h[1]-h[3])/2+h[6]-x[1]-x[2])/2;
            else continue;
            x[6]=h[6]-x[1]-x[2]-x[5];
            if (x[5]<0||x[6]<0) continue;
            x[3]=(h[5]+h[1]-h[3])/2-x[6];
            x[4]=h[1]-x[3]-x[5]-x[6];
            if (x[3]<0||x[4]<0) continue;
            int res=0;
            for (int i=1;i<=7;i++) {
                res+=x[i];
            }
            if (Min>res) {
                flag=true;
                for (int i=1;i<=7;i++) {
                    ans[i]=x[i];
                }
                Min=res;
            }
        }
        //printf("%d\n",Min);
        if (flag==false) {
            printf("-1\n");
            return 0;
        }
        printf("%d\n",Min);
        for (int i=0;i<4;i++) {
            for (int j=1;j<=7;j++) {
                for (int k=1;k<=ans[j];k++) {
                    printf("%c",str[j][i]);
                }
            }
            printf("\n");
        }
        return 0;
    }

[e80269daeb18b0b48930436124080625_v_1514871673]: https://odzkskevi.qnssl.com/e80269daeb18b0b48930436124080625?v=1514871673
[Center]: /images/20220602/ed01bdf919eb42659770b3d61a47fa75.png
[Center 1]: /images/20220602/bca8b730179a463b9b6e39aa05c1378c.png