No.1279 Array Battle
platinum
leafirbyProblem Statement
A and B each have a sequence of positive integers with $N$ elements, $a,b$ respectively. The $i$-th elements are $a_i,b_i$ respectively.
The two play a game using these sequences. The actions on turn $i$ $(i=1,2, \dots,N)$ are as follows.
・A freely chooses one element from $a$ that has not been chosen yet. B chooses $b_i$.
・If the element chosen by A is larger, A gains points equal to the difference. Otherwise, the score does not change.
There are $N!$ ways in total for A to choose the elements. Among them, how many ways of choosing the elements maximize the score A obtains?
Input
$N$ $a_1\ a_2\ \dots\ a_N$ $b_1\ b_2\ \dots\ b_N$
・All inputs are integers.
・$1 \le N \le 9$
・$1 \le a_i, b_i \le 10^8$
Output
Output the number of ways of choosing the elements that maximize the score A obtains.
Sample
Sample 1
Input
2 3 4 1 4
Output
1
A can obtain $3$ points by choosing $4$ on turn $1$.
If A chooses $3$ on turn $1$, A can obtain only $2$ points.
There is $1$ way to reach the maximum score of $3$ points, so output $1$.
Sample 2
Input
3 5 5 5 7 5 6
Output
6
There is nothing A can do: the score is $0$ no matter how the elements are chosen.
There are $6$ ways in total to choose the elements, so output $6$.
Sample 3
Input
5 6 5 5 4 4 1 3 5 7 9
Output
28
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。