A - ab

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

配点 : 100 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。
S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力してください。(a と b の順序は問いません。)

制約

  • 2 \leq N \leq 100
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

S の中で a と b が隣接する箇所があれば Yes を、なければ No を出力せよ。

入力例 1

3
abc

出力例 1

Yes

文字列 abc は 1 文字目にある a と 2 文字目にある b が隣接しています。よって Yes を出力してください。

入力例 2

2
ba

出力例 2

Yes

文字列 ba は 2 文字目にある a と 1 文字目にある b が隣接しています。(a と b の順番は逆でも良い点に注意してください。)

入力例 3

7
atcoder

出力例 3

No

Score : 100 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No. (The order of a and b does not matter.)

Constraints

  • 2 \leq N \leq 100
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

If there are any adjacent occurrences of a and b in S, print Yes; otherwise, print No.

Sample Input 1

3
abc

Sample Output 1

Yes

The string abc has a as the first character and b as the second character, which are adjacent. Thus, print Yes.

Sample Input 2

2
ba

Sample Output 2

Yes

The string ba has a as the second character and b as the first character, which are adjacent. (Note that the order of a and b does not matter.)

Sample Input 3

7
atcoder

Sample Output 3

No
B - Not Too Hard

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

配点 : 100 点

問題文

N 問の問題が出題されるプログラミングコンテストがあります。 i = 1, 2, \ldots, N について、i 問目の配点は S_i です。

配点が X 以下である問題すべての配点の合計を出力してください。

制約

  • 入力される値は全て整数
  • 4 \leq N \leq 8
  • 100 \leq S_i \leq 675
  • 100 \leq X \leq 675

入力

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

N X
S_1 S_2 \ldots S_N

出力

答えを出力せよ。

入力例 1

6 200
100 675 201 200 199 328

出力例 1

499

配点が 200 以下である問題は、1, 4, 5 問目の全 3 問であり、それらの配点の合計は S_1 + S_4 + S_5 = 100 + 200 + 199 = 499 です。

入力例 2

8 675
675 675 675 675 675 675 675 675

出力例 2

5400

入力例 3

8 674
675 675 675 675 675 675 675 675

出力例 3

0

Score : 100 points

Problem Statement

There is a programming contest with N problems. For each i = 1, 2, \ldots, N, the score for the i-th problem is S_i.

Print the total score for all problems with a score of X or less.

Constraints

  • All input values are integers.
  • 4 \leq N \leq 8
  • 100 \leq S_i \leq 675
  • 100 \leq X \leq 675

Input

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

N X
S_1 S_2 \ldots S_N

Output

Print the answer.

Sample Input 1

6 200
100 675 201 200 199 328

Sample Output 1

499

Three problems have a score of 200 or less: the first, fourth, and fifth, for a total score of S_1 + S_4 + S_5 = 100 + 200 + 199 = 499.

Sample Input 2

8 675
675 675 675 675 675 675 675 675

Sample Output 2

5400

Sample Input 3

8 674
675 675 675 675 675 675 675 675

Sample Output 3

0
C - Prefix?

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

配点 : 200 点

問題文

英小文字のみからなる 2 つの文字列 S, T が与えられます。 S が T の接頭辞かどうかを判定してください。

接頭辞とは 長さ N の文字列 T_1T_2\ldots T_N の接頭辞とは、 0 \leq i \leq N を満たすある整数 i によって、T の先頭 i 文字目までの文字列 T_1T_2\ldots T_i として表される文字列です。例えば、T = abc のとき、T の接頭辞は、空文字列、a 、ab 、abc の 4 つです。

制約

  • S と T はそれぞれ英小文字のみからなる長さが 1 以上 100 以下の文字列

入力

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

S
T

出力

S が T の接頭辞である場合は Yes を、そうでない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

atco
atcoder

出力例 1

Yes

atco は atcoder の接頭辞です。よって、Yes を出力します。

入力例 2

code
atcoder

出力例 2

No

code は atcoder の接頭辞ではありません。よって、No を出力します。

入力例 3

abc
abc

出力例 3

Yes

文字列全体もその文字列の接頭辞であることに注意してください。

入力例 4

aaaa
aa

出力例 4

No

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

What is a prefix? A prefix of a string T_1T_2\ldots T_N of length N is a string expressed as the first i characters of T, T_1T_2\ldots T_i, where i is an integer such that 0 \leq i \leq N. For example, when T = abc, there are four prefixes of T: an empty string, a, ab, and abc.

Constraints

  • S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

Print Yes if S is a prefix of T; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No
D - Foreign Exchange

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

配点 : 150 点

問題文

1 から N までの番号がつけられた N 個の国があり、i = 1, 2, \ldots, N について、高橋君は国 i の通貨を A_i 単位持っています。

高橋君は、下記の操作を好きな回数（ 0 回でも良い）繰り返します。

  • まず、1 以上 N-1 以下の整数 i を選ぶ。
  • その後、国 i の通貨を S_i 単位以上持っているなら、下記の行動を 1 回行う。
    • 国 i の通貨を S_i 単位だけ支払い、国 (i+1) の通貨を T_i 単位だけ獲得する。

最終的に高橋君が持っている国 N の通貨の単位数としてあり得る最大値を出力してください。

制約

  • 入力される値はすべて整数
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq S_i \leq 10^9

入力

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

出力

答えを出力せよ。

入力例 1

4
5 7 0 3
2 2
4 3
5 2

出力例 1

5

以下の説明では、高橋君が持っている各国の通貨の単位数を、数列 A = (A_1, A_2, A_3, A_4) として表します。はじめ、A = (5, 7, 0, 3) です。

下記の通りに 4 回操作を行うことを考えます。

  • i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (5, 3, 3, 3) となる。
  • i = 1 を選び、国 1 の通貨 2 単位を支払って、国 2 の通貨 2 単位を獲得する。その結果、A = (3, 5, 3, 3) となる。
  • i = 2 を選び、国 2 の通貨 4 単位を支払って、国 3 の通貨 3 単位を獲得する。その結果、A = (3, 1, 6, 3) となる。
  • i = 3 を選び、国 3 の通貨 5 単位を支払って、国 4 の通貨 2 単位を獲得する。その結果、A = (3, 1, 1, 5) となる。

このとき、最終的に高橋君が持っている国 4 の通貨の単位数は 5 であり、これが考えられる最大値です。

入力例 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

出力例 2

45

Score: 150 points

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

  • First, choose an integer i between 1 and N-1, inclusive.
  • Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
    • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

  • All input values are integers.
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq S_i \leq 10^9

Input

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

N
A_1 A_2 \ldots A_N
S_1 T_1
S_2 T_2
\vdots
S_{N-1} T_{N-1}

Output

Print the answer.

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

  • Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
  • Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
  • Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
  • Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45
E - Gap Existence

実行時間制限: 2 sec / メモリ制限: 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.