CF241G.Challenging Balloons
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Martha — as a professional problemsetter — proposed a problem for a world-class contest. This is the problem statement:
Tomorrow is Nadia's birthday, and Bardia (her brother) is assigned to make the balloons ready!
There are n balloons (initially empty) that are tied to a straight line on certain positions _x_1, _x_2, ..., x__n. Bardia inflates the balloons from left to right. As a result, i-th balloon gets bigger and bigger until its radius reaches the pressure endurance p__i or it touches another previously-inflated balloon.

While Bardia was busy with the balloons, he wondered "What will be the sum of radius of balloons after all of the balloons are inflated?". Being a nerdy type of guy, he is now thinking about the problem instead of preparing his sister's birthday. Calculate the answer to Bardia's problem so that Nadia's birthday won't be balloon-less.
Artha — Martha's student — claimed his solution got accepted. Martha (being his teacher for a long time!) knew he couldn't have solved the problem for real and thus thinks there is something wrong with the testcases. Artha isn't anyhow logical, which means there is no way for Martha to explain the wrong point in his algorithm. So, the only way is to find a testcase to prove him wrong!
Artha's pseudo-code is shown below:

You should output a small testcase for the problem such that Artha's algorithm is incorrect. The algorithm's output is considered correct if it differs from the correct value by no more than 1.
玛莎——作为一名专业出题人——为一场世界级竞赛提出了一道题目。题目描述如下:
明天是娜迪亚的生日,而她的哥哥巴尔迪亚负责准备气球!
一共有 n 个初始为空的气球,它们被系在一条直线上,位置分别为 x1,x2,…,xn。巴尔迪亚从左到右依次给气球充气。第 i 个气球会不断膨胀,直到其半径达到该气球所能承受的最大压强 pi,或与某个此前已充好气的气球相接触。

当巴尔迪亚正忙着给气球充气时,他忽然想到:“当所有气球都充完气后,所有气球的半径之和是多少?”由于他是个典型的书呆子,此刻他反而在思考这个问题,而不是为妹妹的生日做准备。请计算出巴尔迪亚问题的正确答案,以免娜迪亚的生日缺少气球!
阿莎——玛莎的学生——声称他的解法通过了评测。但玛莎(作为他长期的老师!)深知他根本不可能真正解决此题,因此怀疑测试数据存在问题。而阿莎本身毫无逻辑可言,这意味着玛莎无法向他指出其算法中错误的具体环节。所以,唯一可行的办法就是构造一个反例测试数据,来证伪他的算法!
阿莎的伪代码如下所示:

你需要输出一个规模较小的测试用例,使得阿莎的算法给出错误结果。若算法输出值与正确答案之差的绝对值不超过 1,则认为该输出是正确的。
输入格式
Please pay attention! No input will be given to your program for this problem. So you do not have to read from the input anything.
请注意!本题不会向您的程序提供任何输入。因此,您无需从输入中读取任何内容。
输出格式
You should output the generated small testcase (which Artha's solution doesn't get it right). It should be in the following format:
- First line must contain the only number n (1 ≤ n ≤ 500).
- The i-th of the next n lines should contain the description of the i-th balloon — two space-separated integers x__i, p__i (1 ≤ p__i ≤ 106, 0 ≤ _x_1 < _x_2 < ... < x__n ≤ 106).
你应该输出一个生成的小型测试用例(Artha 的解法在此用例上无法得到正确结果)。该测试用例应满足以下格式:
- 第一行必须仅包含一个整数 n(1 ≤ n ≤ 500)。
- 接下来的 n 行中,第 i 行应描述第 i 个气球——两个以空格分隔的整数 xi、pi(1 ≤ pi ≤ 106,且满足 0 ≤ x1 < x2 < … < xn ≤ 106)。
说明/提示
The testcase depicted in the figure above (just showing how output should be formatted):
4
0 9
6 3
12 7
17 1
上图所示的测试用例(仅展示输出格式应如何):
4
0 9
6 3
12 7
17 1
输入解题思路,AI测评打分。不知道怎么写?