商品の入出荷 3 Erlang(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
同じ種類の商品について、以下のような 2n 個の入出荷情報が与えられます。
・ i 番目の出荷情報は整数の組 (a_i, b_i) で表される。
・ a_i = 1 のとき、商品が入荷されることを表す。
・ a_i = 2 のとき、商品が出荷されることを表す。
・ 入荷または出荷される商品の個数は常に 1 である。
・ b_i は、入荷の場合、入荷可能な最後の時刻を、出荷の場合、出荷可能な最初の時刻を表す。
・ 入荷情報および出荷情報はそれぞれちょうど n 個ずつ存在する。
ここで、各商品の入荷と出荷をすべて組み合わせたとき、それぞれの商品を請け負っている業者どうしは協力して入荷時間と出荷時間との差が最小になるように可能な時間内で調整をおこなうと仮定します。
そのような仮定のもとで、各商品の入荷と出荷をすべて組み合わせる方法であって、(出荷時間 - 入荷時間) の総和が t となるものの個数を求めてください。
ただし、各商品の入荷と出荷を組み合わせる方法とは、整数 1 から 2n までの並べ替え p_1, p_2, ..., p_{2n} であって、
a_{p_2k} = 1 かつ a_{p_{2k+1}} = 2 (1 ≦ k ≦ n) を満たすもののことを指します。
なお、入荷時刻が出荷時刻よりも真に早いか同じ場合のみ、入荷と出荷の組み合わせが可能であるものとします。
例えば、入力例 1 では、時刻 1, 2 に入荷期限があり、時刻 3, 4 に出荷開始があります。
よって、それぞれの時刻の情報の番号を順に 1, 2, 3, 4 とすると、
(1, 3), (2, 4) および (1, 4), (2, 3) の 2 通りの組み合わせについて、
それぞれ (出荷時間 - 入荷時間) の総和が (3 - 1) + (4 - 2) = (4 - 1) + (3 - 2) = 4 となり、条件を満たします。
(このときの入荷時間および出荷時間は入荷期限および出荷開始に一致します。)
- 入力される値
-
n t
a_1 b_1
a_2 b_2
...
a_2n b_2n
・ 1 行目に、入出荷情報の個数 (の半分) を表す整数 n と、目標となる総和時間を表す整数 t が半角スペース区切りで与えられます。
・ 続く 2n 行に、整数 a_i, b_i が半角スペース区切りで与えられます。a_i が 1 の場合は入荷、2 の場合は出荷を表します。b_i は商品の入荷または出荷の時刻を表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを 10^9 + 7 で割った余りを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 20
・ 1 ≦ t ≦ 800
・ 1 ≦ a_i ≦ 2 (1 ≦ i ≦ 2n)
・ a_i = 1 となる i はちょうど n 個存在する
・ a_i = 2 となる i はちょうど n 個存在する
・ 1 ≦ b_i ≦ 40
・ b_i ≠ b_j (1 ≦ i, j ≦ 2n, i ≠ j) (与えられる入荷可能な最後の時刻および出荷可能な最初の時刻はすべて異なる)
- 入力例1
-
2 4
1 1
1 2
2 3
2 4
- 出力例1
-
2
- 入力例2
-
3 6
2 5
1 1
1 2
2 3
1 6
2 4
- 出力例2
-
2
