## HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

# Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

### Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

### Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

# A. Juicer

time limit per test

1 second

memory limit per test

256 megabytes

Kolya is going to make fresh orange juice. He has n oranges of sizes a1, a2, ..., an. Kolya will put them in the juicer in the fixed order, starting with orange of size a1, then orange of size a2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

### Input

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

### Output

Print one integer — the number of times Kolya will have to empty the waste section.

### Note

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

## HDU5840 Special Tetrahedron 暴力计算几何

http://acm.hdu.edu.cn/showproblem.php?pid=5839

# Special Tetrahedro

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

### Problem Description

Given n points which are in three-dimensional space(without repetition).

Please find out how many distinct Special Tetrahedron among them. A tetrahedron is called Special Tetrahedron if it has two following characters.

1. At least four edges have the same length.

2. If it has exactly four edges of the same length, the other two edges are not adjacent.

### Input

Intput contains multiple test cases.

The first line is an integer T,1≤T≤20, the number of test cases.

Each case begins with an integer n(n≤200), indicating the number of the points.

The next n lines contains three integers xi,yi,zi, (−2000≤xi,yi,zi≤2000), representing the coordinates of the ith point.

### Output

For each test case,output a line which contains"Case #x: y",x represents the xth test(starting from one),y is the number of Special Tetrahedron.

2
4
0 0 0
0 1 1
1 0 1
1 1 0
9
0 0 0
0 0 2
1 1 1
-1 -1 1
1 -1 1
-1 1 1
1 1 0
1 0 1
0 1 1

Case #1: 1
Case #2: 6

UESTC

### Source

2016中国大学生程序设计竞赛 - 网络选拔赛