CF2273D.Aura Battle
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is an interactive problem. Hacks are disabled.
You're in an aura battle in Pachuca, Mexico. Each battle consists of 10 rounds. The judges have a hidden integer x (1≤x≤104), which remains fixed throughout the battle.
In round i, you choose two integers ai and bi (−109≤ai,bi≤109). You then lose $ \min\bigl(|x-a_i|,\ |x-b_i|\bigr) $ aura and are told this amount before the next round begins. Your choices may depend on the results of all previous rounds. After the battle is over, your total aura loss is calculated as the sum of the aura lost in each of the 10 rounds.
Let m be the smallest integer such that there exists a strategy guaranteeing a total aura loss of at most m, regardless of the hidden value of x. Your task is to guarantee a total aura loss not exceeding the limit, which is 105 on the first test (the example) and m+67 on all other tests.
这是一个交互式问题,禁用 Hack。
你正在墨西哥帕丘卡参加一场灵能对决。每场对决共进行 10 轮。裁判持有一个隐藏整数 x(1≤x≤104),该值在整个对决过程中保持不变。
在第 i 轮中,你需要选择两个整数 ai 和 bi(−109≤ai,bi≤109)。随后,你将损失 min(∣x−ai∣, ∣x−bi∣) 点灵能,并在下一轮开始前获知该损失值。你的选择可依赖于此前所有轮次的结果。对决结束后,你的总灵能损失为各轮灵能损失之和。
令 m 为满足如下条件的最小整数:存在一种策略,无论隐藏值 x 取何值,均可保证总灵能损失不超过 m。你的任务是保证总灵能损失不超过给定上限:在第一个测试点(样例)中,该上限为 105;在其余所有测试点中,该上限为 m+67。
输入格式
The first line of input contains a single integer t (1≤t≤104) — the number of battles.
输入的第一行包含一个整数 t(1≤t≤104)—— 表示战斗的场数。
输出格式
null
输入输出样例
输入#1
1 13 4 2 2 4 5 9 6 9 13
输出#1
3 53 36 49 47 38 1 38 44 32 35 35 31 67 33 46 49 50 20 27
说明/提示
In the example there is a single battle, and the hidden value x is 40.
- In the first round, a1=3 and b1=53, so you lose 13=min(∣3−40∣,∣53−40∣) aura.
- In the second round, a2=36 and b2=49, so you lose 4=min(∣36−40∣,∣49−40∣) aura.
- In the third round, the amount of aura you lose is 2.
- In the following rounds, the amount of aura you lose is 2,4,5,9,6,9,13 respectively.
The total amount of aura you lose is 67. Note that this is an example of how the interaction works. To receive an accepted verdict, you must solve the problem without exceeding the aura limit outlined in the statement above.
在该示例中,仅有一场战斗,隐藏值 x 为 40。
- 在第一轮中,a1=3 且 b1=53,因此你损失 13=min(∣3−40∣,∣53−40∣) 点灵力。
- 在第二轮中,a2=36 且 b2=49,因此你损失 4=min(∣36−40∣,∣49−40∣) 点灵力。
- 在第三轮中,你损失的灵力为 2 点。
- 在后续各轮中,你损失的灵力分别为 2,4,5,9,6,9,13 点。
你总共损失的灵力为 67 点。注意,本例仅用于说明交互机制。要获得“通过”判定,你必须在不超出上述题目陈述中所规定的灵力限制的前提下解决该问题。
输入解题思路,AI测评打分。不知道怎么写?