すぬけ君は、2015 を 2 進数で表すと 11111011111 となり回文になっていることに気づいた。 整数 N を (余計な 0 をつけない) 2 進数で表したとき、回文になっているかどうか判定せよ。 ただし、左から呼んでも右から読んでも同じ文字列を回文という。

2015

Yes

2016

No

N 個の餅がある。i 番目の餅の重さは a_i である。 すぬけ君は、この中からいくつかの餅を選び好きな順番で積み重ねて、餅の塔を作ることにした。 ただし、ある餅の上に乗っている餅の重さの合計がそのもちの重さ以上になると、餅が割れてしまう。 餅の塔を最大何段にすることができるか求めよ。

5
3
20
5
8
6

3

すぬけ君は、新年のプレゼントに文字列 s をもらった。以下の操作を繰り返すことで s をすぬけ君の好きな文字列 t にできるかどうか判定せよ。

操作: s から文字を一つ選び、その直後に選んだ文字とは異なる文字を一つ挿入する。

snuke
snukent

Yes

snuke
ssnuke

No

すぬけ君が、一次元の無限に長い道路の上に立っている。すぬけ君は、N 種類のジャンプをすることができる。i 番目のジャンプでは、a_i に対して対称な位置にジャンプできる (場所 x にいるとき、場所 2a_i - x に移動する)。

Q 種類のクエリに答えよ。i 番目のクエリでは、s_i から t_i に行くのに最小何回ジャンプすればよいか求めよ。ただしジャンプだけで到達できない場合には、代わりに -1 と出力せよ。

4
1
2
4
7
10
2 3
5 6
6 0
3 7
10 3
7 6
5 5
2 10
4 10
10 10

-1
-1
2
2
-1
-1
0
3
1
0

N 人の人が寝ている。すぬけ君は、N-1 本のひもでこの人たちを結びつけることにした。

• それぞれのひもは、両端を異なる人に結びつけることによって、その二人を結びつけることができる。
• どの二人も直接的または間接的にひもでつながっているようにしたい。
• i 番目の人にはちょうど a_i 本のひもがつながっているようにしたい。

ひもの結び付け方は何通りあるか、\rm{mod}\ 1,000,000,007 で求めよ。

9
1
3
2
1
3
1
2
1
2

1260

すぬけ君が番号札を N 個持っている。i 番目の番号札には数字 a_i が書いてあり、色は c_i である。

すぬけ君は、ある正整数 M が存在し、数字と色の間には以下のような関係があるのではないかと考えた。

• 1,\ ...,\ M は同じ色で塗られている。
• M+1,\ ...,\ 2M は別の同じ色で塗られている。
• 2M+1,\ ...,\ 3M は別の同じ色で塗られている。
• ...

M として何通りの数が考えられるか求めよ。ただし、M の値が無限通り考えられる場合には、-1 を出力せよ。

4
27 2
2000 4
2015 4
2100 1

277

3
1 1
2 2
3 1

0

すぬけ君は N 個のロボットを持っている。最初に、i 番目のロボットは座標 (x_i, y_i) に向き d_i の方向を向いて止まっている。 d_i は U, D, L, R のいずれかであり、それぞれ y 座標の正の方向、 y 座標の負の方向、 x 座標の負の方向、 x 座標の正の方向を表す。

このロボットは、何か (すぬけ君または他のロボット) に触れると向いている方向に毎秒 1 の速さで動き出す性質がある。また、このロボットはすり抜けることができるので、動いているロボットが他のロボットに衝突しても止まったり運動の向きや速さが変わることはない。

すぬけ君は、時刻 0 にロボット 1 をさわった。時刻 T のそれぞれのロボットの座標を求めよ。

5 10
1 0 U
3 1 U
1 2 R
1 1 L
0 1 R

1 10
3 6
9 2
-8 1
8 1

6
1 7
8 5
6 3
10 3
5 2
6 10

9

すぬけ君は、配列 P と Q をマージして配列 R を作ることにした。

• 最初に、R は空である。
• P または Q が空でない間、P または Q のうち空でない配列 (両方空でない場合は好きなほう) を選び、その配列の左端の要素を取り出し、R の右端にくっつける。

4
3 1 2 4
3 1 2 4

14

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

127224

無限に広い二次元のマス目がある。このマス目の座標は二つの整数 i, j を用いて (i, j) と表せる。

すぬけ君は、(0, 0) から出発し、N 歩ランダムウォークを行う。(i, j) にいるとき、一歩進むとそれぞれ 1/4 ずつの確率で (i-1, j), (i, j-1), (i, j+1), (i+1, j) に進む。

2 1000000007

44

2015 2000000000

1892319232

N 人の人がチーム戦の練習を行うことになった。 すぬけ君は、次の条件を満たすように練習のスケジュールを組みたい。

• 練習は 1 日以上 N^2 日以下行われる。
• 毎日 N 人のうち 3 人が練習をする。
• 人 p と人 q が同時に練習する回数を f(p, q) としたとき、f(p, q) が任意の二人組について等しくなるようにしたい。

5

10
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

すぬけ君の机には N 個のしみがついている。 i 番目のしみの座標は (x_i, y_i) である。

すぬけ君は、しみを何個か (0 個でもよい) 付け足してしみ全体がボードゲームの盤面となるようにしたい。すぬけ君の作りたい盤は、ある K に対して、K^2 個のしみが K \times K の正方格子状に並んでいるようなものである。ただし、盤面が座標軸に平行である必要はない。

すぬけ君が書き足さなければならないしみの個数の最小値を求めよ。 ただし、机は十分広く、しみが机をはみ出すことはないものとする。

3
1 5
3 6
4 9

6

すぬけ君は、絵を描くことにした。 最初に、すぬけ君は細長い白い紙を用意し、1 \times N のマス目に区切った。 次に、すぬけ君は、K 回の操作を行う。 i 回目の操作では、連続する a_i このマス目を選び、全て黒く塗る。 この操作では、選ばれたマス目のうち白かったものは黒に変わり、もともと黒かったマスはそのままである。

すぬけ君が何通りの絵をかくことができるか、\rm{mod}\ 1,000,000,007 で求めよ。 二つの絵はあるマス目の最終的な色が異なるときに異なる絵であるとみなす。 回転して同じになる絵でも異なるものとみなす。

10 2
1
1

55

1000000000 4
2015
2015
123456789
27

782767239