配点

満点

30

問題文

あなたはプログラミングコンテストに参加している。 このコンテストには問題が N問あり、それぞれの問題はPi\（1≤i≤N）個の部分問題に分割されている。i番目の問題について、j個目の部分問題を解くと、その問題の得点はs_i_jになる。

それぞれの問題では、i番目の部分問題を解くにはi-1番目の部分問題を先に解いておく必要がある。

たとえば、ある問題に3つの部分問題が設定されており、部分点が 3点,6点,10点 と指定されている場合、まず1つめの部分問題を解くと3点が得られ、次に2つめを解くと6点、3つめまでを解くと満点の10点が得られる（部分点が加算されて合計19点になるわけではないことに注意）。

あなたは、簡単に解けそうなところから解こうと考え、配点が小さい部分問題から順に取り組んでいくことにした。 同じ配点の部分問題が複数あった場合は、問題番号が小さいものを先に取り組む。

それぞれの部分問題を解くのに必要な時間t_i_jとコンテスト全体の時間Tが与えられたとき、コンテスト終了までにあなたは何点獲得できるかを求めよ。

コンテスト終了時間と部分問題が解けた時間が同時だった場合、その部分問題も解けたものに含める。

入力例 1

3 100
1 2 2
100
15 150
30 200
20
10 30
20 40

出力例 1

280

問題2-1(15点)→問題3-1(30点)→問題1-1(100点)→問題2-2(150点)の順に解く。 問題3-2を解いている間にコンテストが終了する。

100+150+30で280点。

入力例 2

3 120
1 2 2
100
15 150
30 200
20
10 30
20 40

出力例 2

450

時間ちょうどに問題3-2が解ける。

100+150+200で450点。

入力例 3

2 100
2 3
15 100
3 100 200
10 90
5 40 40

出力例 3

18

入力例 4

3 75
1 1 1
250
500
1000
100
300
1000

出力例 4

0

入力例 5

11 300
1 1 2 2 2 3 2 2 2 3 2
30
50
10 60
30 90
20 100
20 40 100
30 110
30 120
40 120
20 40 140
100 150
10
15
10 15
10 20
15 30
15 40 60
40 60
30 50
40 50
10 20 100
100 150

出力例 5

430

配点

満点

60

部分点

10

問題文

N 枚のカードが全て表を向いて並んでいる。それぞれのカードの表側には数字 X_i が書かれている。あなたは以下の操作を行う。

1. 表になっているカードのうち無作為に2枚を選んで裏返す。
2. 裏になっているカードのうち無作為に1枚を選んで裏返す。このとき選んだカードの表に書かれている数字をスコアに加算する。
3. 表になっているカードが2枚以上あれば1に戻る。表になっているカードが1枚しかなければ操作を終了する。

操作を終了したときのスコアの期待値を求めよ。

入力例 1

2
10 21

出力例 1

15.5

まず、表になっている2枚を両方裏返す。

次に、裏になっている2枚から無作為に1枚を選んで表にする。このときカードに書かれた分の点数を得ることができる。

この時点で表になっているカードは1枚しかないので、操作を終了する。

10が選ばれる確率は0.5で、21が選ばれる確率は0.5なので、期待値は10*0.5 + 21*0.5 = 15.5となる。

入力例 2

3
1 2 3

出力例 2

4

入力例 3

13
748 401 960 630 659 363 612 514 258 361 914 107 149

出力例 3

6162.4615384

配点

満点

90

部分点

30

問題文

数列 \{A_i\} は次のように定義される。

• A_1=0
• A_2=1
• i > 0 のとき、 A_{i+2}=A_{i+1}^2 + A_i^2

A_n を整数 M で割った余りを求めよ。

Hint: この問題はネタ枠なので、あまり真剣に考え込まないことをおすすめします。

入力例 1

6 1999

出力例 1

29

数列 \{A_i\} の最初の6項は、0,1,1,2,5,29である。

入力例 2

123456789 1999

出力例 2

460

入力例 3

987654321 1000000007

出力例 3

75019086

配点

満点

100

部分点

20

問題文

N人の人間が、2次元平面上の格子点にいる。初期状態では各人の座標は異なる。

1ターン目で、各自が上下左右いずれかの方向へちょうど1だけ進む。

2ターン目で、各自が上下左右いずれかの方向へちょうど2だけ進む。

同様に、iターン目には各自が上下左右いずれかの方向へちょうどiだけ進む。

これを繰り返し、あるターンの終了時に全員が同時に原点（0,0）へ集まるようにしたい。

最短で何ターン後に全員が原点へ集まれるかを出力せよ。どうやっても全員が同時に原点に集まることができない場合は、-1を出力せよ。

入力例 1

2
6 0
3 3

出力例 1

3

入力例 2

2
2 1
-5 0

出力例 2

5

配点

満点

100

部分点1

20

部分点2

40

問題文

分数の真ん中の線分を括線(Vinculum)という。分数の計算時、短い括線から順に計算するという暗黙のルールがある。

N個の非0実数列\{a_N\}が与えられる。これを上から下に一列にならべ、間に1～N-1の相異なる長さの括線を引くことで、分数を表しかつその計算順序も表現できる。

たとえば次の図では1.0と2.0の間に長さ3の括線、2.0と3.0の間に長さ1の括線、3.0と4.0の間に長さ2の括線を引いた分数で、計算すると6.0になる。この括線の引き方は、数列[ 1.0, 2.0, 3.0, 4.0 ]に対する括線の引き方のなかで最大値を実現している。

図1

短い括線から順に計算していくとき、最終的にできる値を最大化するような括線の長さの列をひとつ求めよ。

入力例 1

4
1.0 2.0 3.0 4.0

出力例 1

3
1
2

問題文中の例である。

入力例 2

4
0.1 0.2 0.3 0.4

出力例 2

1
2
3

入力例 3

4
9.9 0.1 -9.9 -0.1

出力例 3

3
2
1

配点

満点

110

部分点

30

問題文

1変数関数が与えられる。与えられた関数を等価な50文字以下の表現で書きなおせ。

ただしこの問題で関数 f と g が等価であるとは、任意のx \in \{0,1,..,2147483647(=2^{31}-1)\} に対して f(x) = g(x)が成り立つことをいう。

入力形式

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

N
definition1
definition2
...
definitionN

N は定義する関数の個数である。

definition_iは全て以下のBNFに従う。

<definition> ::= <function-name> + "(x)=" + <expr>
<expr> ::= "x" | <number> | <function> + "(" + <expr> + ")"
                  | "(" + <expr> + "|" + <expr> + ")"
                  | "(" + <expr> + "^" + <expr> + ")"
                  | "(" + <expr> + "&" + <expr> + ")"
<function> ::= <function-name> | <function-name> + "^" + <number>
<function-name> ::= "a" | "b" | ... | "j"
<number> ::= "0" | "1" | ... | "2147483647"

<expr>で使われる"&"、"|"、"^"はそれぞれビット演算のand、or、xorを表す。

<function>で使われる"^"は関数の合成 f^n(x) を表す。

非負整数 n に対して f^n(x) は次のように定義される。

f^0(x) = x
f^{n+1}(x) = f(f^n(x))

関数の定義は上から行われる。定義式の右辺にその時点で未定義な他の関数や、定義しているその関数自身が現れることはない。また、既に定義された関数を新たに定義しなおすこともない。

定義される全ての関数は50文字以下の等価な表現を持つことが保証されている。

出力形式

関数を与えられた順に等価な表現で1行ごとに出力せよ。

各行毎に出力される文字列は50文字を越えてはならない。

出力は以下のBNFにしたがう必要がある。

<output> ::= <function-name> + "(x)=" + <expr>
<expr> ::= "x" | <number>
                  | "(" + <expr> + "|" + <expr> + ")"
                  | "(" + <expr> + "^" + <expr> + ")"
                  | "(" + <expr> + "&" + <expr> + ")"
<function-name> ::= "a" | "b" | ... | "j"
<number> ::= "0" | "1" | ... | "2147483647"

入力が従うBNFと異なり、ある関数の表現に他の関数を用いてはならないことに注意せよ。

制約

• 1 ≤ N ≤ 10
• |definition_i| ≤ 1000

この問題の判定には、30 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• N = 1

入力例 1

4
f(x)=(x^1)
g(x)=(f(x)&7)
h(x)=f(g^3((2147483647^x)))
c(x)=(3|10)

出力例 1

f(x)=(x^1)
g(x)=((x^1)&7)
h(x)=((x&7)^7)
c(x)=11

もちろんこれ以外にも様々な表現がある。例えば

f(x)=((x^3)^2)  c(x)=(((x^x)|1)^10)

f(x)=x^1  c(x)=(1|2|8)  c(x)=(11)

入力例 2

5
a(x)=(x^1)
b(x)=a^1000000000(x)
c(x)=a^1000000001(x)
d(x)=a^0((x|2))
e(x)=a^1((x|2))

出力例 2

a(x)=(x^1)
b(x)=x
c(x)=(x^1)
d(x)=(x|2)
e(x)=((x|2)^1)

配点

満点

120

部分点

30

問題文

A君とT君とJさんは地下世界を走る列車のそれぞれの運行区間表を見ていた。Jさんがいくつかの運行区間をピラミッド型に並べられることに気づき、A君とT君に並べ方が何通りあるか調べるよう命令した。

いまN個の運行区間が与えられる。ここからちょうどD要素からなる運行区間列[ A_1,A_2,...,A_D ]で、任意のi=1,...,D-1について(A_iの始点)<(A_{i+1}の始点)かつ(A_{i+1}の終点)< (A_iの終点)が常に成り立つようなものの個数を数える。相異なる運行区間列の個数を314159265で割った余りを求めよ。

入力例 1

3 2
1 7
2 4
8 10

出力例 1

1

図の通り、1番目の運行区間と2番目の運行区間からなる区間列のみが条件を満たす。

図1

入力例 2

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

出力例 2

5

5個からどの4個を選んでも並べ替えて条件を満たすようにできるので、C(5,4)=5通りとなる。

図2

入力例 3

4 2
1 10
2 5
3 4
8 11

出力例 3

3

入力例 4

4 3
1 7
2 8
3 6
4 5

出力例 4

2

配点

満点

120

部分点

40

問題文

N \times M の行列 \{X_{i,j}\}_{1 ≤ i ≤ N, 1 ≤ j ≤ M} があり、初期状態では 全ての要素が 0 となっている。

長さ Q の整数列 \{a_i\}, \{b_i\}, \{d_i\} が与えられる。 全てのk, i, j (1≤ k ≤ Q,\ 1 ≤ i ≤ N,\ 1 ≤ j ≤ M ) について X_{i,j} に max(\ 0,\ d_k - (|a_k - i| + |b_k - j|)\ ) を加える処理をした後の行列の各要素を求めよ。

入力形式

Qはとても大きいので入力の種を与えことにする。入力は以下の形式で与えられる。

N\ M\ Q\
a_1\ Amul\ Aadd\\
b_1\ Bmul\ Badd\\
d_1\ Dmul\ Dadd

1<k ≤ Q について a_k,\ b_k,\ d_k はそれぞれ次の式で生成される。

a_k = (a_{k-1} * Amul + Aadd) % N + 1
b_k = (b_{k-1} * Bmul + Badd) % M + 1
d_k = (d_{k-1} * Dmul + Dadd) % max(N,M) + 1

出力形式

行列をそのまま出力するのは大きくなるので、以下の擬似コードで計算されるハッシュ値を一行に出力せよ。

P := 10^9 + 7
mod := 10^9 + 9
hash := 0
for i in 1..N
  for j in 1..M
    hash :=  (hash * P + X_{i,j}) % mod

制約

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 1000
• 1 ≤ Q ≤ 10^6
• 1 ≤ a_1 ≤ N
• 1 ≤ b_1 ≤ M
• 1 ≤ d_1 ≤ max(N,M)
• 0 ≤ Amul,\ Bmul,\ Dmul,\ Aadd,\ Badd,\ Dadd ≤ 10^4
• 入力値はすべて整数である。

この問題の判定には、40 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• N = 1

入力例 1

3 4 2
3 2 1
1 2 0
4 0 2

出力例 1

999996819

この例では\{a_i\}=\{3,2\},\ \{b_i\}=\{1,3\},\ \{d_i\}=\{4,3\}となる。

k=1のとき、行列の各要素にそれぞれ次のような値を加える。

2 1 0 0
3 2 1 0
4 3 2 1

k=2のとき、行列の各要素にそれぞれ次のような値を加える。

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

以上のように値を加えた結果、行列Xは最終的に次のようになる。

2 2 2 1
4 4 4 2
4 4 4 2

入力例 2

1000 999 1000000
123 4567 8910
314 1592 6535
47 4747 4747

出力例 2

394300610

入力例 3

1 111 222
1 11 1111
33 44 55
66 77 88

出力例 3

79966854

配点

満点

140

部分点1

20

部分点2

40

問題文

いつも乗る通勤電車をいつもと逆の方向に乗ってみると、車内が空いていてとても気分が良い。この電車はどこまでいくのだろう・・・ふと窓の外に規則正しく並んでいる電柱群を見るとそこに忍者が立っているような気がした。

数直線の整数点上に電柱が並んでいる。はじめ車窓からは座標0を左端としてH本の電柱が連続して見えている。時刻0のときに忍者が座標0の電柱の上に立っている。時刻0から開始して、次の規則で状況が動く。

• 忍者が電柱に立っているときは、かならず車窓のうつす範囲内にいなければならない。
• 車窓から見える範囲は速度1で数直線の正の向きに進む。
• 忍者が整数時刻に電柱に立っているならば、時間[\sqrt{D}]だけかけて、数直線で正の向きにD個先の電柱にジャンプするか、その場で姿を消すかのいずれかを行う。ただし[x]は、x以下で最大の整数を表す。
• Dは正の整数である。
• ジャンプをはじめたら、着地するまでは滞空している。
• 姿を消したらそれ以降については2度と現れず、他の制約を満たす必要もなくなる。

時刻Tで忍者は消えていて滞空もしていなかった。忍者が条件を満たしながら移動する組合せの個数を1000003で割った余りを求めよ。なお忍者は時刻0およびTで消えることも可能とする。

入力例 1

1 2345

出力例 1

2346

忍者がジャンプするなら1本ごとしか行えないためどの時刻で離脱する組合せも1通りずつ、あわせて2345+1=2346通り。

入力例 2

3 1

出力例 2

4

0, 0->1, 0->2, 0->3 の4通り

入力例 3

3 2

出力例 3

11

入力例 4

20 70300

出力例 4

8512

配点

満点

150

部分点

100

問題文

9桁の整数文字列に対して、マスターマインド（hit and blow）をやる。

基本的なマスターマインドのルールは、次のようなものである。

1. 親が、答えとなる9桁の'0'-'9'からなる文字列を決める。この答えは、同じ数字が複数回現れていても良いし、先頭が0になっていてもよい。
2. 競技者は、答えと思われる9桁の文字列を回答する。
3. 親は、回答に対してhit数とblow数の2つの整数を返す。
   • hit数は、正解と回答を比べて同じ位置に同じ数字がある個数
   • blow数は、hitしている数字を取り除いた後で、min(正解に含まれている数字cの数, 回答に含まれている数字cの数) を '0'<=c<='9' で足しあわせたもの。言葉で言うと、"正解と回答に両方含まれているが位置が異なる数字の個数"
4. 競技者の回答と答えが一致したら終了する。一致しない場合は2.に戻る。

ただし、ここでのマスターマインドはちょっと変わっていて、次の条件がついている。

• 競技者は、答えを推測するため、9桁の'0'-'9'からなる文字列9個を同時に送信する（これを"test"と呼ぶ）。送った文字列それぞれに対するhit数とblow数のペア9つが、ランダムな順に並び替えられて返される
• 何回かtestを行って正解が推測できたら、回答として9桁の'0'-'9'からなる文字列を1つだけ送信する（これを"challenge"と呼ぶ）。送信した文字列が答えと一致すればAccepted、間違っていればWrong Answerになる。
• 1つのテストケースを通して、testで同じ文字列を複数回使うことはできない。複数のtestをまたいでいてもだめ
• testは20回以下しか行えない
• challengeは1回しか行えない

次の場合、ジャッジ結果はRuntime Errorになる。

• testを定められた回数を超えて呼び出した
• testで同じ文字列を複数回使用した
• 送信した文字列が定められたフォーマットに合致していなかった

全てのテストケースに正解すると、test回数が一番多かったテストケースについてその回数をTとし、10<=T<=20の場合は100点、T<10の場合は150点が与えられる。

入出力形式

testを行う場合は、標準出力へ文字"?"とスペースに続けて9桁の'0'-'9'からなる文字列9個をスペース区切りで出力し改行する。

例：

printf("? %s %s ... %s\n", t[0], t[1], ... t[8]);
fflush(stdout);

testの結果は、標準入力から18個の整数をスペース区切りで読み取る。

例：

int hit, blow;
for (int i = 0; i < 9; ++i) {
  scanf("%d %d", &hit, &blow);
  // hitやblowを使う
}

challengeを行うときは、標準出力へ文字"!"とスペースに続けて9桁の'0'-'9'からなる文字列を1個出力し改行する。

例：

printf("! %s\n", answer);
fflush(stdout);

入出力例

正解が「123456788」の場合、入出力の一例は次のようになる。