C - Delimiter

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 個の整数 A_1,A_2,\dots,A_N が、 1 行に 1 つずつ、 N 行にわたって与えられます。但し、 N は入力では与えられません。
さらに、以下が保証されます。

  • A_i \neq 0 ( 1 \le i \le N-1 )
  • A_N = 0

A_N, A_{N-1},\dots,A_1 をこの順に出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 100
  • 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
  • A_N = 0

入力

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

A_1
A_2
\vdots
A_N

出力

A_N, A_{N-1},\dots,A_1 をこの順に、改行区切りで整数として出力せよ。


入力例 1

3
2
1
0

出力例 1

0
1
2
3

繰り返しになりますが、 N は入力では与えられないことに注意してください。
この入力においては N=4 で、 A=(3,2,1,0) です。


入力例 2

0

出力例 2

0

A=(0) です。


入力例 3

123
456
789
987
654
321
0

出力例 3

0
321
654
987
789
456
123

Score: 150 points

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

  • A_i \neq 0 ( 1 \le i \le N-1 )
  • A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

  • All input values are integers.
  • 1 \le N \le 100
  • 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
  • A_N = 0

Input

The input is given from Standard Input in the following format:

A_1
A_2
\vdots
A_N

Output

Print A_N, A_{N-1}, \dots, A_1 in this order, as integers, separated by newlines.


Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).


Sample Input 2

0

Sample Output 2

0

A=(0).


Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123
D - Make Target

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

概要:以下のような N\times N の模様を作成してください。
###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

正整数 N が与えられます。

N\times N のグリッドがあります。このグリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表します。はじめ、どのマスにも色は塗られていません。

これから、i=1,2,\dots,N の順に、以下の操作を行います。

  • j=N+1-i とする。
  • i\leq j であるならば、i が奇数ならば黒、偶数ならば白で、マス (i,i) を左上、マス (j,j) を右下とする矩形領域に含まれるマスを塗りつぶす。このとき、既に色が塗られているマスについては色を上書きする。
  • i\gt j であるならば、何もしない。

すべての操作を行った後、色が塗られていないマスが存在しないことが証明できます。最終的に各マスがどの色で塗られているかを求めてください。

制約

  • 1\leq N\leq 50
  • 入力はすべて整数

入力

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

N

出力

N 行出力せよ。i 行目には、最終的にグリッドの i 行目に塗られている色を以下のような長さ N の文字列 S_i として出力せよ。入出力例も参考にすること。

  • マス (i,j) が最終的に黒で塗られているならば、S_i の j 文字目は # である。
  • マス (i,j) が最終的に白で塗られているならば、S_i の j 文字目は . である。

入力例 1

11

出力例 1

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

概要で示した模様と同じです。


入力例 2

5

出力例 2

#####
#...#
#.#.#
#...#
#####

以下のように色が塗られます。ここで、まだ色が塗られていないマスを ? と表します。

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

入力例 3

8

出力例 3

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

入力例 4

2

出力例 4

##
##

Score : 200 points

Problem Statement

Overview: Create an N \times N pattern as follows.
###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

You are given a positive integer N.

Consider an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. Initially, no cell is colored.

Then, for i = 1,2,\dots,N in order, perform the following operation:

  • Let j = N + 1 - i.
  • If i \leq j, fill the rectangular region whose top-left cell is (i,i) and bottom-right cell is (j,j) with black if i is odd, or white if i is even. If some cells are already colored, overwrite their colors.
  • If i > j, do nothing.

After all these operations, it can be proved that there are no uncolored cells. Determine the final color of each cell.

Constraints

  • 1 \leq N \leq 50
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N

Output

Print N lines. The i-th line should contain a length-N string S_i representing the colors of the i-th row of the grid after all operations, as follows:

  • If cell (i,j) is finally colored black, the j-th character of S_i should be #.
  • If cell (i,j) is finally colored white, the j-th character of S_i should be ..

Sample Input 1

11

Sample Output 1

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

This matches the pattern shown in the Overview.


Sample Input 2

5

Sample Output 2

#####
#...#
#.#.#
#...#
#####

Colors are applied as follows, where ? denotes a cell not yet colored:

         i=1      i=2      i=3      i=4      i=5
?????    #####    #####    #####    #####    #####
?????    #####    #...#    #...#    #...#    #...#
????? -> ##### -> #...# -> #.#.# -> #.#.# -> #.#.#
?????    #####    #...#    #...#    #...#    #...#
?????    #####    #####    #####    #####    #####

Sample Input 3

8

Sample Output 3

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.####.#
#......#
########

Sample Input 4

2

Sample Output 4

##
##
E - Blue Spring

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。

ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。

N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq D\leq 2\times 10^5
  • 1\leq P\leq 10^9
  • 1\leq F_i\leq 10^9
  • 入力はすべて整数

入力

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

N D P
F_1 F_2 \ldots F_N

出力

N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。


入力例 1

5 2 10
7 1 6 3 6

出力例 1

20

1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。


入力例 2

3 1 10
1 2 3

出力例 2

6

3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。


入力例 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

3000000000

1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。

Score : 300 points

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq D\leq 2\times 10^5
  • 1\leq P\leq 10^9
  • 1\leq F_i\leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N D P
F_1 F_2 \ldots F_N

Output

Print the minimum possible total cost for the N-day trip.


Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.


Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.


Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

F - Robot Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

子供と大人があわせて N 人います。i 番目の人の体重は W_i です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ N の文字列 S によって表され、
S の i 文字目が 0 であるとき i 番目の人が子供であることを、1 であるとき i 番目の人が大人であることをさします。

ロボットである高橋君に対して実数 X を設定すると、 高橋君はそれぞれの人に対して、体重が X 未満なら子供、X 以上なら大人と判定します。
実数 X に対してf(X) を、高橋君に X を設定したときに N 人のうち子供か大人かを正しく判定できる人数で定めます。

X が実数全体を動くとき、f(X) の最大値を求めてください。

制約

  • 1\leq N\leq 2\times 10^5
  • S は 0 と 1 からなる長さ N の文字列
  • 1\leq W_i\leq 10^9
  • N,W_i は整数

入力

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

N
S
W_1 W_2 \ldots W_N

出力

f(X) の最大値を整数で一行に出力せよ。


入力例 1

5
10101
60 45 30 40 80

出力例 1

4

X=50 と設定すると、高橋君は 2,3,4 番目の人を子供、 1,5 番目の人を大人と判定します。
実際には 2,4 番目の人が子供、 1,3,5 番目の人が大人であるので、このとき、1,2,4,5 番目の合計 4 人に対して正しく判定できています。 よって、f(50)=4 です。

5 人全員に対して正しく判定できるような X は存在しないのでこのときが最大です。よって、4 を出力します。


入力例 2

3
000
1 2 3

出力例 2

3

例えば、X=10 とすると最大値 f(10)=3 を達成します。
全員が大人、または全員が子供である可能性もあることに注意してください。


入力例 3

5
10101
60 50 50 50 60

出力例 3

4

例えば、X=55 とすると最大値 f(55)=4 を達成します。
同じ体重の人が複数人存在する可能性もあることに注意してください。

Score : 300 points

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

  • 1\leq N\leq 2\times 10^5
  • S is a string of length N consisting of 0 and 1.
  • 1\leq W_i\leq 10^9
  • N and W_i are integers.

Input

Input is given from Standard Input in the following format:

N
S
W_1 W_2 \ldots W_N

Output

Print the maximum value of f(X) as an integer in a single line.


Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

4

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.


Sample Input 2

3
000
1 2 3

Sample Output 2

3

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.


Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

4

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

G - Snuke Maze

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

H 行 W 列のグリッドがあります。 以下、上から i 行目、左から j 列目のマスを (i,j) と表記します。 グリッドの各マスには英小文字が書かれており、(i,j) に書かれた文字は与えられる文字列 S_i の j 文字目と一致します。

すぬけくんは、辺で隣接するマスに移動することを繰り返して (1,1) から (H,W) まで移動しようと思っています。 訪れるマス (最初の (1,1) と 最後の (H,W) を含む)に書かれた文字が、 訪れる順に s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots となるような経路が存在するか判定してください。 なお、2 つのマス (i_1,j_1),(i_2,j_2) は |i_1-i_2|+|j_1-j_2| = 1 を満たすとき、またそのときに限り「辺で隣接する」といいます。

より厳密には、マスの列 ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) であって以下の条件を全て満たすものが存在するか判定してください。

  • (i_1,j_1) = (1,1),(i_k,j_k) = (H,W)
  • すべての t\ (1 \leq t < k) について、(i_t,j_t) と (i_{t+1},j_{t+1}) は辺で隣接する
  • すべての t\ (1 \leq t \leq k) について、(i_t,j_t) に書かれた文字は snuke の ((t-1) \bmod 5) + 1 文字目と一致する

制約

  • 2\leq H,W \leq 500
  • H,W は整数
  • S_i は英小文字からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H

出力

問題文中の条件を満たす経路が存在するならば Yes を、存在しないならば No を出力せよ。


入力例 1

2 3
sns
euk

出力例 1

Yes

(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) という経路は、訪れたマスに書かれた文字が訪れた順に s \rightarrow n \rightarrow u \rightarrow k となるため条件を満たします。


入力例 2

2 2
ab
cd

出力例 2

No

入力例 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

出力例 3

Yes

Score : 400 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.

Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W). Determine if there is a path in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting. Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.

Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:

  • (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
  • (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
  • the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of snuke, for all t\ (1 \leq t \leq k).

Constraints

  • 2\leq H,W \leq 500
  • H and W are integers.
  • S_i is a string of length W consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H

Output

Print Yes if there is a path satisfying the conditions in the problem statement; print No otherwise.


Sample Input 1

2 3
sns
euk

Sample Output 1

Yes

The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.


Sample Input 2

2 2
ab
cd

Sample Output 2

No

Sample Input 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Sample Output 3

Yes