A - Hands

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

100 階建ての建物 A , B があります。 i = 1,\dots, 100 について、建物 Ai 階と Bi 階は廊下で繋がれています。 また、i = 1,\dots, 99 について、建物 Ai+1 階と Bi 階は廊下で繋がれています。 どの廊下も双方向に通行可能で、移動には x 分かかります。 また、A, B どちらの建物にも階段があり、i=1,\dots,99 について、同じ建物の i 階と i+1 階は階段で繋がれています。どの階段も双方向に通行可能で、移動には y 分かかります。

### 制約

• 1 \leq a,b,x,y \leq 100
• 入力はすべて整数

### 入力

a b x y


### 入力例 1

2 1 1 5


### 出力例 1

1


### 入力例 2

1 2 100 1


### 出力例 2

101


### 入力例 3

1 100 1 100


### 出力例 3

199


Score : 300 points

### Problem Statement

There are two 100-story buildings, called A and B. (In this problem, the ground floor is called the first floor.)

For each i = 1,\dots, 100, the i-th floor of A and that of B are connected by a corridor. Also, for each i = 1,\dots, 99, there is a corridor that connects the (i+1)-th floor of A and the i-th floor of B. You can traverse each of those corridors in both directions, and it takes you x minutes to get to the other end.

Additionally, both of the buildings have staircases. For each i = 1,\dots, 99, a staircase connects the i-th and (i+1)-th floors of a building, and you need y minutes to get to an adjacent floor by taking the stairs.

Find the minimum time needed to reach the b-th floor of B from the a-th floor of A.

### Constraints

• 1 \leq a,b,x,y \leq 100
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

a b x y


### Output

Print the minimum time needed to reach the b-th floor of B from the a-th floor of A.

### Sample Input 1

2 1 1 5


### Sample Output 1

1


There is a corridor that directly connects the 2-nd floor of A and the 1-st floor of B, so you can travel between them in 1 minute. This is the fastest way to get there, since taking the stairs just once costs you 5 minutes.

### Sample Input 2

1 2 100 1


### Sample Output 2

101


For example, if you take the stairs to get to the 2-nd floor of A and then use the corridor to reach the 2-nd floor of B, you can get there in 1+100=101 minutes.

### Sample Input 3

1 100 1 100


### Sample Output 3

199


Using just corridors to travel is the fastest way to get there.

B - log

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけ君は、渋谷の丸太やさんに丸太を買いに来ました。 すぬけ君は長さ 1 から n までの n 種類の丸太が 1 本ずつほしいです。 丸太やさんには、長さ 1 から n+1 までの n+1 種類の丸太がそれぞれ 1 円で売られています。どの丸太の在庫も 1 本ずつしかありません。

すぬけ君は買った丸太を切る作業を好きなだけ行えます。つまり、L = L_1 + \dots + L_k であるとき、長さ L の丸太 1 本から、長さ L_1, \dots, L_kk 本の丸太を作る作業を何度でもできます。また、不要な丸太を捨てることができます。

すぬけ君はできるだけ安く丸太を手に入れたいです。 長さ 1 から n までの n 種類の丸太を 1 本ずつ手に入れるために必要な最小の金額を求めてください。

### 制約

• 1 \leq n \leq 10^{18}

### 入力

n


### 入力例 1

4


### 出力例 1

3


• 長さ 2,4,5 の丸太を買う
• 長さ 5 の丸太を切って 長さ 1 の丸太 2 本と長さ 3 の丸太を作る
• 長さ 1 の丸太を 1 本捨てる

### 入力例 2

109109109109109109


### 出力例 2

109109108641970782


Score : 400 points

### Problem Statement

Snuke is visiting a shop in Tokyo called 109 to buy some logs. He wants n logs: one of length 1, one of length 2, ..., and one of length n. The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).

He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.

Snuke wants to spend as little money as possible to get the logs he wants. Find the minimum amount of money needed to get n logs of length 1 to n.

### Constraints

• 1 \leq n \leq 10^{18}

### Input

Input is given from Standard Input in the following format:

n


### Output

Print the minimum amount of money needed to get n logs of length 1 to n.

### Sample Input 1

4


### Sample Output 1

3


One way to get the logs he wants with 3 yen is:

• Buy logs of length 2, 4, and 5.
• Cut the log of length 5 into two logs of length 1 each and a log of length 3.
• Throw away one of the logs of length 1.

### Sample Input 2

109109109109109109


### Sample Output 2

109109108641970782

C - Large RPS Tournament

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

r-l2 のべき乗であるような l, r について、番号が l 以上 r 未満の参加者による大会を開いたとき、勝者は次のようにして決定されます。

• r-l=1 であるとき（つまり、参加者がただ一人であるとき）、勝者は l とする。
• r-l\geq 2 であるとき、m=(l+r)/2 として、l 以上 m 未満の参加者による大会と、m 以上 r 未満の参加者による大会を開催する。それぞれの勝者が a, b であるとき、ab がじゃんけんをして勝ったほうを勝者とする。あいこの場合 a を勝者とする。

### 注意

• a\text{ mod } bab で割ったあまりを表す
• じゃんけんの勝敗は次のように決められる
• 同じ手同士はあいこである
• RS に勝つ
• PR に勝つ
• SP に勝つ

### 制約

• 1 \leq n,k \leq 100
• sR, P, S のみからなる長さ n の文字列

### 入力

n k
s


### 入力例 1

3 2
RPS


### 出力例 1

P

• 番号が 0 以上 2 未満の参加者による大会の勝者の得意な手は P です。
• 番号が 2 以上 4 未満の参加者による大会の勝者の得意な手は R です。
• 番号が 0 以上 4 未満の参加者による大会の勝者の得意な手は P です。

よって、答えは P となります。

   P
┌─┴─┐
P   R
┌┴┐ ┌┴┐
R P S R


### 入力例 2

11 1
RPSSPRSPPRS


### 出力例 2

P


### 入力例 3

1 100
S


### 出力例 3

S


Score : 500 points

### Problem Statement

To decide which is the strongest among Rock, Paper, and Scissors, we will hold an RPS tournament. There are 2^k players in this tournament, numbered 0 through 2^k-1. Each player has his/her favorite hand, which he/she will use in every match.

A string s of length n consisting of R, P, and S represents the players' favorite hands. Specifically, the favorite hand of Player i is represented by the ((i\text{ mod } n) + 1)-th character of s; R, P, and S stand for Rock, Paper, and Scissors, respectively.

For l and r such that r-l is a power of 2, the winner of the tournament held among Players l through r-1 will be determined as follows:

• If r-l=1 (that is, there is just one player), the winner is Player l.
• If r-l\geq 2, let m=(l+r)/2, and we hold two tournaments, one among Players l through m-1 and the other among Players m through r-1. Let a and b be the respective winners of these tournaments. a and b then play a match of rock paper scissors, and the winner of this match - or a if the match is drawn - is the winner of the tournament held among Players l through r-1.

Find the favorite hand of the winner of the tournament held among Players 0 through 2^k-1.

### Notes

• a\text{ mod } b denotes the remainder when a is divided by b.
• The outcome of a match of rock paper scissors is determined as follows:
• If both players choose the same hand, the match is drawn;
• R beats S;
• P beats R;
• S beats P.

### Constraints

• 1 \leq n,k \leq 100
• s is a string of length n consisting of R, P, and S.

### Input

Input is given from Standard Input in the following format:

n k
s


### Output

Print the favorite hand of the winner of the tournament held among Players 0 through 2^k-1, as R, P, or S.

### Sample Input 1

3 2
RPS


### Sample Output 1

P

• The favorite hand of the winner of the tournament held among Players 0 through 1 is P.
• The favorite hand of the winner of the tournament held among Players 2 through 3 is R.
• The favorite hand of the winner of the tournament held among Players 0 through 3 is P.

Thus, the answer is P.

   P
┌─┴─┐
P   R
┌┴┐ ┌┴┐
R P S R


### Sample Input 2

11 1
RPSSPRSPPRS


### Sample Output 2

P


### Sample Input 3

1 100
S


### Sample Output 3

S

D - L

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

3 つの石が次の条件を満たしているとき、くの字に並んでいるといいます。

• どの石も、座標が整数である点に置かれている
• どの石も、別の石と隣接している（石からの距離が 1 である場所に別の石が存在する）
• 3 つの石が一直線上に存在しない

T 個のケースが与えられるので、それぞれについて答えを求めてください。

### 注意

3 つの石は互いに区別できないとします。例えば、最初に点 (0,0) に置かれていた石が最終的に点 (ax, ay), (bx, by), (cx, cy) のどこに置かれていても構いません。

### 制約

• 1 \leq T \leq 10^3
• |ax|,|ay|,|bx|,|by|,|cx|,|cy| \leq 10^9
• (ax, ay), (bx, by), (cx, cy) に石がひとつずつ置かれている時、石はくの字に並んでいる

### 入力

T
\text{case}_1
\vdots
\text{case}_T


ax ay bx by cx cy


### 出力

T 個の値を出力せよ。i 個目には \text{case}_i に対応する操作回数の最小値を出力せよ。

### 入力例 1

1
3 2 2 2 2 1


### 出力例 1

4


....    ....    ....    ..#.    ..##
#... -> ##.. -> .##. -> .##. -> ..#.
##..    .#..    .#..    ....    ....


### 入力例 2

10
0 0 1 0 0 1
1 0 0 1 1 1
2 -1 1 -1 1 0
1 -2 2 -1 1 -1
-1 2 0 2 -1 3
-1 -2 -2 -2 -2 -3
-2 4 -3 3 -2 3
3 1 4 2 4 1
-4 2 -4 3 -3 3
5 4 5 3 4 4


### 出力例 2

0
1
2
3
4
5
6
7
8
9


Score : 600 points

### Problem Statement

We have three stones at points (0, 0), (1,0), and (0,1) on a two-dimensional plane.

These three stones are said to form an L when they satisfy the following conditions:

• Each of the stones is at integer coordinates.
• Each of the stones is adjacent to another stone. (That is, for each stone, there is another stone whose distance from that stone is 1.)
• The three stones do not lie on the same line.

Particularly, the initial arrangement of the stone - (0, 0), (1,0), and (0,1) - forms an L.

You can do the following operation any number of times: choose one of the stones and move it to any position. However, after each operation, the stones must form an L. You want to do as few operations as possible to put stones at points (ax, ay), (bx, by), and (cx, cy). How many operations do you need to do this?

It is guaranteed that the desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L. Under this condition, it is always possible to achieve the objective with a finite number of operations.

You will be given T cases of this problem. Solve each of them.

### Notes

We assume that the three stones are indistinguishable. For example, the stone that is initially at point (0,0) may be at any of the points (ax, ay), (bx, by), and (cx, cy) in the end.

### Constraints

• 1 \leq T \leq 10^3
• |ax|,|ay|,|bx|,|by|,|cx|,|cy| \leq 10^9
• The desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L.

### Input

Input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T


Each case is in the following format:

ax ay bx by cx cy


### Output

Print T values. The i-th value should be the minimum number of operations for \text{case}_i.

### Sample Input 1

1
3 2 2 2 2 1


### Sample Output 1

4


Let us use # to represent a stone. You can move the stones to the specified positions with four operations, as follows:

....    ....    ....    ..#.    ..##
#... -> ##.. -> .##. -> .##. -> ..#.
##..    .#..    .#..    ....    ....


### Sample Input 2

10
0 0 1 0 0 1
1 0 0 1 1 1
2 -1 1 -1 1 0
1 -2 2 -1 1 -1
-1 2 0 2 -1 3
-1 -2 -2 -2 -2 -3
-2 4 -3 3 -2 3
3 1 4 2 4 1
-4 2 -4 3 -3 3
5 4 5 3 4 4


### Sample Output 2

0
1
2
3
4
5
6
7
8
9

E - 1D Reversi Builder

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

まず、黒石さんは、各マスについて独立に、黒か白を等確率で選んで塗ります。その後、マス s にマスの色と同じ色の石を置きます。

1. 石が置かれているマスと隣接している空きマスをひとつ選ぶ。マス i を選んだとする。
2. マス i に、マスと同じ色の石をおく。
3. 置いた石と同じ色の石がマス i 以外に置かれているとき、そのうちマス i に最も近い石と、マス i の間にあるすべての石の色をマス i の色に変更する

s=1,\dots,n それぞれの場合について、ゲーム終了時の黒い石の個数の期待値を \text{mod }998244353 で求めてください。

### 制約

• 1 \leq n \leq 2\times 10^5

### 入力

n


### 出力

n 個の値を出力せよ。 i 個目には、s=i としたときのゲーム終了時の黒い石の個数の期待値を \text{mod }998244353 で出力せよ。

### 入力例 1

3


### 出力例 1

499122178
499122178
499122178


s によらず、それぞれの盤面について、ゲーム終了時の黒い石の個数は 0,1,0,2,1,3,2,3 となります。 よって、期待値は (0+1+0+2+1+3+2+3)/8 = 3/2 となるため、答えは 2r \equiv 3 ~(\text{mod } 998244353) かつ 0 \leq r \lt 998244353 を満たす r = 499122178 となります。

### 入力例 2

10


### 出力例 2

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5


### 入力例 3

19


### 出力例 3

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186


Score : 700 points

### Problem Statement

Kuro and Shiro are playing with a board composed of n squares lining up in a row. The squares are numbered 1 to n from left to right, and Square s has a mark on it.

First, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square s a stone of the same color as the square.

Kuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:

1. Choose an empty square adjacent to a square with a stone on it. Let us say Square i is chosen.
2. Put on Square i a stone of the same color as the square.
3. If there are squares other than Square i that contain a stone of the same color as the stone just placed, among such squares, let Square j be the one nearest to Square i. Change the color of every stone between Square i and Square j to the color of Square i.

The game ends when the board has no empty square.

Kuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.

For each of the cases s=1,\dots,n, find the expected value, modulo 998244353, of the number of black stones at the end of the game.

### Notes

When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq=p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353, which we ask you to find.

### Constraints

• 1 \leq n \leq 2\times 10^5

### Input

Input is given from Standard Input in the following format:

n


### Output

Print n values. The i-th value should be the expected value, modulo 998244353, of the number of black stones at the end of the game for the case s=i.

### Sample Input 1

3


### Sample Output 1

499122178
499122178
499122178


Let us use b to represent a black square and w to represent a white square. There are eight possible boards: www, wwb, wbw, wbb, bww, bwb, bbw, and bbb, which are chosen with equal probability.

For each of these boards, there will be 0, 1, 0, 2, 1, 3, 2, and 3 black stones at the end of the game, respectively, regardless of the value of s. Thus, the expected number of stones is (0+1+0+2+1+3+2+3)/8 = 3/2, and the answer is r = 499122178, which satisfies 2r = 3 ~(\text{mod } 998244353) and 0 \leq r \lt 998244353.

### Sample Input 2

10


### Sample Output 2

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5


### Sample Input 3

19


### Sample Output 3

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186

F - 1D Kingdom Builder

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけ君は、一列に並んだ無限個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ整数が振られていて、任意の整数 i についてマス i と マス i+1 は隣り合っています。 また、それぞれのマスは白か黒で塗られています。

この盤面のマスの色は、長さ nw, b からなる文字列 s によって以下のように表されます。

• i = 1, 2, \dots, n について、si 文字目が w であるときマス i は白色であり、b であるときマス i は黒色である
• i \leq 0 について、マス i は白色である
• i > n について、マス i は黒色である

すぬけ君は白いコマと黒いコマをそれぞれ無限個持っています。すぬけ君は次の手順でこれらのコマを盤面に置いていきます。

• (1) 好きな色のコマを選ぶ
• (2) すでにコマが置かれているマスと隣り合ったマスのうち、選んだコマと同じ色の空きマスを探す
• (2a) そのようなマスが存在する場合、そのうちひとつを選びコマを置く
• (2b) そのようなマスが存在しない場合、 選んだコマと同じ色の空きマスをひとつを選びコマを置く

### 制約

• 1 \leq n \leq 10^5
• |s| = |t| = n
• swb のみからなる
• to_ のみからなる
• to1 文字以上含む

### 入力

n
s
t


### 出力

すぬけ君が置く必要のあるコマの数の最小値を出力せよ。

### 入力例 1

3
wbb
o_o


### 出力例 1

2


コマを置かなくてはならない白マスと黒マスをそれぞれ WB で表して、 コマを置かなくてもよい白マスと黒マスをそれぞれ wb で表すことにします。 盤面は次のようになります。

...wwwwwwWbBbbbbb...


...wwwwwwWbBbbbbb...
2 1


...wwwwwwWbBbbbbb...
123


### 入力例 2

4
wwww
o__o


### 出力例 2

3


...wwwwwWwwWbbbbb...
1  32


### 入力例 3

9
bbwbwbwbb
_o_o_o_o_


### 出力例 3

5


...wwwwwbBwBwBwBbbbbbb...
12 3 4 5


### 入力例 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_


### 出力例 4

11


Score : 900 points

### Problem Statement

Snuke is playing with a board composed of infinitely many squares lining up in a row. Each square has an assigned integer; for each integer i, Square i and Square i+1 are adjacent. Additionally, each square is painted white or black.

A string s of length n consisting of w and b represents the colors of the squares of this board, as follows:

• For each i = 1, 2, \dots, n, Square i is white if the i-th character of s is w, and black if that character is b;
• For each i \leq 0, Square i is white;
• For each i > n, Square i is black.

Snuke has infinitely many white pieces and infinitely many black pieces. He will put these pieces on the board as follows:

• (1) Choose a piece of the color of his choice.
• (2) Among the squares adjacent to a square that already contains a piece, look for squares of the same color as the chosen piece.
• (2a) If there are such squares, choose one of them and put the piece on it;
• (2b) if there is no such square, choose a square of the same color as the chosen piece and put the piece on it.

The board initially has no piece on it.

You are given a string t of length n consisting of o and _. Find the minimum number of pieces Snuke needs to put on the board to have a piece on every square i among Squares 1,..,n such that the i-th character of t is o. It is guaranteed that t has at least one occurrence of o.

### Constraints

• 1 \leq n \leq 10^5
• |s| = |t| = n
• s consists of w and b.
• t consists of o and _.
• t has at least one occurrence of o.

### Input

Input is given from Standard Input in the following format:

n
s
t


### Output

Print the minimum number of pieces Snuke needs to put on the board.

### Sample Input 1

3
wbb
o_o


### Sample Output 1

2


Let us use W to represent a white square that needs a piece on it, B to represent a black square that needs a piece on it, w to represent a white square that does not need a piece on it, and b to represent a black square that does not need a piece on it.

We have the following board:

...wwwwwwWbBbbbbb...


If we put pieces in the following order, two pieces is enough:

...wwwwwwWbBbbbbb...
2 1


Note that if we put a piece on the white square first, we will need three or more pieces:

...wwwwwwWbBbbbbb...
123


### Sample Input 2

4
wwww
o__o


### Sample Output 2

3


If we put pieces in the following order, three pieces is enough:

...wwwwwWwwWbbbbb...
1  32


### Sample Input 3

9
bbwbwbwbb
_o_o_o_o_


### Sample Output 3

5


If we put pieces in the following order, five pieces is enough:

...wwwwwbBwBwBwBbbbbbb...
12 3 4 5


### Sample Input 4

17
wwwwbbbbbbbbwwwwb
__o__o_o_ooo__oo_


### Sample Output 4

11