A - Treasure Chest

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

3 種類の文字 . | * からなる、長さ N の文字列 S が与えられます。 S には | がちょうど 2 つ、* がちょうど 1 つ含まれます。

2 つの | で囲まれた部分の中に * が含まれるか判定してください。 含まれている場合 in と、含まれていない場合 out と出力してください。

より厳密には、* より前にある文字のいずれかが | であり、かつ、* より後ろにある文字のいずれかが | であるか判定してください。

制約

  • 3\leq N\leq 100
  • N は整数
  • S は . | * からなる長さ N の文字列
  • S に | はちょうど 2 個含まれる
  • S に * はちょうど 1 個含まれる

入力

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

N
S

出力

2 つの | に囲まれた部分の中に * が含まれている場合 in と、含まれていない場合 out と 1 行に出力せよ。

入力例 1

10
.|..*...|.

出力例 1

in

2 つの | に囲まれた部分は |..*...| です。 この中に * が含まれているため、in と出力してください。

入力例 2

10
.|..|.*...

出力例 2

out

2 つの | に囲まれた部分は |..| です。 この中に * は含まれていないため、out と出力してください。

入力例 3

3
|*|

出力例 3

in

Score : 100 points

Problem Statement

You are given a string S of length N consisting of three kinds of characters: ., |, and *. S contains exactly two | and exactly one *.

Determine whether the * is between the two |, and if so, print in; otherwise, print out.

More formally, determine whether one of the characters before the * is | and one of the characters after the * is |.

Constraints

  • 3\leq N\leq 100
  • N is an integer.
  • S is a string of length N consisting of ., |, and *.
  • S contains exactly two |.
  • S contains exactly one *.

Input

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

N
S

Output

Print a single line containing in if the * is between the two |, and out otherwise.

Sample Input 1

10
.|..*...|.

Sample Output 1

in

Between the two |, we have |..*...|, which contains *, so you should print in.

Sample Input 2

10
.|..|.*...

Sample Output 2

out

Between the two |, we have |..|, which does not contain *, so you should print out.

Sample Input 3

3
|*|

Sample Output 3

in
B - A to Z String 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

A を N 個、B を N 個、…、Z を N 個この順に繋げて得られる文字列の先頭から X 番目の文字を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • 入力は全て整数

入力

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

N X

出力

答えを出力せよ。

入力例 1

1 3

出力例 1

C

得られる文字列は ABCDEFGHIJKLMNOPQRSTUVWXYZ です。先頭から 3 番目の文字は C です。

入力例 2

2 12

出力例 2

F

得られる文字列は AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ です。先頭から 12 番目の文字は F です。

Score : 100 points

Problem Statement

Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X \leq N\times 26
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the answer.

Sample Input 1

1 3

Sample Output 1

C

We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.

Sample Input 2

2 12

Sample Output 2

F

We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.
C - Minimize Abs 1

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) 及び整数 L,R が与えられます。ここで L,R は L\leq R を満たします。

i=1,2,\ldots,N について以下の 2 つの条件を共に満たす整数 X_i を求めてください。なお、求める整数は常に一意に定まります。

  • L\leq X_i \leq R
  • L 以上 R 以下であるようなどの整数 Y についても |X_i - A_i| \leq |Y-A_i| を満たす

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • 入力は全て整数

入力

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

N L R
A_1 \ldots A_N

出力

i=1,2,\ldots,N について X_i を空白区切りで出力せよ。

入力例 1

5 4 7
3 1 4 9 7

出力例 1

4 4 4 7 7

i=1 では、

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

より X_i = 4 です。

入力例 2

3 10 10
11 10 9

出力例 2

10 10 10

Score : 200 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

  • L\leq X_i \leq R.
  • For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq L\leq R \leq 10^9
  • 1\leq A_i\leq 10^9
  • All input values are integers.

Input

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

N L R
A_1 \ldots A_N

Output

Print X_i for i=1,2,\ldots,N, separated by spaces.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

  • |4-3|=1
  • |5-3|=2
  • |6-3|=3
  • |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10
D - Explore

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君はゲームの中で洞窟を探索しています。

洞窟は N 個の部屋が一列に並んだ構造であり、入り口から順に部屋 1,2,\ldots,N と番号がついています。

最初、高橋君は部屋 1 におり、持ち時間 は T です。
各 1 \leq i \leq N-1 について、持ち時間を A_i 消費することで、部屋 i から部屋 i+1 へ移動することができます。これ以外に部屋を移動する方法はありません。 また、持ち時間が 0 以下になるような移動は行うことができません。

洞窟内には M 個のボーナス部屋があります。i 番目のボーナス部屋は部屋 X_i であり、この部屋に到達すると持ち時間が Y_i 増加します。

高橋君は部屋 N にたどりつくことができますか？

制約

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq N-2
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 < X_1 < \ldots < X_M < N
  • 1 \leq Y_i \leq 10^9
  • 入力に含まれる値は全て整数である

入力

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

N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

高橋君が部屋 N にたどりつくことができるなら Yes を、できないなら No を出力せよ。

入力例 1

4 1 10
5 7 5
2 10

出力例 1

Yes
  • 高橋君は最初、部屋 1 にいて持ち時間は 10 です。
  • 持ち時間を 5 消費して部屋 2 に移動します。持ち時間は 5 になります。その後、持ち時間が 10 増え 15 になります。
  • 持ち時間を 7 消費して部屋 3 に移動します。持ち時間は 8 になります。
  • 持ち時間を 5 消費して部屋 4 に移動します。持ち時間は 3 になります。

入力例 2

4 1 10
10 7 5
2 10

出力例 2

No

部屋 1 から部屋 2 へ移動することができません。

Score : 200 points

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq N-2
  • 1 \leq T \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 1 < X_1 < \ldots < X_M < N
  • 1 \leq Y_i \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

If Takahashi can reach Room N, print Yes; otherwise, print No.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes
  • Takahashi is initially in Room 1, and the time limit is 10.
  • He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
  • He consumes a time of 7 to move to Room 3. Now the time limit is 8.
  • He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.
E - Reverse Permutation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

整数 N と o と x からなる長さ N の文字列 S が与えられます。

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) があります。はじめ A=(1,2,\ldots,N) です。

A に対して k=1,2,\ldots,N の順に以下の操作を行います：

  • S_k= o である場合、A の先頭 k 項を反転する。具体的には、A を (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N) に置き換える。
  • S_k= x である場合は何もしない。

全ての操作を終えた後の A を求めてください。

制約

  • 2\le N\le 5\times 10^5
  • N は整数
  • S は o と x からなる長さ N の文字列

入力

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

N
S

出力

全ての操作を終えた後の A の各要素を空白区切りで出力せよ。

入力例 1

5
ooxoo

出力例 1

5 2 1 3 4

A は各操作で以下のように変化します：

  • k=1 のとき：A の先頭 1 項を反転する。A=(1,2,3,4,5) になる。
  • k=2 のとき：A の先頭 2 項を反転する。A=(2,1,3,4,5) になる。
  • k=3 のとき：何もしない。
  • k=4 のとき：A の先頭 4 項を反転する。A=(4,3,1,2,5) になる。
  • k=5 のとき：A の先頭 5 項を反転する。A=(5,2,1,3,4) になる。

全ての操作を終えた後の A は A=(5,2,1,3,4) です。

入力例 2

7
ooooooo

出力例 2

7 5 3 1 2 4 6

入力例 3

15
xooxoxoxoxoxxoo

出力例 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14

Score : 300 points

Problem Statement

You are given an integer N and a string S of length N consisting of o and x.

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. Initially, A=(1,2,\ldots,N).

Perform the following operation on A for k=1,2,\ldots,N in this order.

  • If S_k= o, reverse the first k terms of A. Specifically, replace A with (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N).
  • If S_k= x, do nothing.

Find A after all the operations are completed.

Constraints

  • 2\le N\le 5\times 10^5
  • N is an integer.
  • S is a string of length N consisting of o and x.

Input

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

N
S

Output

Output the elements of A after all the operations are completed, separated by spaces.

Sample Input 1

5
ooxoo

Sample Output 1

5 2 1 3 4

A changes as follows with each operation:

  • For k=1: reverse the first 1 term of A. A becomes (1,2,3,4,5).
  • For k=2: reverse the first 2 terms of A. A becomes (2,1,3,4,5).
  • For k=3: do nothing.
  • For k=4: reverse the first 4 terms of A. A becomes (4,3,1,2,5).
  • For k=5: reverse the first 5 terms of A. A becomes (5,2,1,3,4).

After all the operations are completed, A is A=(5,2,1,3,4).

Sample Input 2

7
ooooooo

Sample Output 2

7 5 3 1 2 4 6

Sample Input 3

15
xooxoxoxoxoxxoo

Sample Output 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14