[C++知识库]coderforces div2 2022/3/12

A

A. Madoka and Math Dad

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Madoka finally found the administrator password for her computer. Her father is a well-known popularizer of mathematics, so the password is the answer to the following problem.

Find the maximum decimal number without zeroes and with no equal digits in a row, such that the sum of its digits is?nn.

Madoka is too tired of math to solve it herself, so help her to solve this problem!

Input

Each test contains multiple test cases. The first line contains a single integer?tt?(1≤t≤10001≤t≤1000)?— the number of test cases. Description of the test cases follows.

The only line of each test case contains an integer?nn?(1≤n≤10001≤n≤1000)?— the required sum of the digits.

Output

For each test case print the maximum number you can obtain.

Example

input

Copy

5
1
2
3
4
5

output

Copy

1
2
21
121
212

Note

The only numbers with the sum of digits equal to?22?without zeros are?22?and?1111. But the last one has two ones in a row, so it's not valid. That's why the answer is?22.

The only numbers with the sum of digits equal to?33?without zeros are?111111,?1212,?2121, and?33. The first one has?22?ones in a row, so it's not valid. So the maximum valid number is?2121.

The only numbers with the sum of digits equals to?44?without zeros are?11111111,?211211,?121121,?112112,?1313,?3131,?2222, and?44. Numbers?11111111,?211211,?112112,?2222?aren't valid, because they have some identical digits in a row. So the maximum valid number is?121121.

一开始我还以为是以2的倍数为规律，1,2特判一下，原来是被样例误导了

后来举了几个例子，是以3的倍数为规律，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n;
void solve()
{
    if(n%3==1)
    {
        for(int i=1;i<=n/3;i++)
        {
            cout<<12;
        }
        cout<<1;

    }
    if(n%3==2)
    {
        for(int i=1;i<=n/3;i++)
        {
            cout<<21;
        }
        cout<<2;


    }
    if(n%3==0)
    {
        for(int i=1;i<=n/3;i++)
        {
            cout<<21;
        }
    }

}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        solve();
        cout<<endl;
    }

    return 0;
}

b

B. Madoka and the Elegant Gift

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Madoka's father just reached?11?million subscribers on Mathub! So the website decided to send him a personalized award?— The Mathhub's Bit Button!

The Bit Button is a rectangular table with?nn?rows and?mm?columns with?00?or?11?in each cell. After exploring the table Madoka found out that:

• A subrectangle?AA?is contained in a subrectangle?BB?if there's no cell contained in?AA?but not contained in?BB.
• Two subrectangles intersect if there is a cell contained in both of them.
• A subrectangle is called?black?if there's no cell with value?00?inside it.
• A subrectangle is called?nice?if it's?black?and it's not contained in another?black?subrectangle.
• The table is called?elegant?if there are no two?nice?intersecting subrectangles.

For example, in the first illustration the red subrectangle is nice, but in the second one it's not, because it's contained in the purple subrectangle.

Help Madoka to determine whether the table is elegant.

Input

Each test contains multiple test cases. The first line contains a single integer?tt?(1≤t≤2001≤t≤200)?— the number of test cases. Description of the test cases follows.

The first line of each test case contains two positive integers?n,mn,m?(1≤n,m≤1001≤n,m≤100).

The next?nn?lines contain strings of length?mm?consisting of zeros and ones?— the description of the table.

It is guaranteed that the sum of the values of?nn?and the sum of the values of?mm?for all test cases do not exceed?777777.

Output

For each test case print "YES" if its table is elegant or print "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

Example

input

Copy

5
3 3
100
011
011
3 3
110
111
110
1 5
01111
4 5
11111
01010
01000
01000
3 2
11
00
11

output

Copy

YES
NO
YES
NO
YES

Note

In the second test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

In the fourth test case the table is not elegant, because the red and the purple subrectangles are nice and intersect.

我一开始以为是联通问题，搞个bfs，我写完之后，发现样例不对，直接裂开，看了题解以后是说一个2*2的方块中有3个就不行了，感觉是凸出来了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int maps[105][105];
int main()
{
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%1d",&maps[i][j]);
            }
        }
        int flag=0;
       for(int i=2;i<=n;i++)
       {
           for(int j=2;j<=m;j++)
           {
               int s=0;
               if(maps[i][j]==1)s++;
               if(maps[i-1][j-1]==1)s++;
               if(maps[i-1][j]==1)s++;
               if(maps[i][j-1]==1)s++;
               if(s==3)
               {
                   flag=1;
               }
           }
       }
       if(flag)
       {
           cout<<"NO"<<endl;
       }
       else
       {
           cout<<"YES"<<endl;
       }
    }
    return 0;
}

c题题解说的很轻松，我看不懂，算了，其他题我还不打算做，div2先搞2题再说