A186076.声望校准
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
一个任务系统会根据玩家原来的声望、参与共享奖励的人数和奖励加成,计算任务结束后的声望。
为了统一单位,输入中的声望已经乘以 100,以整数形式给出。例如,输入 −250 表示实际声望为 −2.50。后续公式与误差比较都使用这个放大后的单位。
系统的基础奖励系数为 K/106,其中 K 是未知整数,且 0≤K≤500000。所有任务记录使用同一个 K。
第 i 条记录包含四个整数:
- si:任务前的声望;
- ti:记录的任务后声望;
- ci:共享奖励的人数;
- bi:奖励加成百分数,例如 bi=20 表示增加 20%。
如果系数参数为 K,按照系统规则计算的任务后声望为:
pi=si+108ci(1000−si)(100+bi)K
这里的除法表示数学上的精确除法。pi 可以不是整数,不进行四舍五入、向下取整或其他取整操作。
记录可能存在偏差。你需要找到一个非负整数容许误差 E,使得存在同一个合法整数 K,对所有记录都有:
∣pi−ti∣≤E
请先使 E 尽可能小;在最小的 E 下,再使 K 尽可能小。输出这两个整数。
各条记录独立计算,直接使用该条记录给出的 si,不会把前一条记录的预测值作为下一条记录的初始声望。
输入格式
第一行输入一个整数 n,表示记录数量。
接下来 n 行,每行输入四个整数 si,ti,ci,bi,含义如题目所述。
输出格式
输出一行两个整数 E,K:先输出最小的整数容许误差,再输出在这个误差下最小的合法整数系数参数。两者都按题目中的整数形式输出,无需换算为实际声望或小数系数。
输入输出样例
输入#1
2 0 100 1 0 500 550 1 0
输出#1
0 100000
输入#2
2 0 100 1 0 0 103 1 0
输出#2
2 101000
输入#3
1 1000 997 1 100
输出#3
3 0
说明/提示
样例解释 1
当 K=100000 时,两条记录的预测值分别恰好为 100 和 550,所以最小误差为 0。第一条记录在误差为 0 时已经唯一确定 K=100000。
样例解释 2
两条记录的预测值相同。当 E=1 时,预测值必须同时位于 [99,101] 和 [102,104],无法满足。
当 E=2 时,两个允许区间的交集为 [101,102]。预测值为 K/1000,所以最小合法整数 K 为 101000。
样例解释 3
由于 s1=1000,无论 K 取何值,预测声望始终为 1000。最小误差为 3,此时最小合法 K 为 0。
数据范围
对于所有测试数据,保证:
- 1≤n≤2×105;
- −1000≤si,ti≤1000;
- 1≤ci≤100;
- 0≤bi≤100。
待求的 K 必须为整数,且 0≤K≤500000;待求的 E 必须为非负整数。
输入解题思路,AI测评打分。不知道怎么写?