MENU

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

2018 年 05 月 25 日 • 阅读: 1898 • 练习 • 阅读设置

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

题意

给定一个1*n的棋盘，n是偶数，棋盘的布局是“黑白黑白黑白…”，现有$\frac{n}{2}$个棋子摆放在不同的位置，问将这些棋子移到全黑或者全白的位置需要的最少移动次数。

题解

数据范围小，手动模拟一遍，得到将所有的棋子移动到全黑的位置次数sum1，移动到全白位置次数sum2，答案为两者最小值。

代码

  • 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

题意

有n个开关和m个灯泡，一个开关能控制多个灯泡，保证使用n个开关可以控制所有的灯泡。现在问能否使用n-1开关控制所有的灯泡。

题解

从每行开始遍历，如果去掉某行后，剩余开关能控制所有的灯泡则直接结束循环输出YES，遍历完后还是不能则输出NO，具体参见代码。

代码

  • 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

题意

有n*k块木板，让你用k块木板组成一个木桶，总共组成n个，每个桶的体积为最短木板的长度，现要求n个木桶中任意两个的体积之差不能超过l，求n个桶的最大体积。

题解

贪心思想，每个木桶的体积都由组成它的最短木板的长度决定，所以只需考虑每个木桶中的最短木板。

首先对n*k块木板进行排序（数组下标从第一个开始），如果a[n]-a[1]大于l，那么输出0。

然后找到排序后序列中最后一个小于等于a[1]+l的木板p的位置，木板p是在范围之内能取得的最大体积。

最后把K块木板中的最短木板加起来，再从第p块木板往前找符合要求的加起来，得到答案。

本题参考了断腿三郎的题解。

代码

  • 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;
}

话说Clion的scanf和printf输入输出64位只能用%lld么，用%I64d的时候莫名出bug。

The end.
2018-05-25 星期五
模拟Codeforces贪心
最后编辑于: 2018 年 05 月 26 日
添加新评论