Assignment 02 Solution

Motivation




After enjoying CS101 at morning, you are immersed in the sunlight shedding on Dongda dining hall, where cusine conjures in your mind. However, the extremely LONG LONG queue blocks your imagination. You starts to be impatient and looks for your friend. At the same time, two facts arouse your curosity.

    1. If two students are adjacent in a queue, they are visible to each other.

    2. If students between two students are shorter(or equal), those two ones are still able to see each other.

    3. Otherwise, if any one of them shorter than any student between them. They cannot see each other.



Goal

When you are having your meal, you find yourself can easily memorize the height of all students in the queue. However, you are really curious about one thing:

how many pairs of students could see each other?

F&Q

1. If students are of height "2, 2, 3", can the first student see the third student?

Yes


Input

    1. At first line, an integer N is provided, indicating the population of the queue.

    2. At next N lines, N integers are provided, indicating the height of those N students.

No illegal input exists in TestCase. All integers can be well saved in int32.

For 30% TestCase, N ≤ 100

For 60% TestCase, N ≤ 10000

For 100% TestCase, N≤ 500000


Output

A integer P, indicating P pairs of people are visible to each other.P can be well saved in int32.



Sample Input 1
Sample Output 1



7
10

2

4

1

2

2

5

1




    Details


Motivation
At Zhangjiang zone of ShanghaiTech University, Network, as an important infrastructure, should be double checked. To realize FTTH(Fiber To The Home), working stuff suffers from a problem:the decay of signal,with respect to the disantce be
tween nodes. The remote terminal cannot receive the weak signal from server.
202
1000MS
256MB
Standard IO
Created By root
Level Mid
Score 100
Tags
Show
An abstract model has been designed to analyze this challenge. First, Regard the whole network structure on campus as a tree:
1. Root node is a server, which releases signal to all terminals. There is only one server in this model for a tree.
 Statistic
2. Leaf nodes are terminals.
3. Intermidiate nodes are packet switches.
4. The edges between nodes are cables.
The signal starts from the server and ends at terminal. It will decay with the rules below:
1. The strength of signals share an initial value at root(server).
2. Each edge is assigned with a decay value. The signal strength will decrease by that value if it passes that cable(edge).
3. If the signal reaches the terminal with positive signal strength(or zero), it means the signal is sucessfully recevied.
4. If the signal from server can successfully reachs the terminal, the terminal is feasible. Otherwise, it is infeasible.
In most cases, not all terminals are feasible. The IT section gives a proposal: the signal amplifier. A signal amplifier will reconstruct the signal and resets the signal strength as the initial value at server(root). It can be installed on switches.Howe
ver, an amplifier cannot recover the negative signal.
Goal
To reduce the cost, for a specific network, we are curious about the minimal quantitiy of signal amplifier when all terminals are feasible.
Input
1. The first line is an integer N, indicating the total number of nodes in the network.
2. The root is defined as the first node.
3. The description (e.g., no. of children, decay value etc. ) of the i_th node can be found in the i+1_th line. For example, the description of the root node (the first node) is presented in the second line.
4. Each line includes several integers. The first integer k, representing the degree of the node. Then, there are 2*k integers following in pairs. Each pair of integer indicates the index of the child node and the decay value between the child no
de and the current node. (e.g.: 2,2,2,3,1 means the node has two children: node 2 and node 3, with decay values of 2 and 1 respectively).
5. The last line contains an integer a, indicating the initial signal strength.
6. All integers can be saved in an int32 variable.
For 100% TestCase, N<=20000.
Output
An integer, the minimal quantity of signal amplifier that makes all terminals feasible.
If it is impossible, output "No solution." (Pay attention to the capital letter and the full stop)
Sample Input 1 
Sample Output 1
4
2 2 3 3 1
1 4 2
1


Motivation
Long long ago, underneath the material tower at ShanghaiTech university, there is a mysterious lab. In the lab, a magical furnace is there. No one know who built that. There is only a manual for that and an experiment worksheet left by a crazy
scientist.
Furnace manual
203
1000MS
256MB
Standard IO
Created By root
Level Low
Score 100
Tags
Show
The unknown sage defines some rules to use it:
 Statistic
1. When add substances, you must add it from the top.
2. When remove substances, you can only remove it from the bottom.
In the furnace, some rules are found when reaction takes place:
1. only adjacent layer reacts
2.If layer of the same substance stacked, the reaction will regard them as an integrity. For example, if A + B -> C, then 3 layers of substance A and 2 layers of substance B will consume 2 layers of substance of A&B, and generate the 2 layers o
f substance at the middle.
3. If one of the layer can react with the upper one and the lower one at the same time, the reaction with lower layer takes place first.
4. The newly generated substance can be input of other chemical reactions.
5. Due to the gravity, there is no hole between layers of substance after chemical reactions. The upper substance will automatically falls down.
Experiment worksheet
In experiment, you will use at most n kinds of substance, indexed by 0 to n-1.
Among those n kinds of substance, m rules of chemical reaction exist. Each rule transforms two different substance into another one(the three substance involved in a rule are different).
In a whole process of experiment. At first, the magical furnace is empty. Then, Apply a sequence of addition and removal of substance. Between operations, all the substance are fully interacted and steps to a stable condition.
Goal
In the worksheet, k operations are recorded. You have verfied all operations are legal: there is no overflow(You can assume the furnace large enough) or underflow(remove from an empty furnace).
In order to clean the furnace, you are trying to estimate how many layers of substance left in furnace after the experiment.
An example of worksheet from a crazy scientist.
Input
At first line, there are three integers.
1. n: # substance
2. m: # rules of chemical reaction
3. k: # operations
Then, for next m lines, each line includes three integers x, y, z: indicating the rule of x + y -> z.
Finally, for the last k lines, each line includes three integers s, q:
1. s: the index of input substance. If the operation is to remove/output, s is set to -1 by default.
Details2. q: # layers of substance added/removed to/from the furnace(q<10000).
Fall 2019 | CS101 Online Judge
 Home
 Problems
 Contests
e.g: s = 5, q = 2 means add 2 layers of substance 5 to at top of the furnace.
 Status
 Rank 
shenjd@shanghaitech.edu.cn 
 About 
e.g: s = -1, q = 2 means remove 2 layer of substance from the bottom.
For 50% TestCase, n ≤ 20, m ≤ 30, k ≤ 50
For 80% TestCase, n ≤ 1000, m ≤ 5000, k ≤ 10000
For 100% TestCase, n ≤ 3000, m ≤ 100000, k ≤ 300000
Output
Only an integer in one line, indicating the layers of substance left in the furnace.
Sample Input 1 
Sample Output 1
5 5 10
2
1
1
0
3
4
2
4
7400
4
3
0
2
2 4 0
0 885
2 1011
4 461
2 1551
2 995
2 1276
0 1387
-1 1844
0 1863
1 276
Hint
We provide compiled AC code on Ubuntu/Windows. If you are puzzled with the input/output, you can write your own testcase based on it.
This code could only handle legal input.
Windows version:mf.exe
Ubuntu version:mf.o
MacOS version:mf.out
Update10/26:
We have detected that some of you have used standard library in your programming homework, which is forbidden in your homework.
If you have ACed your homework by standard libary,we will record your score to 0 after DDL.
And we will judge this by the latest submission of each sub-homework.
CS101 TA Team