問題文

A 冊セットのノート B 組に加えて，単品のノートが C 冊ある．

ノートが合計で何冊あるかを求めよ．

制約

• 1\leqq A \leqq 100．
• 1\leqq B \leqq 100．
• 1\leqq C \leqq 100．
• 入力される値はすべて整数である．

入力例 1

2 7 1

出力例 1

15

セットのノートが 2 \times 7 = 14 冊あり，単品のノートは 1 冊あるため，合計で 14 + 1 = 15 冊ある．したがって 15 を出力する．

入力例 2

8 2 8

出力例 2

24

セットのノートが 8 \times 2 = 16 冊あり，単品のノートは 8 冊あるため，合計で 16 + 8 = 24 冊ある．したがって 24 を出力する．

入力例 3

3 1 4

出力例 3

7

ノートは合計で 7 冊ある．したがって 7 を出力する．

問題文

0 以上の整数 A と B が与えられる．

A でも B でもない 0 以上の整数のうち，最も小さいものを出力せよ．

制約

• 0 \leqq A \leqq 100．
• 0 \leqq B \leqq 100．
• 入力される値はすべて整数である．

入力例 1

0 4

出力例 1

1

0 でも 4 でもない 0 以上の整数のうち，最も小さいものは 1 である．したがって 1 を出力する．

入力例 2

1 0

出力例 2

2

1 でも 0 でもない 0 以上の整数のうち，最も小さいものは 2 である．したがって 2 を出力する．

入力例 3

9 12

出力例 3

0

9 でも 12 でもない 0 以上の整数のうち，最も小さいものは 0 である．したがって 0 を出力する．

入力例 4

0 0

出力例 4

1

0 でも 0 でもない 0 以上の整数のうち，最も小さいものは 1 である．したがって 1 を出力する．

A と B が等しい場合もあることに注意せよ．

問題文

32 チームが参加するスポーツ大会が行われる．それぞれのチームには 1 から 32 まで番号が付けられている．

チーム i (1 \leqq i \leqq 32) の強さは A_i で，すべてのチームの強さは互いに異なる．2 チームが試合をすると，強さが大きいチームが必ず勝つ．

大会は全 5 ラウンドのトーナメント戦で行われる．

第 1 ラウンドの開始時，チームは左からチーム 1,2,\ldots,32 の順に一列に並んでいる．

各ラウンドでは，左から順に隣り合う 2 チームずつ組になり，それぞれ試合を行う． そのラウンドにおけるすべての試合が終了すると，それぞれの試合の勝者だけが次のラウンドに進む．勝者たちは，このラウンドで試合が行われた順番に左から一列に並び，次のラウンドに進む．

この操作をチームが 1 つになるまで繰り返す．第 5 ラウンドでは 2 チームが残り，試合を行う．この試合を決勝戦と呼び，決勝戦に勝ったチームが優勝，負けたチームが準優勝となる．

決勝戦である第 5 ラウンドの試合で敗れ，準優勝となるチームの番号を求めよ．

制約

• 1 \leqq A_i \leqq 1\,000 (1 \leqq i \leqq 32)．
• A_i \neq A_j (1 \leqq i < j \leqq 32)．
• 入力される値はすべて整数である．

入力例 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

出力例 1

16

第 5 ラウンドの試合ではチーム 16 とチーム 32 が試合を行う．チーム 16 の強さは A_{16}=16 で，チーム 32 の強さは A_{32}=32 であるため，チーム 32 が勝利し，チーム 16 が準優勝となる．よって，16 を出力する．

入力例 2

15 17 29 6 7 19 16 26 20 13 32 5 21 4 27 2 22 12 14 28 24 8 30 10 31 1 11 18 25 3 23 9

出力例 2

25

第 5 ラウンドの試合ではチーム 11 とチーム 25 が試合を行う．チーム 11 の強さは A_{11}=32 で，チーム 25 の強さは A_{25}=31 であるため，チーム 11 が勝利し，チーム 25 が準優勝となる．よって，25 を出力する．

入力例 3

19 2 5 12 44 40 24 16 3 26 23 21 41 28 9 39 43 22 15 14 7 49 17 46 34 4 32 30 45 27 33 36

出力例 3

5

第 5 ラウンドの試合ではチーム 5 とチーム 22 が試合を行う．チーム 5 の強さは A_{5}=44 で，チーム 22 の強さは A_{22}=49 であるため，チーム 22 が勝利し，チーム 5 が準優勝となる．よって，5 を出力する．

入力例 4

538 714 395 303 912 315 903 629 588 760 590 344 794 577 541 193 404 325 544 536 435 975 340 511 806 769 44 95 741 519 332 973

出力例 4

5

第 5 ラウンドの試合ではチーム 5 とチーム 22 が試合を行う．チーム 5 の強さは A_{5}=912 で，チーム 22 の強さは A_{22}=975 であるため，チーム 22 が勝利し，チーム 5 が準優勝となる．よって，5 を出力する．

問題文

長さ N の数列 A=(A_1,A_2,\cdots,A_N) が与えられる.

次の 2 つの条件をともに満たす 2 つの整数の組 (i,j) の個数を求めよ.

• 1 \leqq i < j \leqq N．
• A_i が A_j の倍数である．

制約

• 2\leqq N \leqq 1\,000．
• 1\leqq A_i \leqq 1\,000\,000 (1\leqq i \leqq N)．
• 入力される値はすべて整数である．

入力例 1

4
1 6 2 3

出力例 1

2

• A_2=6 は A_3=2 の倍数で，かつ 2<3 である．そのため，整数の組 (2,3) は 2 つの条件をともに満たす．
• A_2=6 は A_4=3 の倍数で，かつ 2<4 である．そのため，整数の組 (2,4) は 2 つの条件をともに満たす．

条件を満たす整数の組は (2,3),(2,4) の 2 個である．したがって 2 を出力する．

入力例 2

6
30 30 30 60 60 60

出力例 2

6

条件を満たす整数の組は (1,2),(1,3),(2,3),(4,5),(4,6),(5,6) の 6 個である．したがって 6 を出力する．

入力例 3

5
50 25 5 5 1

出力例 3

10

条件を満たす整数の組は 10 個である．したがって 10 を出力する．

問題文

J, O, I, G からなる，空でない文字列 S が与えられる． 文字列 T が空文字列で初期化されている．次の操作を好きな回数行うことで T=S とすることができるか判定せよ．

• T の末尾に JOI，IOI，JOIG のいずれかを追加する．

制約

• S の長さは 1 以上 100\,000 以下である．
• S の各文字は J, O, I, G のいずれかである．

小課題

1. (20 点) S は O, I からなる文字列である．
2. (20 点) S は J, O, I からなる文字列である．
3. (20 点) S の長さは 20 以下である．
4. (40 点) 追加の制約はない．

入力例 1

JOIJOIGIOI

出力例 1

Yes

T の末尾に JOI, JOIG, IOI をこの順に追加することで，T=S とすることができる．

この入力例は小課題 3, 4 の制約を満たす．

入力例 2

IOIOI

出力例 2

No

T の長さを 5 にすることはできないため，T=S とすることはできない．

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

入力例 3

JOIIOIIOIJOI

出力例 3

Yes

この入力例は小課題 2, 3, 4 の制約を満たす．

入力例 4

JOJGIOIJOIIOI

出力例 4

No

この入力例は小課題 3, 4 の制約を満たす．

問題文

JOI 高校の葵さんは，友達にお菓子を配ることにした．

葵さんには，N 人の友達がおり，1 から N までの番号が付けられている．

葵さんはアイスクリームを X 個，チョコレートを Y 個持っている．葵さんは，N 人の友達全員にアイスクリームまたはチョコレートのいずれか一方を 1 個ずつ配ることにした．ここで，アイスクリームとチョコレートは合わせて N 個以上であることが保証される．そのため，葵さんは友達全員にお菓子を配ることが可能である．

友達 i (1 \leqq i \leqq N) は，アイスクリームをもらうと A_i の嬉しさを，チョコレートをもらうと B_i の嬉しさを得る．

このとき，葵さんの友達全員が得る嬉しさの合計としてあり得る最大値を出力せよ．

制約

• 1\leqq N \leqq 200\,000．
• 0\leqq X \leqq N．
• 0\leqq Y \leqq N．
• N \leqq X + Y．
• 1\leqq A_i \leqq 10^9 (1\leqq i \leqq N)．
• 1\leqq B_i \leqq 10^9 (1\leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

1. (5 点) N=1．
2. (5 点) X=N，Y=0．
3. (5 点) X=N，Y=N．
4. (25 点) X=N，Y=1．
5. (25 点) X+Y=N．
6. (10 点) N \leqq 10．
7. (25 点) 追加の制約はない．

入力例 1

2 1 1
10 20
40 30

出力例 1

60

葵さんがお菓子を配る方法は以下の 2 通りである．

• 友達 1 にアイスクリームを配り，友達 2 にチョコレートを配る場合，嬉しさの合計は A_1 + B_2 = 10 + 30 = 40 である．
• 友達 1 にチョコレートを配り，友達 2 にアイスクリームを配る場合，嬉しさの合計は B_1 + A_2 = 40 + 20 = 60 である．

この 2 通りのうち，嬉しさの合計が最大となるのは後者であり，そのときの嬉しさの合計は 60 である．したがって 60 を出力する．

この入力例は小課題 5, 6, 7 の制約を満たす．

入力例 2

2 2 2
10 20
40 30

出力例 2

70

葵さんがお菓子を配る方法は以下の 4 通りである．

• 友達 1 と 友達 2 の両方にアイスクリームを配る場合，嬉しさの合計は A_1 + A_2 = 10 + 20 = 30 である．
• 友達 1 にアイスクリームを配り，友達 2 にチョコレートを配る場合，嬉しさの合計は A_1 + B_2 = 10 + 30 = 40 である．
• 友達 1 にチョコレートを配り，友達 2 にアイスクリームを配る場合，嬉しさの合計は B_1 + A_2 = 40 + 20 = 60 である．
• 友達 1 と 友達 2 の両方にチョコレートを配る場合，嬉しさの合計は B_1 + B_2 = 40 + 30 = 70 である．

この 4 通りのうち，嬉しさの合計が最大となるのは最後の場合であり，そのときの嬉しさの合計は 70 である．したがって 70 を出力する．

この入力例は小課題 3, 6, 7 の制約を満たす．

入力例 3

1 1 0
1234
5678

出力例 3

1234

この入力例において，葵さんには友達が 1 人しかいない．

この入力例は小課題 1, 2, 5, 6, 7 の制約を満たす．

入力例 4

10 10 1
314159265 358979323 846264338 327950288 419716939 937510582 97494459 230781640 628620899 862803482
534211706 798214808 651328230 664709384 460955058 223172535 940812848 111745028 410270193 852110555

出力例 4

5867599604

出力が 32bit 整数型に収まらない場合があることに注意せよ．

この入力例は小課題 4, 6, 7 の制約を満たす．