题解 P8344 「Wdoi-6」走在夜晚的莲台野

GI录像机 · 2022-05-17 09:07:58 · 题解

思路：

因为金色木板不会消失，又至少有一个银色的，所以金色木板数小于容量时才有解。

考虑贪心，放入每个金色木板时，最大化减少的银色木板个数，则若有 z-1 个金色木板，将会减少 1+2+3+\cdots+(z-1) 个木板，根据等差数列公式，就是 \frac{(z-1)z}{2} 个木板。但由于实际的金色木板可能不够，所以我们实际消去的木板应减少 1+2+3+\cdots+(z-x-1) 个。最后判断还未被消去的银木板与金木板的和是否超过容量即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return f * x;
}
void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)write(x / 10);
    putchar(x % 10 + '0');
}
int t = read();
signed main() {
    while (t--) {
        int x = read(), y = read(), z = read();
        if (z <= x) {
            puts("Merry");
            continue;
        }
        int k = z * (z - 1) / 2 - (z - x) * (z - x - 1) / 2;
        y -= k;
        if (y > z - x) {
            puts("Merry");
            continue;
        }
        puts("Renko");
    }
    return 0;
}