← 返回题目列表

AtCoder · joisc2012_kangaroo

kangaroo. 袋鼠

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

カンガルー - 原题 PDF 第 1 页
原题PDF第4页
カンガルー - 原题 PDF 第 2 页
原题PDF第5页
カンガルー - 原题 PDF 第 3 页
原题PDF第6页
カンガルー - 原题 PDF 第 4 页
原题PDF第7页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 3 – Kangaroo

                  カンガルー(Kangaroo)



 K 理事長はカンガルーに興味を持ち,カンガルーの行動を観察することにした.K 理事長はN 匹のカン
ガルーを観察している.カンガルーにはポケットが一つずつ付いている.カンガルーには1, 2, · · · , N の番
号が付けられている.カンガルーi の本体のサイズはAi であり,カンガルーi のポケットのサイズはBi で
ある.ポケットのサイズはそのカンガルーの本体のサイズより小さい(Ai > Bi).
 最初にどのカンガルーのポケットの中にも他のカンガルーは入っていない.カンガルーは以下の操作を
操作ができなくなるまで繰り返す.
  Ai < Bj を満たすカンガルーi とカンガルーj の組であって,カンガルーi が他のカンガルーのポケット
の中ではなく,カンガルーj のポケットの中に他のカンガルーがいないようなものが存在するとき,カン
ガルーi はカンガルーj のポケットの中に入る.このとき,カンガルーi のポケットの中に他のカンガルー
がいても,カンガルーj が他のカンガルーのポケットの中にいても構わない.そのような(i, j) の組が複数
存在するとき,どの組が選ばれるか分からない.カンガルーi の中に他のカンガルーが入っている場合,中
のカンガルーはカンガルーi と一緒に移動する.
 与えられたカンガルーの本体とポケットのサイズに対して,最後の状態が何通りあるかを1 000 000 007 (=
109 + 7) で割った余りを求めたい.


課題

 カンガルーの本体とポケットのサイズが与えられたとき,最後の状態が何通りあるかを1 000 000 007 (=
109 + 7) で割った余りを求めるプログラムを作成せよ.


制限

   1 ≦N ≦300        カンガルーの匹数
   1 ≦Bi < Ai ≦1 000 000 000    i 匹目のカンガルーのポケットと本体のサイズ





                     カンガルー– 1 / 4

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 3 – Kangaroo


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数N が書かれている.N はカンガルーの匹数を表す.
   • 続くN 行にはカンガルーの情報が書かれている.i + 1 行目(1 ≦i ≦N) には2 つの整数Ai, Bi が空白
   を区切りとして書かれている.Ai はi 匹目のカンガルーの本体のサイズを,Bi はi 匹目のカンガルー
   のポケットのサイズをそれぞれ表す.


出力

 標準出力に,最後の状態が何通りあるかを1 000 000 007 (= 109 + 7) で割った余りを表す整数を1 行に出
力せよ.


採点基準

 採点用データのうち,配点の50% 分についてはN ≦30 を満たす.
 採点用データのうち,配点の70% 分についてはN ≦70 を満たす.





                     カンガルー– 2 / 4

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 3 – Kangaroo


入出力の例

  入力例1        出力例1
   5                    4
   4 3
   3 1
   6 5
   2 1
   4 2

 カンガルー1,カンガルー2,およびカンガルー5 はカンガルー3 のポケットに入ることができる.また
カンガルー4 はカンガルー1 またはカンガルー3 のポケットに入ることができ,カンガルー3 は他のどの
カンガルーのポケットにも入ることはできない.よって,最後の状態としてありうるのは以下の4 通りで
ある.

   • カンガルー4 がカンガルー3 のポケットに入っている.
   • カンガルー4 はカンガルー1 のポケットに入っており,カンガルー1 はカンガルー3 のポケットに
   入っている.

   • カンガルー4 はカンガルー1 のポケットに入っており,カンガルー2 はカンガルー3 のポケットに
   入っている.

   • カンガルー4 はカンガルー1 のポケットに入っており,カンガルー5 はカンガルー3 のポケットに
   入っている.





                     カンガルー– 3 / 4

Japanese Olympiad in Informatics 2011/2012
                                                        Spring Training Camp/Qualifying Trial
                                            March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                     Contest Day 3 – Kangaroo


入力例2        出力例2
20                   21060
7 6
7 3
10 1
7 2
10 7
10 7
8 6
3 2
5 4
7 2
3 2
10 9
9 4
7 2
8 6
5 4
8 6
7 4
10 5
9 3





                    カンガルー– 4 / 4