301500: CF283B. Cow Program
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Cow Program
题意翻译
输入n,输入一串序列$a_2$,$a_3$,$a_4$……$a_n$,$a_1$是运行程序的次数 已知一个程序: 对于数x,y有4种操作: 1. 最初,x=1且y=0。如果任一步骤之后,x≤0或x>n,则程序立即终止。 2. x和y同时增加$a_x$。 3. y增加$a_x$,同时x减少$a_x$。 4. 程序重复执行步骤2和3(先是步骤2,然后是步骤3),直到它终止(它可能永远不会终止)。 运行n-1次程序,每行输出每次程序终止后y的值,若不能终止,输出-1题目描述
Farmer John has just given the cows a program to play with! The program contains two integer variables, $ x $ and $ y $ , and performs the following operations on a sequence $ a_{1},a_{2},...,a_{n} $ of positive integers: 1. Initially, $ x=1 $ and $ y=0 $ . If, after any step, $ x<=0 $ or $ x>n $ , the program immediately terminates. 2. The program increases both $ x $ and $ y $ by a value equal to $ a_{x} $ simultaneously. 3. The program now increases $ y $ by $ a_{x} $ while decreasing $ x $ by $ a_{x} $ . 4. The program executes steps 2 and 3 (first step 2, then step 3) repeatedly until it terminates (it may never terminate). So, the sequence of executed steps may start with: step 2, step 3, step 2, step 3, step 2 and so on. The cows are not very good at arithmetic though, and they want to see how the program works. Please help them! You are given the sequence $ a_{2},a_{3},...,a_{n} $ . Suppose for each $ i $ $ (1<=i<=n-1) $ we run the program on the sequence $ i,a_{2},a_{3},...,a_{n} $ . For each such run output the final value of $ y $ if the program terminates or -1 if it does not terminate.输入输出格式
输入格式
The first line contains a single integer, $ n $ ( $ 2<=n<=2·10^{5} $ ). The next line contains $ n-1 $ space separated integers, $ a_{2},a_{3},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ).
输出格式
Output $ n-1 $ lines. On the $ i $ -th line, print the requested value when the program is run on the sequence $ i,a_{2},a_{3},...a_{n} $ . Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
输入输出样例
输入样例 #1
4
2 4 1
输出样例 #1
3
6
8
输入样例 #2
3
1 2
输出样例 #2
-1
-1