CF66E.Petya and Post
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Little Vasya's uncle is a postman. The post offices are located on one circular road. Besides, each post office has its own gas station located next to it. Petya's uncle works as follows: in the morning he should leave the house and go to some post office. In the office he receives a portion of letters and a car. Then he must drive in the given car exactly one round along the circular road and return to the starting post office (the uncle can drive along the circle in any direction, counterclockwise or clockwise). Besides, since the car belongs to the city post, it should also be fuelled with gasoline only at the Post Office stations.
The total number of stations equals to n. One can fuel the car at the i-th station with no more than a__i liters of gasoline. Besides, one can fuel the car no more than once at each station. Also, the distance between the 1-st and the 2-nd station is _b_1 kilometers, the distance between the 2-nd and the 3-rd one is _b_2 kilometers, ..., between the (n - 1)-th and the n-th ones the distance is b__n - 1 kilometers and between the n-th and the 1-st one the distance is b__n kilometers. Petya's uncle's high-tech car uses only one liter of gasoline per kilometer. It is known that the stations are located so that the sum of all a__i is equal to the sum of all b__i. The i-th gas station and i-th post office are very close, so the distance between them is 0 kilometers.
Thus, it becomes clear that if we start from some post offices, then it is not always possible to drive one round along a circular road. The uncle faces the following problem: to what stations can he go in the morning to be able to ride exactly one circle along the circular road and visit all the post offices that are on it?
Petya, who used to attend programming classes, has volunteered to help his uncle, but his knowledge turned out to be not enough, so he asks you to help him write the program that will solve the posed problem.
小瓦西亚的叔叔是一名邮递员。邮局都位于一条环形道路上。此外,每个邮局旁边都设有一个加油站。佩佳的叔叔的工作流程如下:每天早晨,他需从家中出发前往某个邮局;在该邮局,他领取一批信件和一辆汽车;随后,他必须驾驶这辆汽车沿环形道路恰好行驶一圈并返回出发的邮局(叔叔可选择顺时针或逆时针任一方向行驶)。另外,由于该车属于市邮政系统,只能在邮局所属的加油站加油。
总共有 n 个加油站(即邮局)。在第 i 个加油站最多可加 ai 升汽油,且每个加油站至多只能加一次油。相邻两个邮局之间的距离为:第 1 个与第 2 个邮局之间为 b1 千米,第 2 个与第 3 个之间为 b2 千米,……,第 (n−1) 个与第 n 个之间为 bn−1 千米,第 n 个与第 1 个之间为 bn 千米。佩佳叔叔的高科技汽车每千米耗油恰好 1 升。已知所有加油站的位置满足:∑i=1nai=∑i=1nbi。第 i 个加油站与第 i 个邮局位置极近,二者间距离为 0 千米。
因此,显然:若从某些邮局出发,则不一定总能完成环形道路的一整圈行驶。叔叔面临如下问题:早晨可以前往哪些邮局作为起点,才能确保恰好绕环形道路行驶一圈,并访问沿途所有邮局?
曾参加过编程课程的佩佳主动提出帮叔叔解决此问题,但他的知识不足以独立完成,因此请求你帮助编写程序来解决这一问题。
输入格式
The first line contains integer n (1 ≤ n ≤ 105). The second line contains n integers a__i — amount of gasoline on the i-th station. The third line contains n integers _b_1, _b_2, ..., b__n. They are the distances between the 1-st and the 2-nd gas stations, between the 2-nd and the 3-rd ones, ..., between the n-th and the 1-st ones, respectively. The sum of all b__i equals to the sum of all a__i and is no more than 109. Each of the numbers a__i, b__i is no less than 1 and no more than 109.
第一行包含一个整数 n(1 ≤ n ≤ 105)。
第二行包含 n 个整数 ai —— 第 i 个加油站的汽油量。
第三行包含 n 个整数 b1,b2,...,bn,分别表示第 1 个与第 2 个加油站之间的距离、第 2 个与第 3 个加油站之间的距离、……、第 n 个与第 1 个加油站之间的距离。
所有 bi 的总和等于所有 ai 的总和,且不超过 109。每个数 ai 和 bi 均满足 1 ≤ ai,bi ≤ 109。
输出格式
Print on the first line the number k — the number of possible post offices, from which the car can drive one circle along a circular road. Print on the second line k numbers in the ascending order — the numbers of offices, from which the car can start.
第一行输出整数 k —— 表示汽车能够沿环形道路行驶一圈的可能邮局数量。
第二行按升序输出 k 个数字 —— 表示汽车可以出发的邮局编号。
输入输出样例
输入#1
4 1 7 2 3 8 1 1 3
输出#1
2 2 4
输入#2
8 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1
输出#2
8 1 2 3 4 5 6 7 8
输入解题思路,AI测评打分。不知道怎么写?