問題文

はにーま君はプログラミング合宿を開催することにしました。参加者は N 人いて、 N は 3 の倍数です。

競技プログラマの間では「アジ本」と呼ばれる参考書が広く普及しています。事前のアンケートにより、今回の合宿にアジ本を持参した人は A 人いることがわかっています。

合宿では 3 人ずつのチームを \dfrac{N}{3} 個作ってチーム戦を行います。 このとき、 3 人のうち少なくとも 1 人がアジ本を持っているようなチームの個数として、ありえる最小の個数と最大の個数を答えてください。

制約

• 3\le N\le 99
• 0\le A\le N
• N は 3 の倍数
• A は整数

入力例 1

6 2

出力例 1

1 2

アジ本を持っている 2 人が同じチームになった場合アジ本を持っているチームの数は 1 つです。

2 人が別のチームになった場合はアジ本を持っているチームの数は 2 つになります。

入力例 2

9 6

出力例 2

2 3

入力例 3

81 0

出力例 3

0 0

問題文

英小文字からなる文字列 S が「美しい」とは、 S に 1 つ以上含まれるアルファベットについて、その出現回数がすべて等しいことを言います。例えば、abba や ddddd，xyz は美しいですが、aab や xyxyxyz は美しくありません。

文字列 S が与えられるので、S が美しいかどうかを判定してください。

制約

• S の長さは 1 以上 10^5 以下
• S は英小文字のみからなる

入力例 1

ababcc

出力例 1

Yes

a，b，c が 2 回ずつですべて出現回数が等しいので美しいです。

入力例 2

reiwa

出力例 2

Yes

入力例 3

cpsco

出力例 3

No

問題文

ある国では 1,\ 10,\ 100,\ldots ,10^{9} 円硬貨および 5,\ 50,\ 500,\ldots ,5\times 10^{9} 円硬貨の 20 種類の硬貨が流通しています。

てんぷら君は果物を買いにスーパーマーケットに行きました。そこには N 種類の果物が 1 つずつ売られており、値段はそれぞれ A_1, A_2,\ldots, A_N 円です。

てんぷら君はこの中から K 個を選んで買うことにしました。合計金額をちょうど支払うために必要な硬貨の枚数として考えられる最小の枚数を求めてください。なお、てんぷら君はすべての硬貨を十分たくさん持っているものとします。

制約

• 1\le N\le 32
• 1\le K\le min(N, 6)
• 1\le A_i\le 10^8
• 入力はすべて整数

入力例 1

3 2
25 29 62

出力例 1

5

1 つめの商品と 2 つめの商品を購入すると合計金額は 54 円で、50 円硬貨 1 枚と 1 円硬貨 4 枚の合計 5 枚で支払うことができます。この場合が最小です。

入力例 2

3 1
10000 2 3

出力例 2

1

入力例 3

10 3
1415 9265 3589 7932 3846 2643 3832 7950 2884 1971

出力例 3

5

問題文

やむなく君はお菓子を食べることが大好きです。今日を 1 日目として、今日から N 日間、お菓子をどのように食べるかを考えることにしました。そこで、以下のルールを設定しました。

• お菓子は毎日朝、昼、晩の 3 回食べる。
• それぞれで食べるお菓子は「クッキー」「チョコレート」「ケーキ」のいずれか 1 つにする。
• 同じお菓子を 2 回連続で食べない。( i 日目の晩と (i+1) 日目の朝についても適用される。)
• 朝に食べるお菓子は「クッキー」「チョコレート」のどちらかにする。

N 日間、合計 3N 回のお菓子について、上のルールをすべて満たすような食べ方の組み合わせが何通りあるかを 10^9+7 で割った余りを計算してください。

なお、1 日目の朝は「クッキー」「チョコレート」のどちらを食べてもよく、やむなく君は 3 種類のお菓子すべてを十分たくさん持っているものとします。

制約

• 1\le N\le 10^{18}
• N は整数

部分点

この問題には部分点が設定されています。

• N \leq 10^5 を満たす入力に正解すると、300 点が与えられます。

入力例 1

1

出力例 1

8

クッキーを「ク」、ケーキを「ケ」、チョコレートを「チ」と表すと、

(朝、昼、晩) = (ク、ケ、ク), (ク、ケ、チ), (ク、チ、ク), (ク、チ、ケ), (チ、ケ、ク), (チ、ケ、チ), (チ、ク、ケ), (チ、ク、チ)

の 8 通りです。同じお菓子が連続してはいけないこと、朝にはケーキを食べないことに注意してください。

入力例 2

2

出力例 2

40

入力例 3

100000

出力例 3

607318103

問題文

長さ N の整数列 A_1, A_2, \ldots, A_N があります。以下の Q 個のクエリを順番に処理してください。

• 値が L_i 以上 R_i 以下である要素をすべて選び、それらの排他的論理和を答える。その後、選んだ要素をすべて X_i に更新する。 ただし、L_i 以上 R_i 以下の整数が 1 つも存在しない場合の答えは 0 とする。

制約

• 1\le N\le 3\times 10^5
• 1\le Q\le 2\times 10^5
• 0\le A_i\le 10^9
• 0\le L_i\le R_i\le 10^9
• 0\le X_i\le 10^9
• 入力はすべて整数

入力例 1

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

出力例 1

14
1

• 1 つめのクエリでは、7 以上 10 以下の整数は 7 と 9 の 2 つなのでこれらの排他的論理和の 14 を出力します。 その後この 2 つを 2 に更新して、数列は \{2,4,1,5,2\} になります。
• 2 つめのクエリでは、2 以上 8 以下の整数は 2, 4, 5, 2 の 4 つなのでこれらの排他的論理和の1 を出力します。 その後この 4 つを 5 に更新して、数列は \{5,5,1,5,5\} になります。

入力例 2

1 1
5
1 3 2

出力例 2

0

入力例 3

15 10
76 87 42 60 30 58 52 82 42 13 81 8 97 5 87
4 11 92
56 60 68
90 100 24
30 35 15
12 17 53
24 32 31
0 6 85
74 82 55
69 72 30
50 61 49

出力例 3

13
6
97
30
2
24
0
79
0
3

問題文

てんぷら君は果物を N 個持っています。今日から N 日間ですべての果物を食べきることにしました。

彼は毎日、その時点で残っている果物から 1 つを選んで食べます。1 度食べた果物はその日のうちに完食します。

果物 i には旬 t_i が定められていて、旬とその果物を食べた日付によって美味しさが変化します。

果物 i を t_i 日目に食べた場合の美味しさは A_i であり、t_i 日目から 1 日ずれるごとに食べたときの美味しさが B_i ずつ低くなります。 より正確には、果物 i (1\le i\le N) を j 日目 (1\le j\le N) に食べたときの美味しさは A_i -|j-t_i|\times B_i と表すことができます。

彼の得られる満足度は N 日間で食べた果物の美味しさの最小値です。

てんぷら君が食べる順番を適切に決めたときの、得られる満足度の最大値を求めてください。

制約

• 1\le N\le 2\times 10^4
• 1\le t_i\le N
• 0\le A_i\le 10^9
• 1\le B_i\le 5\times 10^4
• 入力はすべて整数

入力例 1

3
1 7 1
1 6 3
2 5 2

出力例 1

5

1 日目に果物 2 を食べると美味しさは 6-|1-1|\times 3 = 6 です。

2 日目に果物 3 を食べると美味しさは 5-|2-2|\times 2 = 5 です。

3 日目に果物 1 を食べると美味しさは 7-|3-1|\times 1 = 5 です。

このとき満足度は 5 で、これが最大です。

入力例 2

2
2 0 1
2 0 1

出力例 2

-1

入力例 3

10
3 78 4
1 97 8
4 93 7
1 72 5
5 81 6
9 70 9
2 72 3
6 84 5
5 83 9
3 79 2

出力例 3

65

問題文

やむなく君は 1 枚の紙と長さ N の整数列 A_1, A_2, \ldots, A_N を使った次のようなゲームを考えました。

まず紙に好きな正の整数を 1 つ書きます。その後 N 回の操作をします。 i 回目 (1\le i\le N) の操作では以下のどちらか 1 つを行います。

• その時点で紙に書かれている数字を X として、Y = \left \lfloor\frac{A_i}{X}\right \rfloor とする (\lfloor x \rfloor で x の整数部分を表します)。紙に書かれている数字を Y に書き換えて、Y 点を獲得する。 なおこの操作は X > A_i のときには行うことができない。
• 何もしない。得点も獲得できない。

やむなく君は N 回の操作で獲得する点数の合計を最大化したいです。

やむなく君が最初に紙に書く数字と N 回の操作を最適に行ったときに獲得できる点数を求めてください。

制約

• 1\le N\le 1000
• 1\le A_i\le 10^6
• 入力はすべて整数

部分点

この問題には部分点が設定されています。

• すべての i\ (1\le i\le N) について A_i\le 1000 を満たす入力に正解すると、300 点が与えられます。

入力例 1

3
3 6 9

出力例 1

10

• まず紙に 2 と書く。
• 1 回目の操作では紙の数字を \left \lfloor\frac{3}{2}\right \rfloor = 1 に書き換えて 1 点を獲得する。
• 2 回目の操作では何もしない。
• 3 回目の操作では紙の数字を \left \lfloor\frac{9}{1}\right \rfloor = 9 に書き換えて 9 点を獲得する。

このとき合計 10 点を獲得できて、これが最大です。なお、10 点を獲得する方法は他にもあります。

入力例 2

3
10 3 4

出力例 2

10

入力例 3

1
1000

出力例 3

1000

入力例 4

10
87 72 55 81 12 59 1 10 18 53

出力例 4

166

問題文

長さ N の整数列 A_1, A_2, \ldots, A_N と整数 X が与えられます。 以下の条件をすべて満たす整数 (l,\ m,\ r) の組の個数を数えてください。

• 1\le l \le m\le r\le N
• A_l + A_m + A_r = X
• A_m は l\le i\le r における A_i の最大値である。

制約

• 1\le N\le 10^5
• 0\le X\le 3\times 10^5
• 0\le A_i\le 10^5
• 入力はすべて整数

部分点

この問題には部分点が設定されています。

• N\le 2000 を満たす入力に正解すると、300 点が与えられます。

入力例 1

6 9
1 2 4 4 3 2

出力例 1

6

(l,\ m,\ r)=(1,3,3), (1,3,4), (1,4,4), (2,3,5), (2,4,5), (5,5,5) の 6 つです。

入力例 2

3 0
0 0 0

出力例 2

10

入力例 3

10 15
3 1 4 1 5 9 2 6 5 3

出力例 3

7