Atcoder ABC 069 C - 4-adjacent D

C - 4-adjacent

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a sequence of length N, a=(a₁,a₂,…,a_N). Each a_i is a positive integer.

Snuke's objective is to permute the element in a so that the following condition is satisfied:

For each 1≤i≤N−1, the product of a_i and a_i+1 is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

2≤N≤10⁵
a_i is an integer.
1≤a_i≤10⁹

Input

Input is given from Standard Input in the following format:

N

a₁ a₂ … a_N

Output

If Snuke can achieve his objective, print Yes; otherwise, print No.

Sample Input 1

3

1 10 100

Sample Output 1

Yes

One solution is (1,100,10).

Sample Input 2

4

1 2 3 4

Sample Output 2

No

It is impossible to permute a so that the condition is satisfied.

Sample Input 3

3

1 4 1

Sample Output 3

Yes

The condition is already satisfied initially.

Sample Input 4

2

1 1

Sample Output 4

No

Sample Input 5

6

2 7 1 8 2 8

Sample Output 5

Yes
1～n-1之间保证a[i]*a[i+1]%4==0

    #include <iostream>

    #include <algorithm>

    #include <cstring>

    #include <cstdio>

    #include <vector>

    #include <queue>

    #include <stack>

    #include <cstdlib>

    #include <iomanip>

    #include <cmath>

    #include <cassert>

    #include <ctime>

    #include <map>

    #include <set>

    using namespace std;

    #define lowbit(x) (x&(-x))

    #define max(x,y) (x>y?x:y)

    #define min(x,y) (x<=y?x:y)

    #define MAX 100000000000000000

    #define MOD 1000000007

    #define pi acos(-1.0)

    #define ei exp(1)

    #define PI 3.141592653589793238462

    #define ios() ios::sync_with_stdio(false)

    #define INF 1044266558

    #define mem(a) (memset(a,0,sizeof(a)))

    typedef long long ll;

    int a,b,c,x,n;

    int main()

    {

        while(scanf("%d",&n)!=EOF)

        {

            a=b=c=;

            for(int i=;i<n;i++)

            {

                scanf("%d",&x);

                if(!(x%)) a++;

                else if(x&) b++;

                else c++;

            }

            if(!c) b--;

            puts(a>=b?"Yes":"No");

        }

        return ;

    }

D - Grid Coloring

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a grid with H rows and W columns of squares. Snuke is painting these squares in colors 1, 2, …, N. Here, the following conditions should be satisfied:

For each i (1≤i≤N), there are exactly a_i squares painted in Color i. Here, a₁+a₂+…+a_N=HW.
For each i (1≤i≤N), the squares painted in Color i are 4-connected. That is, every square painted in Color i can be reached from every square painted in Color i by repeatedly traveling to a horizontally or vertically adjacent square painted in Color i.

Find a way to paint the squares so that the conditions are satisfied. It can be shown that a solution always exists.

Constraints

1≤H,W≤100
1≤N≤HW
a_i≥1
a₁+a₂+…+a_N=HW

Input

Input is given from Standard Input in the following format:

H W

N

a₁ a₂ … a_N

Output

Print one way to paint the squares that satisfies the conditions. Output in the following format:

c₁₁ … c_1W

:

c_H1 … c_HW

Here, c_ij is the color of the square at the i-th row from the top and j-th column from the left.

Sample Input 1

Sample Output 1

1 1

2 3

Below is an example of an invalid solution:

1 2

3 1

This is because the squares painted in Color 1 are not 4-connected.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

1
h*w的网格，填充颜色，颜色种类为n，a[i]*****a[n],为每种颜色的个数，保证所填充相等颜色之间必须联通，蛇形填充就行。

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <stack>

#include <cstdlib>

#include <iomanip>

#include <cmath>

#include <cassert>

#include <ctime>

#include <map>

#include <set>

using namespace std;

#define lowbit(x) (x&(-x))

#define max(x,y) (x>y?x:y)

#define min(x,y) (x<=y?x:y)

#define MAX 100000000000000000

#define MOD 1000000007

#define pi acos(-1.0)

#define ei exp(1)

#define PI 3.141592653589793238462

#define ios() ios::sync_with_stdio(false)

#define INF 1044266558

#define mem(a) (memset(a,0,sizeof(a)))

typedef long long ll;

int g[][];

int h,w,n,x,k;

int main()

{

    while(scanf("%d%d%d",&h,&w,&n)!=EOF)

    {

        mem(g);

        k=-;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&x);

            while(x--) k++,g[(k/h)&?(h--(k%h)):k%h][k/h]=i;

        }

        for(int i=;i<h;i++)

        {

            for(int j=;j<w;j++)

            {

                if(j) printf(" ");

                printf("%d",g[i][j]);

            }

            printf("\n");

        }

    }

    return ;

}

巴特西

Atcoder ABC 069 C - 4-adjacent D - Grid Coloring

C - 4-adjacent

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

D - Grid Coloring

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

最新文章

热门文章