# Educational Codeforces Round 44 (Div. 2)（模拟+贪心）

## A. Chess Placing（模拟）

• time limit per test：1 second
• memory limit per test：256 megabytes

You are given a chessboard of size 1 × n. It is guaranteed that n is even. The chessboard is painted like this: "BWBW...BW".

Some cells of the board are occupied by the chess pieces. Each cell contains no more than one chess piece. It is known that the total number of pieces equals to $\frac{n}{2}$.

In one step you can move one of the pieces one cell to the left or to the right. You cannot move pieces beyond the borders of the board. You also cannot move pieces to the cells that are already occupied.

Your task is to place all the pieces in the cells of the same color using the minimum number of moves (all the pieces must occupy only the black cells or only the white cells after all the moves are made).

### Input

The first line of the input contains one integer n (2 ≤ n ≤ 100, n is even) — the size of the chessboard.

The second line of the input contains $\frac{n}{2}$ integer numbers $p_1, p_2, …, p_{\frac{n}{2}}$ ($1 ≤ p_i ≤ n$) — initial positions of the pieces. It is guaranteed that all the positions are distinct.

### Output

Print one integer — the minimum number of moves you have to make to place all the pieces in the cells of the same color.

### Examples

6
1 2 6
2
10
1 2 3 4 5
10

### Note

In the first example the only possible strategy is to move the piece at the position 6 to the position 5 and move the piece at the position 2 to the position 3. Notice that if you decide to place the pieces in the white cells the minimum number of moves will be 3.

In the second example the possible strategy is to move $5\rightarrow9$ in 4 moves, then $4\rightarrow7$ in 3 moves, $3 \rightarrow 5$ in 2 moves and $2 \rightarrow 3$ in 1 move.

### 链接

http://codeforces.com/contest/985/problem/A

### 代码

• Accepted
• 31 ms
• 0 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 110;
int a[maxn];

int main()
{
int n, b = 1, w = 2;
int sum1 = 0, sum2 = 0;
scanf("%d", &n);
for (int i = 1; i <= n / 2; ++i)
scanf("%d", &a[i]);
sort(a + 1,  a + 1 + n / 2);
for (int i = 1; i <= n / 2; ++i)
{
sum1 += abs(b - a[i]); // 全黑
sum2 += abs(w - a[i]); // 全白
b += 2, w += 2;
}
printf("%d\n", min(sum1, sum2));
return 0;
}

## B. Switches and Lamps（模拟）

• time limit per test：3 seconds
• memory limit per test：256 megabytes

You are given n switches and m lamps. The i-th switch turns on some subset of the lamps. This information is given as the matrix a consisting of n rows and m columns where $a_{i, j} = 1$ if the i-th switch turns on the j-th lamp and $a_{i, j} = 0$ if the i-th switch is not connected to the j-th lamp.

Initially all m lamps are turned off.

Switches change state only from "off" to "on". It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards.

It is guaranteed that if you push all n switches then all m lamps will be turned on.

Your think that you have too many switches and you would like to ignore one of them.

Your task is to say if there exists such a switch that if you will ignore (not use) it but press all the other n - 1 switches then all the m lamps will be turned on.

### Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2000) — the number of the switches and the number of the lamps.

The following n lines contain m characters each. The character $a_{i, j}$ is equal to '1' if the i-th switch turns on the j-th lamp and '0' otherwise.

It is guaranteed that if you press all n switches all m lamps will be turned on.

### Output

Print "YES" if there is a switch that if you will ignore it and press all the other n - 1 switches then all m lamps will be turned on. Print "NO" if there is no such switch.

### Examples

4 5
10101
01000
00111
10000
YES
4 5
10100
01000
00110
00101
NO

### 链接

http://codeforces.com/contest/985/problem/B

### 代码

• Accepted
• 46 ms
• 19800 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2010;
char s[maxn][maxn];
int a[maxn][maxn];
int sum[maxn];

int main()
{
int n, m;
scanf("%d%d", &n, &m);
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
a[i][j] = ((s[i][j] == '1') ? 1 : 0);
sum[j] += a[i][j]; // 统计每个灯泡可以被多少个开关控制
}
bool flag = false;
for (int i = 1; i <= n; ++i)
{
int j;
for (j = 1; j <= m; ++j)
{
if (sum[j] - a[i][j] == 0) // 去除该开关后，没有别的开关可以控制该灯泡
break;
}
if (j > m) // 去除该开关后没有问题
{
flag = true;
break;
}
}
if (flag)
printf("YES\n");
else
printf("NO\n");
return 0;
}

### C. Liebig's Barrels（贪心）

• time limit per test：2 seconds
• memory limit per test：256 megabytes

You have m = n·k wooden staves. The i-th stave has length $a_i$. You have to assemble n barrels consisting of k staves each, you can use any k staves to construct a barrel. Each stave must belong to exactly one barrel.

Let volume $v_j$ of barrel j be equal to the length of the minimal stave in it.

You want to assemble exactly n barrels with the maximal total sum of volumes. But you have to make them equal enough, so a difference between volumes of any pair of the resulting barrels must not exceed l, i.e. $|v_x - v_y| ≤ l$ for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.

Print maximal total sum of volumes of equal enough barrels or 0 if it's impossible to satisfy the condition above.

### Input

The first line contains three space-separated integers n, k and l ($1 ≤ n, k ≤ 10^5, 1 ≤ n·k ≤ 10^5, 0 ≤ l ≤ 10^9$).

The second line contains m = n·k space-separated integers $a_1, a_2, ..., a_m (1 ≤ a_i ≤ 10^9)$ — lengths of staves.

### Output

Print single integer — maximal total sum of the volumes of barrels or 0 if it's impossible to construct exactly n barrels satisfying the condition $|v_x - v_y| ≤ l$ for any 1 ≤ x ≤ n and 1 ≤ y ≤ n.

### Examples

4 2 1
2 2 1 2 3 2 2 3
7
2 1 0
10 10
20
1 2 1
5 2
2
3 2 1
1 2 3 4 5 6
0

### Note

In the first example you can form the following barrels: [1, 2], [2, 2], [2, 3], [2, 3].

In the second example you can form the following barrels: [10], [10].

In the third example you can form the following barrels: [2, 5].

In the fourth example difference between volumes of barrels in any partition is at least 2 so it is impossible to make barrels equal enough.

### 链接

http://codeforces.com/contest/985/problem/C

### 代码

• Accepted
• 280 ms
• 1800 KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 200010;
bool vis[maxn];
ll a[maxn];

int main()
{
ll n, k, l, sum = 0, cnt = 0;
cin >> n >> k >> l;
for (int i = 1; i <= k * n; ++i)
cin >> a[i];
sort(a + 1, a + 1 + k * n);
if (a[n] - a[1] > l)
{
cout << "0\n";
return 0;
}
int p = k * n; // 注意p初始化的值
for (int i = n + 1; i <= n * k; ++i) // 找到最后一个小于等于a[1] + k的
if (a[i] - a[1] > l)
{
p = i - 1;
break;
}
bool flag = false;
for (int i = 1; i <= p; i += k) // 范围之内，每k个取一个最小的
{
sum += a[i];
vis[i] = true;
cnt++;
if (cnt == n)
{
flag = true;
break;
}
}
if (flag)
cout << sum << "\n";
else
{
for (int i = p; i >= 1; --i) // 从最后一个开始选择剩余符合要求的
{
if (!vis[i])
{
sum += a[i];
cnt++;
if (cnt == n)
{
cout << sum << "\n";
break;
}
}
}
}
return 0;
}

The end.
2018-05-25 星期五