283A.md (2171B)
1 Source: https://codeforces.com/problemset/problem/283/A 2 3 A. Cows and Sequence 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Bessie and the cows are playing with sequences and need your help. They start with a sequence, initially containing just the number 0, and perform *n* operations. Each operation is one of the following: 22 23 1. Add the integer *x**i* to the first *a**i* elements of the sequence. 24 2. Append an integer *k**i* to the end of the sequence. (And hence the size of the sequence increases by 1) 25 3. Remove the last element of the sequence. So, the size of the sequence decreases by one. Note, that this operation can only be done if there are at least two elements in the sequence. 26 27 After each operation, the cows would like to know the average of all the numbers in the sequence. Help them! 28 29 Input 30 31 The first line contains a single integer *n* (1 ≤ *n* ≤ 2·105) — the number of operations. The next *n* lines describe the operations. Each line will start with an integer *t**i* (1 ≤ *t**i* ≤ 3), denoting the type of the operation (see above). If *t**i* = 1, it will be followed by two integers *a**i*, *x**i* (|*x**i*| ≤ 103; 1 ≤ *a**i*). If *t**i* = 2, it will be followed by a single integer *k**i* (|*k**i*| ≤ 103). If *t**i* = 3, it will not be followed by anything. 32 33 It is guaranteed that all operations are correct (don't touch nonexistent elements) and that there will always be at least one element in the sequence. 34 35 Output 36 37 Output *n* lines each containing the average of the numbers in the sequence after the corresponding operation. 38 39 The answer will be considered correct if its absolute or relative error doesn't exceed 10- 6. 40 41 Examples 42 43 Input 44 45 ``` 46 5 47 2 1 48 3 49 2 3 50 2 1 51 3 52 ``` 53 54 Output 55 56 ``` 57 0.500000 58 0.000000 59 1.500000 60 1.333333 61 1.500000 62 ``` 63 64 Input 65 66 ``` 67 6 68 2 1 69 1 2 20 70 2 2 71 1 2 -3 72 3 73 3 74 ``` 75 76 Output 77 78 ``` 79 0.500000 80 20.500000 81 14.333333 82 12.333333 83 17.500000 84 17.000000 85 ``` 86 87 Note 88 89 In the second sample, the sequence becomes 