A186076.声望校准

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

一个任务系统会根据玩家原来的声望、参与共享奖励的人数和奖励加成,计算任务结束后的声望。

为了统一单位,输入中的声望已经乘以 100100,以整数形式给出。例如,输入 −250-250 表示实际声望为 −2.50-2.50。后续公式与误差比较都使用这个放大后的单位。

系统的基础奖励系数为 K/106K/10^6,其中 KK 是未知整数,且 0≤K≤5000000\le K\le500000。所有任务记录使用同一个 KK。

第 ii 条记录包含四个整数:

  • sis_i:任务前的声望;
  • tit_i:记录的任务后声望;
  • cic_i:共享奖励的人数;
  • bib_i:奖励加成百分数,例如 bi=20b_i=20 表示增加 20%20\%。

如果系数参数为 KK,按照系统规则计算的任务后声望为:

pi=si+(1000−si)(100+bi)K108cip_i=s_i+\frac{(1000-s_i)(100+b_i)K}{10^8c_i}

这里的除法表示数学上的精确除法。pip_i 可以不是整数,不进行四舍五入、向下取整或其他取整操作。

记录可能存在偏差。你需要找到一个非负整数容许误差 EE,使得存在同一个合法整数 KK,对所有记录都有:

∣pi−ti∣≤E|p_i-t_i|\le E

请先使 EE 尽可能小;在最小的 EE 下,再使 KK 尽可能小。输出这两个整数。

各条记录独立计算,直接使用该条记录给出的 sis_i,不会把前一条记录的预测值作为下一条记录的初始声望。

输入格式

第一行输入一个整数 nn,表示记录数量。

接下来 nn 行,每行输入四个整数 si,ti,ci,bis_i,t_i,c_i,b_i,含义如题目所述。

输出格式

输出一行两个整数 E,KE,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=100000K=100000 时,两条记录的预测值分别恰好为 100100 和 550550,所以最小误差为 00。第一条记录在误差为 00 时已经唯一确定 K=100000K=100000。

样例解释 2

两条记录的预测值相同。当 E=1E=1 时,预测值必须同时位于 [99,101][99,101] 和 [102,104][102,104],无法满足。

当 E=2E=2 时,两个允许区间的交集为 [101,102][101,102]。预测值为 K/1000K/1000,所以最小合法整数 KK 为 101000101000。

样例解释 3

由于 s1=1000s_1=1000,无论 KK 取何值,预测声望始终为 10001000。最小误差为 33,此时最小合法 KK 为 00。

数据范围

对于所有测试数据,保证:

  • 1≤n≤2×1051\le n\le2\times10^5;
  • −1000≤si,ti≤1000-1000\le s_i,t_i\le1000;
  • 1≤ci≤1001\le c_i\le100;
  • 0≤bi≤1000\le b_i\le100。

待求的 KK 必须为整数,且 0≤K≤5000000\le K\le500000;待求的 EE 必须为非负整数。

输入解题思路,AI测评打分。不知道怎么写?

首页