A - 天下一有無

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

天下一株式会社では、天下一級の物質「Tenkaitium」を製造している。
「Tenkaitium」は、次世代量子コンピューターの製造に欠かせない物質となっている。
新人のユウヤ君は、「Tenkaitium」の運用・管理チームに配属されることになった。
配属されてからのユウヤ君の初仕事は、運搬のため、容器に「Tenkaitium」を入れる作業をすることになった。しかし、「Tenkaitium」には、ある一定量以上が接近すると「Tenkanitium」に変化してしまうという特性がある。残念ながら「Tenkanitium」に産業的価値はない。
そこで、ユウヤ君は、容器を N \times Mのマスに区切り、「Tenkaitium」が同じマスに2つ以上入ったり、縦、横、ななめに隣り合あったマスに入ったりしないように配置することを考えた。

入力

入力は以下の形式で標準入力から与えられる。 

N M
  • 1 \leq N,\ M \leq 15

出力

「Tenkaitium」を縦、横、ななめに隣り合わないように1つ以上配置する方法が何通りあるかを {\rm mod}\ 1000000007 で標準出力に1行で出力せよ。ただし、回転や反転によって同じになる配置も別々のものとする。
また、行の終端には改行が必要である。

入力例 1

2 2

出力例 1

4

「Tenkaitium」が有るマスを■、無いマスを□とすると以下の 4 通りの配置が考えられる。

入力例 2

3 2

出力例 2

10

以下の 10 通りの配置が考えられる。

B - 天下一マジック

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

どこかの会社の社長である高橋くんは社員を楽しませるためにマジックを披露しようと考えました。 マジックを成功させるためには一見ランダムに並んでいるカードを社員に気付かれないように素早くソートしなければなりません。

使うカードの枚数2N+1は必ず奇数で、便宜上それぞれのカードは1番から2N+1番の番号が書かれているものとします。 高橋くんは次の2通りの操作を連続して行いカードを並び替えていきます。 ただし、Xは1以上2N+1未満の整数から成る集合です。

操作1（カット）:
集合Xの要素Kを選び、カードの先頭からK枚抜き取り、そのままの順番でカードの末尾に置く。 例えば、K=3の場合は、この操作で[5, 1, 4, 7, 6, 2, 3] → [7, 6, 2, 3, 5, 1, 4]となる。

操作2（リフルシャッフル）:
カードの先頭からN+1枚のカードと、残りのN枚のカードに分けて、 先頭から1枚ずつ交互にカードを取っていく。この際、最初はN+1枚のカードからなるグループから取る。 例えば、この操作で[5, 1, 4, 7, 6, 2, 3] → [5, 6, 1, 2, 4, 3, 7]となる。

カードの初期配置と集合Xが与えられるので、高橋くんがカードを昇順に並び替えるのに必要な操作の数の最小値を求めなさい。 ただし、カードを完全に昇順に並び替えるのが不可能な場合は-1を出力しなさい。

入力

入力は以下の形式で標準入力から与えられる。 

N M
C_1 C_2 ‥‥ C_{2N+1}
K_1 K_2 ‥‥ K_M
  • 入力は3行ある。
  • 1行目には、Nと集合Xの要素の数Mが空白区切りで与えられる。
  • 2行目には、カードの初期配置として2N+1個の整数が空白区切りで与えられる。
    • i番目の整数C_iは先頭からi番目のカードに書かれている数字を表している。
    • カードには1から2N+1までの整数がちょうど1回ずつ書かれている。
  • 3行目には、集合Xの要素としてM個の整数が空白区切りで与えられる。
    • i番目の整数K_iは1≦K_i＜2N+1を満たす。
    • 3行目では同じ整数が2回以上与えられることはない。
    • M=0の場合は、3行目は空行（改行のみ）となる。

部分点

  • 1≦N≦4、X=\{1\}（M=1、K_1=1）の入力に正解すると、200 点満点に対して部分点として、20 点が与えられる。
  • 1≦N≦2013、X=\{1\}（M=1、K_1=1）の入力に正解すると、200 点満点に対して部分点として、上記とは別に 80点が与えられる。
  • 0≦N≦2013、0≦M＜2N+1の入力に正解すると、200 点満点に対して残りの 100 点が与えられる。

出力

カードを昇順に並び替えるのに必要な操作の数の最小値を標準出力に1行で出力せよ。
ただし、カードを昇順に並び替えることができない場合は、操作の数の最小値の代わりに-1を出力せよ。
なお、最後には改行を出力せよ。

入力例 1

1 1
3 2 1
1

出力例 1

2
  • 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
    • 操作2を行います。[3, 2, 1] → [3, 1, 2]
    • K=1として操作1を行います。[3, 1, 2] → [1, 2, 3]

入力例 2

2 1
3 2 5 1 4
1

出力例 2

-1
  • この場合はどうやっても昇順に並び替えることはできません。

入力例 3

2 1
4 2 5 3 1
1

出力例 3

4
  • 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
    • 操作2を行います。[4, 2, 5, 3, 1] → [4, 3, 2, 1, 5]
    • 操作2を行います。[4, 3, 2, 1, 5] → [4, 1, 3, 5, 2]
    • K=1として操作1を行います。[4, 1, 3, 5, 2] → [1, 3, 5, 2, 4]
    • 操作2を行います。[1, 3, 5, 2, 4] → [1, 2, 3, 4, 5]

入力例 4

3 1
1 2 3 4 5 6 7
1

出力例 4

0
  • 最初から昇順になっているため、必要な操作回数の最小値は0となります。

入力例 5

4 2
2 3 4 5 6 7 8 9 1
1 6

出力例 5

3
  • 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
    • K=1として操作1を行います。[2, 3, 4, 5, 6, 7, 8, 9, 1] → [3, 4, 5, 6, 7, 8, 9, 1, 2]
    • K=6として操作1を行います。[3, 4, 5, 6, 7, 8, 9, 1, 2] → [9, 1, 2, 3, 4, 5, 6, 7, 8]
    • K=1として操作1を行います。[9, 1, 2, 3, 4, 5, 6, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8, 9]
C - 天下一ジグソーパズルみたび

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたパズル作家のショウヘイ君は、天下一プログラマーコンテストのポスターを下図のようにN \times M のピースに分割したジグソーパズルを作った。

上下左右に隣り合うピースの一辺は一方が凸に他方が凹になっており、外周の辺は直線になっている。

ショウヘイ君は一度バラバラにしたポスターを、2つの辺がくっつくかどうかを試していき元々くっついていた辺を探すことで、元のポスターを復元するプログラムを制作することにした。

入出力

まず、入力が以下の形式で標準入力から与えられる。 

N M Q
P_{1, 1} P_{1, 2} P_{1, 3} P_{1, 4}
P_{2, 1} P_{2, 2} P_{2, 3} P_{2, 4}
...
P_{N \times M, 1} P_{N \times M, 2} P_{N \times M, 3} P_{N \times M, 4}
  • パズルの縦幅 N、横幅 M ( 2 \leq N, M \leq 8 ) 、質問回数の上限 Q ( 3 \leq Q \leq 10000 ) が、スペースで区切られて、それぞれ整数で与えられる。
  • 続く N \times M 行で、i 番目のピースの上辺 P_{i, 1}、右辺 P_{i, 2}、下辺 P_{i, 3}、左辺 P_{i, 4}が与えられる。ただし、P_{i, j} = 0は直線、P_{i, j} = 1は凸、P_{i, j} = 2は凹を意味する。

あなたのプログラムは、2つのピースのある辺と辺が繋がるかどうかを、以下の形式で標準出力を用いて質問することができる。 

? a d_a b d_b
  • a 番目のピースの方向 d_a の辺と、b 番目のピースの方向 d_b の辺をつなげるのが正解かどうかを質問する。
  • 1 \leq a, b \leq N \times M
  • d_a, d_bは、上辺を1、右辺を2、下辺を3、左辺を4とする。
  • 応答プログラムは、質問された辺がつながるのが正解であればyesを、そうでなければnoを出力する。

最後に、ジグソーパズルの並べ方を以下の形式で標準出力を用いて回答する。 

!
p_{1, 1} d_{1, 1} p_{1, 2} d_{1, 2} ... p_{1, M} d_{1, M}
p_{2, 1} d_{2, 1} p_{2, 2} d_{2, 2} ... p_{2, M} d_{2, M}
...
p_{N, 1} d_{N, 1} p_{N, 2} d_{N, 2} ... p_{N, M} d_{N, M}
  • i 行目の j 列目に p_{i, j} 番目のピースを入力で与えられた上辺を方向 d_{i, j} にして置く。
  • d_{i, j} は、上を1、右を2、下を3、左を4とする。
  • ジグソーパズル全体の向きは問わない。すなわち、ジグソーパズル全体が正解に対して180度回転していても構わない。N = Mであれば90度または270度回転していても構わない。

部分点

  • Q = 10000 の入力に正解すると、160 点満点に対して部分点として、50 点が与えられる。
  • Q = 3000 の入力に正解すると、160 点満点に対して部分点として、上記とは別に 60 点が与えられる。
  • 残り 50 点に対しては 25 の入力があり、入力を一つ正解するごとに部分点として 2 点が与えられる。各入力の N, M, Q を下表に示す。
    NMQ
    1571000
    2751000
    3851000
    4581000
    5661000
    6661000
    756500
    865500
    955500
    1046500
    1164500
    1245200
    1354200
    1444100
    154480
    164470
    174350
    183440
    193425
    203325
    213315
    222310
    23237
    24225
    25223

入出力例 1



プログラムの出力プログラムへの入力


2 2 100
0 0 1 2
0 1 2 0
0 0 2 2
1 1 0 0


? 1 4 2 2


no


? 1 3 2 3


yes


!
1 4 2 2
4 1 3 2
D - 天下一ボディービルコンテスト

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、頭には自信がありませんが、体には自信があります。そこで、高橋君はボディービルコンテストに出ることにしました。

高橋君には筋肉が N 個ついています。 高橋君は、ボディービルコンテストが開かれるまでの D 日間、毎日トレーニングをすることにしました。

高橋君は、毎日筋肉をひとつ選び、トレーニングしてその筋肉を 1kg 増やします。

高橋君は、ボディービルコンテストで優勝するために、各筋肉をどれだけ増やすか、目標を設定しました。ですが、その目標を達成するために、どのようなスケジュールでトレーニングをすれば良いかが分かりません。

高橋君のために、トレーニングスケジュールが何通りあるかを、mod 1000000007で求めてください。

入力

入力は以下の形式で標準入力から与えられる。 

N D
a_1
a_2
...
a_N
  • 1 行目は、高橋君の筋肉の数 N (1 \leq N \leq 30) と トレーニング日数 D (1 \leq D \leq 10^9) が空白区切りで与えられる。
  • 2 行目から N+1 行目までの N 行は、i (1 \leq i \leq N) 番目の筋肉を最低何kg増やしたいかの目標 a_i\ (1 \leq a_i \leq 30) が与えられる。

部分点

  • N \leq 5,\ a_i \leq 5,\ D \leq 500 の入力に正解すると、280 点満点に対して部分点として、40 点が与えられる。
  • N \leq 5,\ a_i \leq 5 の入力に正解すると、280 点満点に対して部分点として、上記とは別に 100 点が与えられる。

出力

高橋君が全ての目標を達成するための、スケジュールの組み方が何通りあるかを、1000000007 で割った余りを出力しなさい。

また、出力の最後には改行をいれること。

入力例 1

2 3
1
1

出力例 1

6

鍛えるべき筋肉が2つあり、3日間トレーニングします。

スケジュールの組み方は、1日目から順番に、{1,1,2}, {1,2,1}, {1,2,2}, {2,1,1}, {2,1,2}, {2,2,1}の6通りです。

入力例 2

4 4
1
1
1
1

出力例 2

24

鍛えるべき筋肉が4つあり、4日間のトレーニングでそれぞれ1つの筋肉を選ぶ必要があり、その組み合わせは4!=24通りです。

入力例 3

13 12345678
1
2
3
4
5
6
7
8
9
10
11
12
13

出力例 3

910759485
E - 天下一折れ線遊戯

Time Limit: 4 sec / Memory Limit: 64 MB

問題文

x 座標の正の方向を右、y 座標の正の方向を上とします。

紙の上に、

  • 左の方に N 個の赤い点 (0,\ 0),\ (0,\ 1000),\ ...,\ (0,\ 1000(N-1))
  • 右の方に N 個の青い点 (10^9,\ 0),\ (10^9,\ 1000),\ ..., (10^9,\ 1000(N-1))
  • M 個の黒い点 (X_k,\ Y_k)
があります。黒い点の x 座標は全て異なります。

高橋くんは折れ線が大好きです。

それぞれの点 (x_k,\ y_k) について、

  • 何もしない
  • x > x_k,\ y > y_kの領域にある点の中で、 y 座標の値が最も小さい点と線分でつなぐ。そのような点が複数あるなら最も近い点と線分でつなぐ。そのような点がないなら何もしない。
  • x > x_k,\ y < y_kの領域にある点の中で、 y 座標の値が最も大きい点と線分でつなぐ。そのような点が複数あるなら最も近い点と線分でつなぐ。そのような点がないなら何もしない。
  • x > x_k,\ y = y_kの領域にある点の中で、最も近い点と線分でつなぐ。そのような点がないなら何もしない。
のどれか 1 つを行います。

高橋くんは、全ての赤い点に対して、折れ線でちょうど 1 つの青い点と結ばれるようにしたいです。

それぞれの折れ線は交わったり触れたりしてはいけません。また、 N 個の折れ線に含まれない無駄な線分を引いてもいけません。

N 個の折れ線の引き方は何通りあるかを mod 1000000007 で求めてください。

入力

入力は、以下の形式で与えられる。

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M
  1. 1 行目には、赤い点と青い点の数 N\ (1 ≦ N ≦ 3) と、黒い点の数 M\ (0 ≦ M ≦ 100000) が、 1 行で入力される
  2. 2 行目から M+1 行までの M 行では、i 番目の黒い点の x 座標と y 座標を表す整数 X_i,\ Y_i\ (0 < X_i < 10^9,\ 0 ≦ Y_i ≦ 10^9) が与えられる。
    • 黒い点の x 座標は互いに異なります。つまり、i \neq j のとき、X_i \neq X_j を満たします。

部分点

  • N = 1の入力に正解すると、320 点満点に対して部分点として 60 点が与えられる。
  • 0 ≦ M ≦ 40 の入力に正解すると、320 点満点に対して部分点として上記とは別に 60 点が与えられる。

出力

高橋君が引くことが出来る、 N 個の折れ線の引き方は何通りあるかを、出力しなさい。もし組み合わせが 1000000007 通り以上であった場合は、 1000000007 で割った余りを出力しなさい。

また、出力の最後には改行をいれること。

入力例 1

2 2
100 100
110 110

出力例 1

5

(0,\ 0) が1つ目の赤い点（赤1）、(0,\ 1000) が2つ目の赤い点（赤2）、 (1000000000,\ 0) が1つ目の青い点（青1）、(1000000000,\ 1000) が2つ目の青い点（青2）、 (100,\ 100) が1つ目の黒い点（黒1）、(110,\ 110) が2つ目の黒い点（黒2）、と合計で 6 個の点があります。

  • 赤1から線分を引けるのは黒1または青1のみ、
  • 赤2から線分を引けるのは黒2または青2のみ、
  • 黒1から線分を引けるのは黒2または青1のみ、
  • 黒2から線分を引けるのは青1または青2のみ

となります。

交わったり、触れたりせずに折れ線を2個作るには

  • （赤1 - 黒1 - 黒2 - 青1、赤2 - 青2）
  • （赤1 - 黒1 - 青1、赤2 - 黒2 - 青2）
  • （赤1 - 黒1 - 青1、赤2 - 青2）
  • （赤1 - 青1、赤2 - 黒2 - 青2）
  • （赤1 - 青1、赤2 - 青2）
と 5 通りの方法があります。

入力例 2

1 3
500 800
300 500
400 400

出力例 2

3

(0,\ 0) が1つ目の赤い点（赤1）、 (1000000000,\ 0) が1つ目の青い点（青1）、 (500,\ 800) が1つ目の黒い点（黒1）、(300,\ 500) が2つ目の黒い点（黒2）、(400,\ 400) が3つ目の黒い点（黒3）と合計で 5 個の点があります。

  • 赤1から線分を引けるのは黒3または青1のみ、
  • 黒1から線分を引けるのは青1のみ、
  • 黒2から線分を引けるのは黒1または黒3のみ、
  • 黒3から線分を引けるのは黒1または黒2のみ

となります。

赤1と青1をつなぐ折れ線を作るには

  • （赤1 - 青1）
  • （赤1 - 黒3 - 青1）
  • （赤1 - 黒3 - 黒1 - 青1）
と 3 通りの方法があります。

入力例 3

2 2
1000 0
2000 1000

出力例 3

1

赤い点を下から赤1、赤2、 青い点を下から青1、青2、 黒い点を入力で与えられた順番に黒1、黒2とします。

  • （赤1 - 黒1 - 青1、赤2 - 黒2 - 青2）

と 1 通りの方法しかありません。

入力例 4

3 8
500 5000
3500 5000
2000 3500
1500 2000
2500 2000
1000 1000
3000 1000
1 1

出力例 4

48

入力例 5

3 0

出力例 5

1

それぞれの赤い点は、まっすぐ右にある青い点と結びます。

それぞれの折れ線は交差できないため、これ以外の引き方はありません。