第4回ドワンゴからの挑戦状本選

A - アナログ時計

Time Limit: 2.525 sec / Memory Limit: 246 MB

配点 : 400 点

問題文

太郎君と次郎君はアナログ時計が好きです。太郎君と次郎君が持っているアナログ時計は普通のアナログ時計と同じように秒針が1分で1周し、分針が1時間で1周し、時針が12時間で1周します。また、秒針、分針、時針はなめらかに一定の角速度で動き、12時0分0秒ちょうどに全ての針が重なります。

太郎君は突然眠くなり、ちょうど H:M:S (H 時 M 分 S 秒) に眠りについてしまいました。その後、目が覚めたとき、次郎君から以下の情報を聞きました。

眠っている間にアナログ時計の分針と秒針が重なった回数が C_1 回だった
眠っている間にアナログ時計の時針と分針が重なった回数が C_2 回だった
太郎君が眠っていた時間はちょうど整数秒間だった
太郎君が眠りについた時刻・目が覚めた時刻に、アナログ時計の分針と秒針は重なっていない
太郎君が眠りについた時刻・目が覚めた時刻に、アナログ時計の時針と分針は重なっていない

これらの情報から、太郎君が眠っていた時間の最小秒数 t_1 と最大秒数 t_2 を出力してください。そのような範囲が存在しない場合は -1 を出力してください。

制約

入力は全て整数
1 \leq H \leq 12
0 \leq M, S \leq 59
1 \leq C_1 \leq 10,000
0 \leq C_2 \leq 10,000

入力

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

H M S
C_1 C_2

出力

答えを一行に出力せよ。

入力例1

12 0 1
1 0

出力例1

61 121

12:00:01 から最初に秒針と分針が重なるのは 12:01:01 と 12:01:02 の間の時刻です。その次に秒針と分針が重なるのは 12:02:02 と 12:02:03 の間の時刻です。したがって、秒針と分針が 1 回だけ交わる時刻は 12:01:02 から 12:02:02 の間なので、眠っていた時間の最小時間は 61 秒、最大時間は 121 秒です。

入力例2

12 0 1
1 2

出力例2

-1

この問題の制約の範囲では、 C_2 が C_1 を超えるような時刻は存在しません。

入力例3

11 59 59
1 1

出力例3

2 62

12時ちょうどに秒針と分針と時針の全てが重なります。目覚めた可能性がある時刻として、針がちょうど重なった時刻は含めません。

入力例4

12 34 56
10000 155

出力例4

610149 610209

B - だんだん強く

Time Limit: 5.252 sec / Memory Limit: 512 MB

配点 : 800 点

問題文

ニコニコのマスコットキャラクターであるニコニコテレビちゃんは、明日から N 日間に渡って生放送をすることになりました。 N 日間のうち、テレビちゃんは任意の日に生放送を休むことができます。

生放送をするときにテレビちゃんが出せる音量は日によって決まっていて、 i 日目には v_i の音量で放送します。

テレビちゃんの今年の目標は「だんだん強く」です。なので、テレビちゃんは直前に行ったものよりも大きな音量で放送するように、生放送をする日を選ぶことにしました。ただし、強くし続けるのは大変なので、最大 K 回までこのルールに反して生放送を行う日があってもいいことにしました。最初に行う生放送の音量はなんでも構いません。

このルールのもとで、テレビちゃんは最大何回生放送できるでしょうか？

制約

1 \leq N \leq 10^5
0 \leq K \leq 100
0 \leq v_i \leq 10^9

入力

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

N K
v_1 ... v_N

出力

答えを一行に出力せよ。

入力例 1

8 2
4 1 6 2 8 5 7 3

出力例 1

たとえば 1, 2, 4, 6, 7, 8 日目に生放送を行うことができます。このとき強さは 4, 1, 2, 5, 7, 3 となって、2 日目と 8 日目の 2 回を除いて直前の日より強くなっています。

入力例 2

3 0
1 1 1

出力例 2

直前の日と同じ強さで放送することもたかだか K 回しかできないことに注意してください。

入力例 3

5 2
5 1 3 2 4

出力例 3

C - XOR ピラミッド

Time Limit: 5.252 sec / Memory Limit: 512 MB

配点 : 1300 点

問題文

dwango社員のニワンゴくんは N 段のピラミッドを作る仕事をしています。各 1 \leq i \leq N について、上から i 段目は 2i - 1 個のブロックが横一列に並んでいます。また、各段の中央のブロックに着目したとき、これらは縦一列に並んでいます。例えば 4 段のピラミッドの場合、以下の図のようになります。

ニワンゴくんは長さ 2N-1 の数列 a を用いて、ピラミッドの各ブロックに整数を書き込むことにしました。ニワンゴくんは各 1 \leq i \leq 2N-1 について N 段目の左から i 番目のブロックに整数 a_i を書き込んだのち、以下の条件を満たすようにその他のブロックに値を書き込みました。

各ブロックに書き込まれる整数は左下、真下、右下のブロックに書き込まれた整数をそれぞれ x, y, z として x xor y xor z となる
ただし、xor はビットごとの排他的論理和を表す

1 段目のブロックに書き込まれた整数を求めてください。

ただし、N は非常に大きくなりうるため a のみが以下の形式で与えられます。詳しくはサンプル 1 も参照してください。

整数 M と長さ M の数列 v,L が与えられる
これは、a が v_1 を L_{1} 回繰り返した数列、v_2 を L_{2} 回繰り返した数列、...、v_M を L_{M} 回繰り返した数列をこの順で連結して得られる数列であることを表す

制約

1 \leq M \leq 252{,}525
0 \leq v_i \leq 10^9
1 \leq L_i \leq 10^9
{\rm Σ}{L_i} は 3 以上の奇数
与えられる入力は全て整数

入力

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

M
v_1 L_1
:
v_{M} L_{M}

出力

答えを出力せよ。

入力例 1

出力例 1

a は (1), (2,2,2), (3,3), (4) をこの順番で連結した数列である、(1,2,2,2,3,3,4) となります。
このとき、以下の図のようなピラミッドが得られ、1 段目のブロックには 6 が書き込まれます。

入力例 2

1
1 999999999

出力例 2

N=499999999 で、a は 1 が 999999999 個繰り返されるような数列です。1 段目のブロックには 1 が書き込まれます。

入力例 3

21
89 54
6724143 9
122809 50
217 28
11179392 38
756 6
127 53
7490953 33
7235 47
877957251 1
708258674 49
539545 3
20170110 6
6991539 40
4 14
3 21
204 35
9 3
680 41
158030498 44
34248 10

出力例 3

590313667

D - ニワンゴくんとゲーム

Time Limit: 2.525 sec / Memory Limit: 246 MB

配点 : 1400 点

問題文

dwango社員のニワンゴくんは、あるゲームで遊んでいます。このゲームでは、Q 体の敵が現れるので、プレイヤーをうまく操作して敵を倒す必要があります。また、敵にはそれぞれ体力と呼ばれる値が定まっており、i 番目の敵の体力は N_i です。

ニワンゴくんの操作するプレイヤーには、魔力とよばれる値が定まっています。敵と遭遇したとき、プレイヤーの魔力は 1 です。この魔力は、敵と遭遇するたびに 1 に戻ることに注意してください。ニワンゴくんは、毎ターン、次の操作のうちいずれかを行うことができます。

操作 1: 魔力を 1 増加させる。
操作 2: 現在の魔力を x として、魔力を 2x に変更する。
操作 3: 現在の魔力を x として、魔力を 2x + 1 に変更する。

プレイヤーの魔力がちょうど敵の体力に等しくなったとき、特殊な魔法が発動し、敵を倒すことができます。ただし、魔力が敵の体力を超えてしまうと、もう敵を倒すことはできません。そのため、魔力が敵の体力を超えてしまうような操作を行ってはいけません。プレイヤーの操作によって敵の体力が変化することはありません。

ニワンゴくんは、敵を倒すまでの操作の方法は何通りあるかが気になっています。それぞれの敵に対して、ニワンゴくんが敵を倒すまでの操作の方法は何通りあるかを {\rm mod} 1,000,000,007 で求めてください。ここで、途中で行う操作の番号が一回でも異なれば、途中の魔力の経過がまったく同じでも、異なる操作の方法として数えることに注意してください。

制約

1 \leq Q \leq 200
1 \leq N_i \leq 10^{18} (1 \leq i \leq Q)
N_i は整数

部分点

Q = 1, 1 \leq N_1 \leq 10^{14} を満たすデータセットに正答すると、1300 点が与えられる。

入力

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

Q
N_1
N_2
:
N_Q

出力

答えを Q 行で出力せよ。i 行目には、i 番目の敵を倒すまでの操作の方法は何通りあるかを {\rm mod} 1,000,000,007 で出力せよ。

入力例 1

1
4

出力例 1

1 番目の敵の体力は 4 です。魔力をちょうど 4 にするまでの操作の方法としては、次の 5 通りがあります。

操作 1, 操作 1, 操作 1 の順に操作を行う。
操作 1, 操作 2 の順に操作を行う。
操作 2, 操作 1, 操作 1 の順に操作を行う。
操作 2, 操作 2 の順に操作を行う。
操作 3, 操作 1 の順に操作を行う。

ここで、最初に操作 1 を行っても、操作 2 を行っても、魔力の変化の仕方は変わりませんが、この 2 つの操作は区別することに注意してください。

入力例 2

2
2
1

出力例 2

2
1

1 番目の敵については、この敵を倒すまでの操作の方法は 2 通りあります。

2 番目の敵については、一切操作を行わなくても最初からプレイヤーの魔力が敵の体力と等しくなっています。ここで、プレイヤーの魔力は 2 番目の敵と遭遇した際に 1 に戻ることに注意してください。

入力例 3

出力例 3

415443858
630306535
766913460

{\rm mod} 1,000,000,007 で出力するのを忘れないようにしてください。

入力例 4

10
983102606006243867
653718290103598600
364611268624595444
114746989192634390
81304291426411017
931878752092058491
395809284336497545
633900034071891379
895817108011279740
92661392530626177

出力例 4