409389: GYM103496 B2 Basketbology (Counting)

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B2. Basketbology (Counting)time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Cindy was tasked with organizing her school's sportsfest this year. In addition to normal competitions like volleyball, tug of war, and an actual basketball match, Cindy thinks that it would be exciting to start off the sportsfest with a special basketball jump shot competition.

She has chosen $$$n$$$ of her classmates to participate in the jump shot competition. There are $$$n$$$ marks on the ground (drawn in chalk), placed such that the $$$i$$$th mark is $$$x_i$$$ units away from the basket. Cindy will assign one person to each mark, and she tells each person to stand at their assigned mark. Each person will then be asked to try to shoot the ball into the basket from their respective locations. For each classmate, we know their "skill level" is some numerical value $$$c_i$$$, meaning that they will successfully land their shot if and only if they shoot from a distance of $$$c_i$$$ units from the basket or closer.

Cindy believes that the sportsfest will start with a bang if all her classmates successfully land their shot. Unfortunately, she wasn't able to communicate this to Bob, who just totally randomly assigned students to marks. In light of this, Cindy is instead interested in finding the exact probability that a randomly chosen assignment of students to marks will result in all her classmates landing their shot successfully.

Recall that there are $$$n!$$$ ($$$n$$$ factorial) different ways to assign students to marks. Among them, count the number of assignments that result in all $$$n$$$ people landing their shot successfully.

Input

The first line of input contains a single integer $$$n$$$.

The second line of input contains $$$n$$$ space-separated integers $$$x_1, x_2, \dots, x_n$$$, the distances of each mark from the basket.

The third line of input contains $$$n$$$ space-separated integers $$$c_1, c_2, \dots, c_n$$$, the skill levels of Cindy's classmates.

Output

Output a single integer, the number of assignments of students to marks such that all of them land their shots successfully. Two assignments are considered different if there exists a student that was assigned somewhere else between the two ways.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq x_1 < x_2 < \dots < x_n \leq 12345 \\ 1 \leq c_i \leq 12345 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{35} & 1 \leq n \leq 3 \\ \hline 2 & \mathbf{32} & 1 \leq n \leq 8 \\ \hline 3 & \mathbf{32} & 1 \leq n \leq 20 \\ \hline 4 & \mathbf{1} & 1 \leq n \leq 12345 \\ \hline \end{array}\\

\end{align*}$$$$$$

ExamplesInput
3
10 15 20
28 16 18
Output
2
Input
3
10 15 20
24 13 13
Output
0
Note

In the first sample input, there are $$$2$$$ valid assignments. We can assign the first student to the $$$20$$$ mark, the second student to the $$$10$$$ mark, and the third student to the $$$15$$$ mark. Or, we can assign the first student to the $$$20$$$ mark, the second student to the $$$15$$$ mark, and the third student to the $$$10$$$ mark.

In the second sample input, none of the assignments are valid.

加入题单

上一题 下一题 算法标签: