概述

本题要求找出获奖概率不低于 ~m\%~ 的最小奖级，即满足 ~k/sum \ge m\%~ 的最小整数 ~k~（~sum = 1 + 2 + \cdots + n~），无解时输出 ~-1~。核心解法是把条件等价变形为 ~k \ge sum \cdot m/100~，直接对 ~sum \cdot m/100~ 向上取整得到答案。

分析

核心观察

中 ~k~ 等奖的概率为 ~k/sum~，随 ~k~ 单调递增；条件 ~k/sum \ge m/100~ 等价于 ~k \ge sum \cdot m/100~，因此最小的合格奖级就是 ~\lceil sum \cdot m/100 \rceil~。

思路

奖盘共被分成 ~sum = n(n+1)/2~ 份，条件 ~k/sum \ge m\%~ 等价于：

$$\displaystyle \frac{k}{sum} \ge \frac{m}{100} \iff k \ge \frac{sum \cdot m}{100} $$

故答案 ~k = \lceil sum \cdot m/100 \rceil~（~m = 0~ 时取 ~\max(1, \cdot)~）；若 ~k > n~，说明概率最大的 ~n~ 等奖也不达标，输出 ~-1~。

向上取整必须用精确整数运算：~sum~ 最大约 ~5 \times 10^{13}~，double 计算 ~sum \cdot m/100~ 的误差可达 ~0.01~，而该值到最近整数的距离最小只有 ~10^{-8}~，浮点版本会在边界处取错。因此把 ~m~ 解析为精确分数 ~M/10^d~：

$$\displaystyle k = \left\lceil \frac{sum \cdot M}{10^{d+2}} \right\rceil = \left\lfloor \frac{sum \cdot M + 10^{d+2} - 1}{10^{d+2}} \right\rfloor $$

若不用闭式，也可从小到大枚举奖级 ~x~ 检查 ~x/sum \ge m\%~，第一个满足的 ~x~ 与上式结果一致。

具体示例

样例 ~1~：~n = 5~，~sum = 15~，~m = 20~，~sum \cdot m/100 = 3~，向上取整得 ~k = 3 \le 5~，输出 ~3~。样例 ~4~：~n = 17~，~sum = 153~，~sum \cdot m/100 = 22.95~，向上取整得 ~23 > 17~，输出 ~-1~。

算法步骤

1. 读入 n 与浮点数 m。
2. 将 m 解析为精确分数：整数部分与小数部分合并为 M（~m = M/10^d~），d 为小数位数。
3. 计算 sum 为 ~n(n+1)/2~。
4. 计算 k 为 ~\lceil sum \cdot M / 10^{d+2} \rceil~（用整数除法实现，即 ~(sum \cdot M + 10^{d+2} - 1) / 10^{d+2}~），并取 k 与 ~1~ 的较大值。
5. 若 k 不超过 n，输出 k；否则输出 ~-1~。

复杂度分析

时间：~O(1)~

空间：~O(1)~

实现注意事项

• ~sum \cdot M~ 最大约 ~5 \times 10^{21}~，超出 64 位整数范围，C++ 中需使用 128 位整数（__int128），Python 的大整数可直接处理。
• 向上取整不能先浮点计算再取整：~sum \cdot m/100~ 的 double 误差（约 ~0.01~）远大于其与整数的最小距离（~10^{-8}~），会在边界处出错。
• ~m = 0~ 时任意奖级都满足条件，答案应为 ~1~，注意对计算结果取 ~\max(1, \cdot)~。
• 无解条件为 ~\lceil sum \cdot m/100 \rceil > n~，即概率最大的 ~n~ 等奖仍不达标。

源代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    string m;
    cin >> n >> m;

    long long M = 0;
    int d = 0;
    size_t dot = m.find('.');
    if (dot == string::npos) {
        M = stoll(m);
    } else {
        string ip = m.substr(0, dot);
        string fp = m.substr(dot + 1);
        d = (int)fp.size();
        long long ipv = ip.empty() ? 0 : stoll(ip);
        long long fpv = fp.empty() ? 0 : stoll(fp);
        M = ipv;
        for (int i = 0; i < d; i++) M *= 10;
        M += fpv;
    }

    long long sum = n * (n + 1) / 2;
    long long den = 1;
    for (int i = 0; i < d + 2; i++) den *= 10;

    __int128 k128 = ((__int128)sum * M + den - 1) / den;
    long long k = (long long)k128;
    if (k < 1) k = 1;

    if (k > n) cout << -1 << '\n';
    else cout << k << '\n';
    return 0;
}

n, m = input().split()
n = int(n)

if '.' in m:
    ip, fp = m.split('.', 1)
    d = len(fp)
    M = (int(ip) if ip else 0) * 10**d + (int(fp) if fp else 0)
else:
    d = 0
    M = int(m)

total = n * (n + 1) // 2
den = 10 ** (d + 2)
k = (total * M + den - 1) // den
k = max(k, 1)
print(k if k <= n else -1)