問題文

今年のパ研合宿には、外部から 4 人の講師が参加しています。

運営長であるペンギンくんは、パ研合宿のスケジュールを管理するにあたり、合宿の日程すべてに参加する講師の数を把握したいです。

今年のパ研合宿は 4 日間からなり、i 人目の講師は文字列 S_i の j 文字目が 1 なら合宿の j 日目に参加し、0 なら合宿の j 日目には欠席します。遅刻や早退は考慮しません。

ペンギンくんの代わりに、合宿の日程すべてに参加する講師の数を数えてあげてください。

制約

• S_i\ (1 \leq i \leq 4) は 0 と 1 のみからなる長さ 4 の文字列

小課題

この問題には小課題は存在しない。

入力例 1

1111
0101
0000
1111

出力例 1

2

1 人目の講師と 4 人目の講師の 2 人が、合宿の日程すべてに参加します。

入力例 2

1111
1111
1111
1111

出力例 2

4

すべての講師が合宿の日程すべてに参加します。

入力例 3

0010
1000
0110
0010

出力例 3

0

合宿の日程すべてに参加する講師は 1 人もいません。

原案: penguinman

問題文

N 人のパ研部員が、円環上に配置されています。そしてまた彼らには、時計回りに 1 から N までの番号が振られています。

各パ研部員にはレートと呼ばれる値が定まっており、部員 i のレートは A_i です。

パ研部長であるペンギンくんは、N 人のパ研部員を円環上で連続した 2 つのグループに分け、片方のグループに含まれるパ研部員のレートの総和を X に、もう片方のグループに含まれるパ研部員のレートの総和を Y にしたいと考えています。

これが可能かを判定してください。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq X,Y \leq 10^{15}
• 1 \leq A_i \leq 10^9
• 入力は全て整数

小課題

1. (100 点) N \leq 3000
2. (200 点) 追加の制約はない

入力例 1

5 6 11
3 4 2 3 5

出力例 1

Yes

部員 2 と部員 3 を 1 つのグループに、残りの部員をもう片方のグループに分類すると、それぞれのグループに含まれる部員のレートの総和は順に X=6、Y=11 となります。

この入力はすべての小課題の制約を満たします。

入力例 2

4 4 8
1 2 3 4

出力例 2

No

N 人のパ研部員を問題文中にある通りに 2 つのグループに分けることは不可能です。

この入力はすべての小課題の制約を満たします。

入力例 3

10 191 376
72 6 62 98 90 61 36 82 9 51

出力例 3

Yes

この入力はすべての小課題の制約を満たします。

原案: penguinman

ストーリー

Paken 王国では、ある正整数に対してその ID が下 M 桁の桁和で定義されます。ところで、 Paken 王国の住人である turtle5555 君は 5 冪が好きです。そこで、いくつかの連続する 5 冪についての ID の和を求めることにしました。

問題文

正整数 n,k に対して f_k(n) を、 n の 10 進法での下 k 桁の桁和で定義します。例えば、 f_2(314)=5,f_1(100)=0,f_{100}(1)=1 です。

正整数 L,R,M が与えられるので、 \displaystyle \sum_{k=L}^R f_M(5^k) を求めてください。

制約

• 1 \le L \le R \le 10^{16}
• 1 \le M \le 16
• 入力は全て整数

小課題

1. (100 点) 1 \le L \le R \le 10^6
2. (150 点) M=3
3. (250 点) 追加の制約はない。

入力例 1

2 4
3

出力例 1

28

f_3(25)=7, f_3(125)=8, f_3(625)=13 より 28 です。

この入出力はすべての小課題の制約を満たします。

入力例 2

333 4444
5

出力例 2

77100

この入出力は小課題 1,3 の制約を満たします。

入力例 3

12 998244353
5

出力例 3

18717081408

この入力は小課題 3 の制約を満たします。

入力例 4

12321 123456787654321
16

出力例 4

8395076630065056

この入力は小課題 3 の制約を満たします。

原案: turtle0123__

問題文

20XX年、高校教師となったペンギンくんは期末試験の作成に勤しんでいます。

N 個の問題があり、この中から 1 問以上を選んで期末試験を作成します。試験時間は T 分と決まっていますが、選ぶ問題の数は自由です。

期末試験はペンギンくんの教え子たちによって解かれますが、その中には太郎くんと次郎くんの 2 人がいます。各 i\ (1 \leq i \leq N) について、太郎くんが i 問目の問題を解くのにかかる時間は A_i 分、次郎くんがかかる時間は B_i 分であることが分かっています。

太郎くんを贔屓したいペンギンくんは、なるべく太郎くんに有利になるような試験を作ろうとしています。使用する問題をうまく選ぶことで、（太郎くんが解いた問題数）-（次郎くんが解いた問題数）を最大化してください。

ただし、太郎くん、次郎くんの 2 人は各々が試験中に解く問題の数を最大化するように問題を解くこととします。

制約

• 1 \leq N \leq 1000
• 1 \leq T \leq 10000
• 1 \leq A_i,B_i \leq T
• 入力はすべて整数

小課題

1. (50 点) N \leq 16
2. (150 点) すべての (i,j) について A_i \lt A_j ならば B_i \leq B_j、T \leq 100
3. (150 点) すべての (i,j) について A_i \lt A_j ならば B_i \leq B_j
4. (250 点) 追加の制約はない

入力例 1

4 8
3 4
5 3
3 4
4 5

出力例 1

1

1 問目と 4 問目を選んで試験を作ったとき、太郎くんは 2 問、次郎くんは 1 問を解きます。

これより（太郎くんが解いた問題数）-（次郎くんが解いた問題数）の値が大きくなる問題の選び方は存在しないので、答えは 1 となります。

この入力は小課題 1,4 の制約を満たします。

入力例 2

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

出力例 2

2

この入力はすべての小課題の制約を満たします。

入力例 3

10 100
95 5
85 70
8 44
71 66
74 11
39 2
26 81
29 23
92 70
52 57

出力例 3

2

この入力は小課題 1,4 の制約を満たします。

原案: penguinman

問題文

Paken 王国には N 校の学校があり、 1, 2, \ldots, N の番号が付けられています。学校 i には最初、 A_i 人の生徒が所属しています。もちろん学校である以上、同じ人が永遠に学校に所属し続けることはできません。生徒の人数は途中で変わることがあります。

Paken 王国では毎日のように王国主催の大会が開催されており、それぞれの大会では、招待する学校の候補を表す整数組 (l, r) を定め、学校 l, l+1, \ldots, r のうちから 1 校のみを選び、その学校の生徒を全員招待することになっています。

さて、大会では頭を使うため、糖分補給用に参加者にお菓子が配られます。しかし、このお菓子の個数には次のような条件があります。

• 人によってお菓子の個数が変わらないように、学校 l, l+1, \ldots, r のどの学校に対しても、その学校の生徒の人数が用意するお菓子の個数の約数になるようにする。
• Paken 王国にはあまりお金がないため、用意するお菓子の個数は、上の条件を満たす中で最小になるようにする。

あなたは Paken 王国で唯一のお菓子の会社の社長です。すべての大会のお菓子はあなたの会社に発注されます。あなたは会社の PR のため、どの学校が大会に招待される候補になっているのかを知りたくなりました。 そこで、それぞれの大会について、発注されたお菓子の個数から、その大会で定められた整数組 (l, r) としてあり得るものの個数を求めることにしました。

Paken 王国で起こる出来事は Q 個あり、それぞれの出来事は次のいずれかの形のクエリで表されます。

• 入学クエリ 1 k a : 学校 k に人が a 人入学する。学校 k に所属する生徒は a 人増える。
• 卒業クエリ 2 k b : 学校 k から人が b 人卒業する。学校 k に所属する生徒は b 人減る。
• 大会クエリ 3 s : ある大会でお菓子が s 個発注される。あなたは、その大会に招待される学校の候補を表す整数組 (l, r) として考えられるものの個数を求める。

Q 個の出来事が順に起きたとき、それぞれの大会クエリに対する答えを求めて下さい。

なお、学校はあくまで学校であるので、どの学校も、その学校に所属する生徒の数は常に 1 以上 10^9 以下となることが保証されています。

制約

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq A_j \leq 10^9 (1 \leq j \leq N)
• 入学クエリと卒業クエリについて、 1 \leq k \leq N
• 入学クエリについて、 1 \leq a \leq 10^9
• 卒業クエリについて、 1 \leq b \leq 10^9
• 大会クエリについて、 1 \leq s \leq 10^9
• どの時点においても、全ての学校について、その学校に所属する生徒の人数は 1 以上 10^9 以下である
• 入力は全て整数

小課題

1. (150 点) N, Q \leq 10^3
2. (200 点) 入学クエリと卒業クエリは与えられない
3. (200 点) どの時点においても、全ての学校について、その学校に所属する生徒は 10 人以下である
4. (150 点) 追加の制約はない

入力例 1

4 3
1 2 3 4
3 12
1 1 3
3 12

出力例 1

3
4

それぞれのクエリの結果は次のようになります。

1. 大会クエリ。 (l, r) = (1, 4), (2, 4), (3, 4) が条件を満たす。
2. 入学クエリ。学校 1 に生徒が 3 人入学し、それぞれの学校の生徒の人数は 4, 2, 3, 4 になる。
3. 大会クエリ。 (l, r) = (1, 3), (1, 4), (2, 4), (3, 4) が条件を満たす。

この入力例は小課題 1, 3, 4 の制約を満たします。

入力例 2

10 5
10 1 8 3 10 10 6 3 3 7
3 30
3 7
3 4
3 10
3 1

出力例 2

11
1
0
5
1

この入力例はすべての小課題の制約を満たします。

入力例 3

20 20
13 5 30 10 15 22 30 4 11 18 10 23 9 1 27 8 5 6 16 26
3 60
3 90
2 19 11
2 7 6
2 5 6
3 12870
3 198
1 12 3
2 10 1
3 30
3 5
2 18 5
3 234
3 291720
1 10 6
3 1776060
3 198
3 10
3 792
3 30

出力例 3

1
1
1
2
7
3
2
2
1
1
2
3
4

この入力例は小課題 1, 4 の制約を満たします。

原案: shiomusubi496

問題文

define 君は 4 月にオープンする遊園地「パ研ランド」の設計をしています。この遊園地は東西に細長いことが特徴で、その入口は遊園地の最も西にあります。以下、入口から東に k m 進んだ場所を地点 k と呼ぶことにします。

この遊園地にはアトラクションが N 基 あり、 1, 2, \dots, N の番号が振られています。アトラクション i は地点 i にあります。

define 君はパ研ランドのオープン日にぺんぎん君を招待しています。ぺんぎん君は 1m 進むのに 1 秒掛かります。ぺんぎん君は M 回に渡ってアトラクションに乗る計画を立てており、i 番目に乗るのはアトラクション A_i と決めています。 この計画では、地点 A_i から地点 A_{i+1} への移動に掛かる最短時間を T_i 秒として、移動に \sum_{i=1}^{M-1}{T_i} 秒掛かります。

さて、オープン直前になって define 君は「アトラクションが一列に並んでいると移動しにくいのでは？」と思い始めました。このままでは、ぺんぎん君が途中で移動が嫌になって帰ってしまうかもしれません。 そこで、時間もないので 1 本だけワープ路を造る事にしました。地点を 2 つ選んでワープ路を造ると、その 2 地点間を双方向に 1 秒で移動する事ができます。

Q 個のクエリが与えられます。i 番目のクエリは「地点 S_i と地点 T_i を結ぶワープ路を造った時にぺんぎん君の計画に掛かる移動時間は何秒か」というものです。それぞれのクエリに答えてください。

制約

• 2 \leq N, M \leq 300000
• 1 \leq Q \leq 300000
• 1 \leq A_i \leq N (1 \leq i \leq M)
• A_i \neq A_{i+1} (1 \leq i \leq M-1)
• 1 \leq S_i < T_i \leq N (1 \leq i \leq Q)

小課題

1. (20 点) M, Q \leq 5000
2. (50 点) N \leq 300, |A_i - A_{i+1}| \leq 10 (1 \leq i \leq M-1)
3. (100 点) N \leq 300
4. (280 点) N \leq 2000
5. (300 点) M, Q \leq 50000
6. (50 点) 追加の制約はない。

入力例 1

5 6
3 5 2 1 5 3
2
1 3
2 5

出力例 1

11
8

クエリ 2 では、ぺんぎん君は例えば以下のように移動します。

1. 地点 3 から地点 2 に移動する (1 秒)
2. ワープを使って地点 2 から地点 5 に移動する (1 秒)
3. ワープを使って地点 5 から地点 2 に移動する (1 秒)
4. 地点 2 から地点 1 に移動する (1 秒)
5. 地点 1 から地点 2 に移動する (1 秒)
6. ワープを使って地点 2 から地点 5 に移動する (1 秒)
7. 地点 5 から地点 3 に移動する (2 秒)

ぺんぎん君は必ず最短時間で移動する事に注意してください。この入力例は全ての小課題の制約を満たします。

入力例 2

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

出力例 2

24
27
21
27
31
23
29
25
28
27

この入力例は全ての小課題の制約を満たします。

入力例 3

100 20
6 97 94 50 96 51 94 86 92 77 9 73 21 9 46 42 76 77 49 17 
20
38 87
20 60
5 56
8 82
69 80
13 42
90 99
97 98
96 97
95 97
61 88
48 61
11 73
42 81
8 18
78 83
17 54
41 68
2 69
72 100

出力例 3

401
451
449
417
573
489
625
633
633
631
493
535
401
393
596
609
451
467
437
543

この入力例は小課題 1,3,4,5,6 の制約を満たします。

原案: define

問題文

パ研王国は 1 から N までの番号が付けられた N 個の都市と、1 から M までの番号が付けられた M 本の道路からなります。各 i\ (1 \leq i \leq M) について、辺 i は都市 u_i と都市 v_i を双方向に結んでいます。

ペンギンくんは今、パ研王国の中を旅行する計画を立てています。彼はその計画を立てるにあたって、以下の情報を知りたがっています。

• 1 \leq l \leq r \leq M を満たす整数対 (l,r) であって、以下の条件を満たすものはいくつあるか。
  • ある都市 X を出発し、道路 l、道路 l+1、\cdots、道路 r を好きな順番でちょうど一度ずつ通って都市 X に戻るような経路が存在する。

この値を求めることは、ペンギンくんには難しすぎました。そのため、彼の代わりに答えを求めてあげてください。

（16:30 補足：）

• 経路において道路 l、道路 l+1、\cdots、道路 r 以外の道路を通ることはできません。
• 経路の途中で都市 X を経由することは可能です。

制約

• 1 \leq N,M \leq 5 \times 10^4
• 1 \leq u_i,v_i \leq N
• u_i \neq v_i
• 入力は全て整数

小課題

1. (200 点) N,M \leq 3000
2. (150 点) v_i = u_{i+1}\ (1 \leq i \leq M-1)
3. (350 点) M は偶数、(u_{2i-1},v_{2i-1}) = (u_{2i},v_{2i})\ (1 \leq i \leq \frac{M}{2})、\{u_i,v_i\} \neq \{u_j,v_j\}\ (|i-j| \geq 2)
4. (100 点) 追加の制約はない

入力例 1

4 4
1 2
2 3
3 4
2 4

出力例 1

1

問題文中の条件を満たす (l,r) は、(2,4) の 1 つのみです。

(l,r)=(2,4) においては、例えば都市 2 を出発したあと道路 4、道路 3、道路 2 をこの順に通って都市 2 に戻ってくるような経路が存在します。

この入力は小課題 1,4 の制約を満たします。

入力例 2

5 8
2 3
3 1
2 3
3 2
2 5
3 2
1 5
2 1

出力例 2

3

この入力は小課題 1,4 の制約を満たします。

入力例 3

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

出力例 3

6

この入力は小課題 1,2,4 の制約を満たします。

入力例 4

8 12
7 1
7 1
3 7
3 7
6 3
6 3
5 7
5 7
6 8
6 8
5 8
5 8

出力例 4

18

この入力は小課題 1,3,4 の制約を満たします。

原案: penguinman

問題文

パ研王国は 1 から N までの番号が振られた N 個の都市と、それらの都市間を結ぶ M 本の道路からなります。i 本目の道路は、都市 u_i と都市 v_i を双方向に結んでおり、その長さは l_i メートルです。

あなたの属するペンギン株式会社は、パ研王国内において貨物の輸送を行うという仕事を K 個受注しました。i 番目の仕事（仕事 i とする）では、都市 s_i にある貨物を都市 g_i に移動させる必要があり、仕事に成功した場合 m_i 円の利益が生まれます。
ただしこの K 個の仕事には時間制限があり、ある時刻 T までに仕事を行うことができなかった場合得られる利益は 0 円になります。

あなたは、ペンギン株式会社の利益のため、以下のような輸送計画を立てることにしました。

1. まずはじめに、行う仕事の集合を決める。
2. その後、行う仕事それぞれについて（仕事 x とする）、経由する都市の列 (a_0=s_x, a_1, \ldots, a_k=g_x)、および仕事を開始する時刻 t を決める。t は整数である必要があり、また、このとき 1 \leq i \leq k について都市 a_{i-1} と都市 a_i は直接道路で結ばれている必要がある。
3. 時刻 0 以降、2. までで決めた内容をもとに実際に仕事を行う。行う仕事それぞれについて、時刻 t に輸送する貨物を会社の車に乗せた状態から仕事を開始する。その後はその仕事が完了するまでの間、分速 1 メートルの速さで今いる地点から次に経由する都市に向けて移動し続ける。途中で車が止まることはない。

パ研王国の道路は非常に狭いため、同じ時刻に同じ道路内の同じ地点（道路の両端を除く）に複数の車が存在することは許されません。

得られる利益の合計をできるだけ大きくしてください。

入力例1

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

出力例1

2
2 0 1
3 1 
3 7 1
2 4

これは説明用の入力例であり、制約を満たしていないことに注意してください。 この例では、得られる利益は 11 円となります。

原案: define