課程名稱︰資料結構與演算法
課程性質︰資工系大一必修
課程教師︰張智星
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰2017/04/25
考試時限（分鐘）：上機考 80 mins
試題 :
*本次考試有筆試與上機考兩部分，此為上機考
For each of the following problems, the time limit is 1 second, and the memory
limit is 256MB.
1. (25 pts) Container identification:
Problem description:
Given an empty container, one can perform n operations, with each of them being
either "add" (put an integer xi into it) or "remove" (take an integer xi out of
it). Determine the type of the container based on the result of these n
operations.
Input format:
The first line is an integer indicating n, the number of operations.
Each of the following n lines contains two integers, ti and xi:
ti: 1 for "add", 2 for "remove"
xi: the integer for "add", or the integer returned from "remove".
Output format:
Please output one of the following answers:
both: The container is both a stack and a queue.
stack: The container is a stack, not a queue.
queue: The container is a queue, not a stack.
neither: The container is neither a stack nor a queue.
Ranges of variables:
1 <= xi,n <= 2*10^5
Test cases:
Input (p01_input01.txt):
4
1 10
2 10
1 20
2 20
Output (p01_output01.txt):
both
Input (p01_input02.txt):
4
1 10
1 20
2 20
2 10
Output (p01_output02.txt):
stack
Input (p01_input03.txt):
4
1 10
1 20
2 10
2 20
Output (p01_output03.txt):
queue
Input (p01_input04.txt):
4
1 10
1 20
2 30
2 40
Output (p01_output04.txt):
neither
2. (25 pts) Game of Ongress:
Problem description:
To play the game of Ongress, you need to walk along a street of nn blocks.
When you walk through block i, you earn pi points. You plan to play Ongress
m times. The jth time you play Ongress, you plan to walk from block uj to vj,
so you can collect points for each block you walk through, including block uj
and vj. Compute how many points you will earn each time you play Ongress.
Input format:
The first line contains two integers, n and m.
The second line contains n integers, p1,p2,…,pn
Each of the following mm lines contains two integers, uj and vj.
Output format:
On the jth line (j=1,2,…,m), print the amount of points you earn at the jth
time you play Ongress.
Ranges of variables:
1 <= n,m <= 2*10^5
1 <= pi <= 10^9
1 <= ui <= vi <= n
Test cases:
Input (p02_input01.txt):
5 3
10 30 50 20 40
1 5
1 2
4 4
Output (p02_output01.txt):
150
40
20
3. (25 pts) Story of Untied Airline:
Problem Description:
Untied Airline have n employees. The salary of the ith employee is wi per
month. On the first day of month j (j=1,2,…,m), one of two things could
happen:
If t_j=1, a new employee with salary v_j per month joined the airline.
If t_j=2, all employees with salary higher than v_j per month were laid
off.
Assuming all empolyees received their salary on the last day of the month,
compute the total amount the airline paid to its employees from month 1 to
month m.
Input format:
Line 1 contains two integers, nn and mm.
Line 2 contains nn integers, w1,w2,…,wn.
Each of the following m lines contains two integers, tj and vj.
Output format:
Print an integer, the total amount the airline paid.
Ranges of variables:
1 <= n,m,wi,ti <= 2*10^5
Test cases:
Input (p03_input01.txt):
4 2
30000 40000 50000 60000
1 22000
2 35000
Output (p03_output01.txt):
254000
4. (25 pts) A tree or not:
Problem Description:
In a country, there are n cities connected by m roads, where road j connects
city uj and vj. (Note that each pair of cities are connected by at most one
road, and no road connects a city to itself.) If any two given cities can be
connected by a unique path (consisting of one or several roads), then the
road system is a tree. Determine if the road system is a tree or not.
Input format:
Line 1 contains two integers, n and m.
Each of the following mm lines contains two integers, uj and vj,
indicating there is a road between cities uj and vj.
Output format:
Print yes if the road system is a tree. Print no otherwise.
Ranges of variables:
1 <= n,m <= 5*10^3
1 <= ui <= vi <= n
Test cases:
Input (p04_input01.txt):
3 2
1 3
2 3
Output (p04_output01.txt):
yes
Input (p04_input02.txt):
5 4
1 2
1 3
3 4
3 5
Output (p04_output02.txt):
yes
Input (p04_input03.txt):
6 6
1 2
1 3
2 4
3 4
4 5
5 6
Output (p04_output03.txt):
no
Input (p04_input04.txt):
6 4
1 2
2 3
4 5
5 6
Output (p04_output04.txt):
no
(Total score = 100)