AtCoder Beginner Contest 048

A - AtCoder *** Contest

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 100 点

問題文

すぬけ君は、AtCoder s Contest という名前のコンテストを開こうとしています。ここで、s は長さ 1 以上の文字列であり、1 文字目は英大文字、2 文字目以降は英小文字です。

すぬけ君は、このコンテストの略称を AxC に決めました。ここで、x は s の先頭の英大文字です。

コンテストの名前が与えられるので、コンテストの略称を出力してください。

制約

s の長さは 1 以上 100 以下である。
s の 1 文字目は英大文字である。
s の 2 文字目以降は英小文字である。

入力

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

AtCoder s Contest

出力

コンテストの略称を出力せよ。

入力例 1

AtCoder Beginner Contest

出力例 1

ABC

今あなたが参加しているコンテストです。

入力例 2

AtCoder Snuke Contest

出力例 2

ASC

このコンテストは存在しません。

入力例 3

AtCoder X Contest

出力例 3

AXC

Score : 100 points

Problem Statement

Snuke is going to open a contest named "AtCoder s Contest". Here, s is a string of length 1 or greater, where the first character is an uppercase English letter, and the second and subsequent characters are lowercase English letters.

Snuke has decided to abbreviate the name of the contest as "AxC". Here, x is the uppercase English letter at the beginning of s.

Given the name of the contest, print the abbreviation of the name.

Constraints

The length of s is between 1 and 100, inclusive.
The first character in s is an uppercase English letter.
The second and subsequent characters in s are lowercase English letters.

Input

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

AtCoder s Contest

Output

Print the abbreviation of the name of the contest.

Sample Input 1

AtCoder Beginner Contest

Sample Output 1

ABC

The contest in which you are participating now.

Sample Input 2

AtCoder Snuke Contest

Sample Output 2

ASC

This contest does not actually exist.

Sample Input 3

AtCoder X Contest

Sample Output 3

AXC

B - Between a and b ...

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 200 点

問題文

非負の整数 a, b (a ≤ b) と、正の整数 x が与えられます。 a 以上 b 以下の整数のうち、x で割り切れるものの個数を求めてください。

制約

0 ≤ a ≤ b ≤ 10^{18}
1 ≤ x ≤ 10^{18}

入力

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

a b x

出力

a 以上 b 以下の整数のうち、x で割り切れるものの個数を出力せよ。

入力例 1

4 8 2

出力例 1

4 以上 8 以下の整数のうち 2 で割り切れるものは、4, 6, 8 です。

入力例 2

0 5 1

出力例 2

0 以上 5 以下の整数のうち 1 で割り切れるものは、0, 1, 2, 3, 4, 5 です。

入力例 3

9 9 2

出力例 3

9 以上 9 以下の整数のうち 2 で割り切れるものはありません。

入力例 4

1 1000000000000000000 3

出力例 4

333333333333333333

オーバーフローに注意してください。

Score : 200 points

Problem Statement

You are given nonnegative integers a and b (a ≤ b), and a positive integer x. Among the integers between a and b, inclusive, how many are divisible by x?

Constraints

0 ≤ a ≤ b ≤ 10^{18}
1 ≤ x ≤ 10^{18}

Input

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

a b x

Output

Print the number of the integers between a and b, inclusive, that are divisible by x.

Sample Input 1

4 8 2

Sample Output 1

There are three integers between 4 and 8, inclusive, that are divisible by 2: 4, 6 and 8.

Sample Input 2

0 5 1

Sample Output 2

There are six integers between 0 and 5, inclusive, that are divisible by 1: 0, 1, 2, 3, 4 and 5.

Sample Input 3

9 9 2

Sample Output 3

There are no integer between 9 and 9, inclusive, that is divisible by 2.

Sample Input 4

1 1000000000000000000 3

Sample Output 4

333333333333333333

Watch out for integer overflows.

C - Boxes and Candies

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

N 個の箱が横一列に並んでいます。最初、左から i 番目の箱には a_i 個のキャンディが入っています。

すぬけ君は次の操作を好きな回数だけ行うことができます。

キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べる。

すぬけ君の目標は次の通りです。

どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

制約

2 ≤ N ≤ 10^5
0 ≤ a_i ≤ 10^9
0 ≤ x ≤ 10^9

入力

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

N x
a_1 a_2 ... a_N

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

入力例 1

3 3
2 2 2

出力例 1

2 番目の箱のキャンディを 1 個食べればよいです。すると、各箱のキャンディの個数は (2, 1, 2) となります。

入力例 2

6 1
1 6 1 2 0 4

出力例 2

たとえば、2 番目の箱のキャンディを 6 個食べ、4 番目の箱のキャンディを 2 個食べ、6 番目の箱のキャンディを 3 個食べればよいです。

すると、各箱キャンディの個数は (1, 0, 1, 0, 0, 1) となります。

入力例 3

5 9
3 1 4 1 5

出力例 3

最初から目標が達成されているので、操作を行う必要はありません。

入力例 4

2 0
5 5

出力例 4

すべてのキャンディを食べなければなりません。

Score : 300 points

Problem Statement

There are N boxes arranged in a row. Initially, the i-th box from the left contains a_i candies.

Snuke can perform the following operation any number of times:

Choose a box containing at least one candy, and eat one of the candies in the chosen box.

His objective is as follows:

Any two neighboring boxes contain at most x candies in total.

Find the minimum number of operations required to achieve the objective.

Constraints

2 ≤ N ≤ 10^5
0 ≤ a_i ≤ 10^9
0 ≤ x ≤ 10^9

Input

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

N x
a_1 a_2 ... a_N

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3 3
2 2 2

Sample Output 1

Eat one candy in the second box. Then, the number of candies in each box becomes (2, 1, 2).

Sample Input 2

6 1
1 6 1 2 0 4

Sample Output 2

For example, eat six candies in the second box, two in the fourth box, and three in the sixth box. Then, the number of candies in each box becomes (1, 0, 1, 0, 0, 1).

Sample Input 3

5 9
3 1 4 1 5

Sample Output 3

The objective is already achieved without performing operations.

Sample Input 4

2 0
5 5

Sample Output 4

All the candies need to be eaten.

D - An Ordinary Game

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 500 点

問題文

長さ 3 以上の文字列 s があります。 s の中に同一の文字が隣り合う箇所はありません。

高橋君と青木君がゲームで勝負します。二人は交互に次の操作を行います。高橋君が先手です。

s から両端以外の文字をひとつ取り除く。ただし、その文字を取り除くことで、s の中に同一の文字が隣り合う箇所ができる場合、その文字を取り除くことはできない。

先に操作を行えなくなった人が負けです。二人が最適に行動したとき、どちらが勝つかを判定してください。

制約

3 ≤ |s| ≤ 10^5
s は英小文字のみからなる。
s の中に同一の文字が隣り合う箇所はない。

入力

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

出力

先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。

入力例 1

aba

出力例 1

Second

先手の高橋君は操作を行うことができません。なぜならば、s から両端以外の文字の b を取り除くと、s は aa となって a が隣り合うからです。

入力例 2

abc

出力例 2

First

先手の高橋君が s から b を取り除くと、s は ac となります。すると、後手の青木君は操作を行うことができません。なぜならば、s には両端以外の文字が存在しないからです。

入力例 3

abcab

出力例 3

First

Score : 500 points

Problem Statement

There is a string s of length 3 or greater. No two neighboring characters in s are equal.

Takahashi and Aoki will play a game against each other. The two players alternately performs the following operation, Takahashi going first:

Remove one of the characters in s, excluding both ends. However, a character cannot be removed if removal of the character would result in two neighboring equal characters in s.

The player who becomes unable to perform the operation, loses the game. Determine which player will win when the two play optimally.

Constraints

3 ≤ |s| ≤ 10^5
s consists of lowercase English letters.
No two neighboring characters in s are equal.

Input

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

Output

If Takahashi will win, print First. If Aoki will win, print Second.

Sample Input 1

aba

Sample Output 1

Second

Takahashi, who goes first, cannot perform the operation, since removal of the b, which is the only character not at either ends of s, would result in s becoming aa, with two as neighboring.

Sample Input 2

abc

Sample Output 2

First

When Takahashi removes b from s, it becomes ac. Then, Aoki cannot perform the operation, since there is no character in s, excluding both ends.

Sample Input 3

abcab

Sample Output 3

First