AtCoder Regular Contest 080 CD题

话说都有题解，所以这是骗访问量的

C - 4-adjacent

---

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

We have a sequence of length N, a=(a1,a2,…,aN). Each ai 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 ai and ai+1 is a multiple of 4.

Determine whether Snuke can achieve his objective.

Constraints

2≤N≤105ai is an integer.1≤ai≤109

---

Input

Input is given from Standard Input in the following format:

N a1 a2 … aN

Output

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

---

Sample Input 1

Copy 3 1 10 100

Sample Output 1

Copy Yes

One solution is (1,100,10).

分成4的倍数和奇数还有2的倍数（不整除4的偶数）

1414141允许奇数比四的倍数多一个，但不允许加入新的2的倍数

14141422222允许奇数最多等于四的倍数

于是我WA了6次

#include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,a[100005], b[5]; int main(){ scanf("%d", &n); for( int i = 1; i <= n; i++ ) scanf("%d", &a[i]); for( int i = 1; i <= n; i++ ){ if( a[i] & 1 ){ b[1]++; continue; } if( a[i]%4 == 0 ) b[4]++; else if( a[i]%2 == 0 ) b[2]++; } if( !b[2] && b[1] > b[4]+1 ) { puts("No"); return 0;} if( b[2] && b[1] > b[4] ) { puts("No"); return 0;} puts("Yes"); return 0; }

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 ai squares painted in Color i. Here, a1+a2+…+aN=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≤1001≤N≤HWai≥1a1+a2+…+aN=HW

---

Input

Input is given from Standard Input in the following format:

H W N a1 a2 … aN

Output

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

c11 … c1W : cH1 … cHW

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

---

Sample Input 1

Copy 2 2 3 2 1 1

Sample Output 1

Copy 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.

-------------------------                              | ------------------------- | -------------------------                              | ------------------------- 这样放就行了 #include<algorithm> #include<iostream> #include<cstdio> #include<cmath> using namespace std; int mp[105][105],a[105*105],h,w,n; int main(){ scanf("%d%d", &h, &w); int tail = 1; scanf("%d", &n); for( int i = 1; i <= n; i++ ) scanf("%d", &a[i]); for( int i = 1; i <= h; i++ ){ if( i & 1 ){ for( int j = 1; j <= w; j++ ){ while( !a[tail] ) tail++; mp[i][j] = tail; a[tail]--; } } else{ for( int j = w; j >= 1; j-- ){ while( !a[tail] ) tail++; mp[i][j] = tail; a[tail]--; } } } for( int i = 1; i <= h; i++ ){ for( int j = 1; j <= w; j++ ) printf("%d ", mp[i][j]); puts(""); } return 0; }