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




可复制的 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