A - Doors in the Center

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

以下の条件を全て満たす長さ N の文字列を求めてください。

  • 各文字は - または = である
  • 回文である
  • 文字列中に = は 1 個または 2 個含まれる。 2 個含まれる場合、それらの = は隣接している

なお、そのような文字列はちょうど 1 つ存在します。

制約

  • 1 \leq N \leq 100
  • N は整数である

入力

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

N

出力

答えを出力せよ。

入力例 1

4

出力例 1

-==-

入力例 2

7

出力例 2

---=---

Score : 100 points

Problem Statement

Find a length-N string that satisfies all of the following conditions:

  • Each character is - or =.
  • It is a palindrome.
  • It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

  • 1 \leq N \leq 100
  • N is an integer.

Input

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

N

Output

Print the answer.

Sample Input 1

4

Sample Output 1

-==-

Sample Input 2

7

Sample Output 2

---=---
B - Distinct Strings

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字のみからなる長さ 3 の文字列 S が与えられます。

S の各文字を並び替えて得られる文字列は、何種類ありますか？

制約

  • S は英小文字のみからなる長さ 3 の文字列

入力

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

S

出力

S の各文字を並び替えて得られる文字列の種類数を出力せよ。

入力例 1

aba

出力例 1

3

S= aba の各文字を並び替えて得られる文字列は、aab, aba, baa の 3 通りです。

入力例 2

ccc

出力例 2

1

S= ccc の各文字を並び替えて得られる文字列は、ccc の 1 通りのみです。

入力例 3

xyz

出力例 3

6

S= xyz の各文字を並び替えて得られる文字列は、xyz, xzy, yxz, yzx, zxy, zyx の 6 通りです。

Score : 100 points

Problem Statement

You are given a string S of length 3 consisting of lowercase English letters.

How many different strings can be obtained by permuting the characters in S?

Constraints

  • S is a string S of length 3 consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of different strings that can be obtained by permuting the characters in S.

Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.

Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.

Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.
C - Caesar Cipher

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

  • まず、非負整数 K を選ぶ。
  • その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

  • a の 1 個後ろの英小文字は b であり、
  • b の 1 個後ろの英小文字は c であり、
  • c の 1 個後ろの英小文字は d であり、
  • \cdots
  • y の 1 個後ろの英小文字は z であり、
  • z の 1 個後ろの英小文字は a です。

例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。

文字列 T が与えられます。 高橋君が上記の操作によって S を T に一致させることができるかを判定してください。

制約

  • S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
  • S の長さと T の長さは等しい

入力

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

S
T

出力

高橋君が S を T に一致させることができる場合は Yes と出力し、 できない場合は No と出力せよ。

入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

  • a は 8 個後ろの i に
  • b は 8 個後ろの j に
  • c は 8 個後ろの k に

それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。

入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。

入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。 よって、No と出力します。

入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと S と T が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

  • First, choose a non-negative integer K.
  • Then, shift each character of S to the right by K (see below).

Here,

  • a shifted to the right by 1 is b;
  • b shifted to the right by 1 is c;
  • c shifted to the right by 1 is d;
  • \cdots
  • y shifted to the right by 1 is z;
  • z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

  • Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
  • The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

  • a is shifted to the right by 8 and becomes i,
  • b is shifted to the right by 8 and becomes j,
  • c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

D - Piano 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。 このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。 演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。 なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

  • 1\leq N \leq 100
  • 1\leq A_i \leq 100
  • N,A_i は整数
  • S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

11

例えば以下のように演奏することができます。

  • 最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
  • 左手で鍵盤 3 を押す。
  • 右手で鍵盤 6 を押す。
  • 左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
  • 右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
  • 左手で鍵盤 9 を押す。
  • 右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

3
2 L
2 L
100 L

出力例 2

98

入力例 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

出力例 3

188

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • N and A_i are integers.
  • S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

  • Initially, place the left hand on key 3 and the right hand on key 6.
  • Press key 3 with the left hand.
  • Press key 6 with the right hand.
  • Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
  • Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
  • Press key 9 with the left hand.
  • Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188
E - Gap Existence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。

制約

  • 2 \leq N \leq 2\times 10^5
  • -10^9 \leq A_i \leq 10^9
  • -10^9 \leq X \leq 10^9
  • 入力は全て整数である

入力

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

N X
A_1 \ldots A_N

出力

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。

入力例 1

6 5
3 1 4 1 5 9

出力例 1

Yes

A_6-A_3=9-4=5 です。

入力例 2

6 -4
-2 -7 -1 -8 -2 -8

出力例 2

No

A_i-A_j=-4 となる組 (i,j) は存在しません。

入力例 3

2 0
141421356 17320508

出力例 3

Yes

A_1-A_1=0 です。

Score : 300 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • -10^9 \leq A_i \leq 10^9
  • -10^9 \leq X \leq 10^9
  • All values in the input are integers.

Input

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

N X
A_1 \ldots A_N

Output

Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.