AtCoder Beginner Contest 072

A - Sandglass2

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 100 点

問題文

X 秒を測れる砂時計があります。はじめ上のパーツに砂が X [g] あり、1 秒間に 1 [g] 砂が落ちます。なお、上のパーツにもう砂が残っていない場合は砂は落ちません。

t 秒後に上のパーツに残っている砂は何gでしょう。

制約

1≤X≤10^9
1≤t≤10^9
X,t は整数

入力

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

X t

出力

t 秒後に上のパーツに残っている砂は何gかを出力せよ。

入力例 1

100 17

出力例 1

100 [g] の砂のうち 17 [g] が落ちるので、83 [g] になります。

入力例 2

48 58

出力例 2

48 [g] の砂は全て落ちきるので、0 [g] になります。

入力例 3

1000000000 1000000000

出力例 3

Score : 100 points

Problem Statement

We have a sandglass that runs for X seconds. The sand drops from the upper bulb at a rate of 1 gram per second. That is, the upper bulb initially contains X grams of sand.

How many grams of sand will the upper bulb contains after t seconds?

Constraints

1≤X≤10^9
1≤t≤10^9
X and t are integers.

Input

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

X t

Output

Print the number of sand in the upper bulb after t second.

Sample Input 1

100 17

Sample Output 1

17 out of the initial 100 grams of sand will be consumed, resulting in 83 grams.

Sample Input 2

48 58

Sample Output 2

All 48 grams of sand will be gone, resulting in 0 grams.

Sample Input 3

1000000000 1000000000

Sample Output 3

B - OddString

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 200 点

問題文

英小文字からなる文字列 s が与えられます。前から数えて奇数文字目だけ抜き出して作った文字列を出力してください。ただし、文字列の先頭の文字を1文字目とします。

制約

s の各文字は英小文字
1≤|s|≤10^5

入力

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

出力

前から数えて奇数文字目だけ抜き出して作った文字列を出力せよ。

入力例 1

atcoder

出力例 1

acdr

1 文字目の a, 3 文字目の c, 5 文字目の d, 7 文字目の r を取り出して acdr となります。

入力例 2

aaaa

出力例 2

aa

入力例 3

出力例 3

入力例 4

fukuokayamaguchi

出力例 4

fkoaaauh

Score : 200 points

Problem Statement

You are given a string s consisting of lowercase English letters. Extract all the characters in the odd-indexed positions and print the string obtained by concatenating them. Here, the leftmost character is assigned the index 1.

Constraints

Each character in s is a lowercase English letter.
1≤|s|≤10^5

Input

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

Output

Print the string obtained by concatenating all the characters in the odd-numbered positions.

Sample Input 1

atcoder

Sample Output 1

acdr

Extract the first character a, the third character c, the fifth character d and the seventh character r to obtain acdr.

Sample Input 2

aaaa

Sample Output 2

aa

Sample Input 3

Sample Output 3

Sample Input 4

fukuokayamaguchi

Sample Output 4

fkoaaauh

C - Together

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

長さ N の整数列 a_1,a_2,...,a_N が与えられます。

各 1≤i≤N に対し、a_i に 1 足すか、1 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。

この操作の後、ある整数 X を選んで、a_i=X となる i の個数を数えます。

うまく操作を行い、X を選ぶことで、この個数を最大化してください。

制約

1≤N≤10^5
0≤a_i<10^5 (1≤i≤N)
a_i は整数

入力

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

N
a_1 a_2 .. a_N

出力

うまく操作を行い、X を選んだ時の a_i=X なる i の個数の最大値を出力せよ。

入力例 1

7
3 1 4 1 5 9 2

出力例 1

例えば操作後の数列を 2,2,3,2,6,9,2 とすることができて、X=2 とすると 4 を得ることができ、これが最大です。

入力例 2

10
0 1 2 3 4 5 6 7 8 9

出力例 2

入力例 3

1
99999

出力例 3

Score : 300 points

Problem Statement

You are given an integer sequence of length N, a_1,a_2,...,a_N.

For each 1≤i≤N, you have three choices: add 1 to a_i, subtract 1 from a_i or do nothing.

After these operations, you select an integer X and count the number of i such that a_i=X.

Maximize this count by making optimal choices.

Constraints

1≤N≤10^5
0≤a_i<10^5 (1≤i≤N)
a_i is an integer.

Input

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

N
a_1 a_2 .. a_N

Output

Print the maximum possible number of i such that a_i=X.

Sample Input 1

7
3 1 4 1 5 9 2

Sample Output 1

For example, turn the sequence into 2,2,3,2,6,9,2 and select X=2 to obtain 4, the maximum possible count.

Sample Input 2

10
0 1 2 3 4 5 6 7 8 9

Sample Output 2

Sample Input 3

1
99999

Sample Output 3

D - Derangement

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

1,2,..,N からなる順列 p_1,p_2,..,p_N が与えられます。次の操作を何回か (0回でもよい) 行うことが出来ます。

操作: 順列で隣り合う二つの数を選んでスワップする。

何回か操作を行って、任意の 1≤i≤N に対して p_i ≠ i となるようにしたいです。必要な操作の最小回数を求めてください。

制約

2≤N≤10^5
p_1,p_2,..,p_N は 1,2,..,N の順列である。

入力

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

N
p_1 p_2 .. p_N

出力

必要な操作の最小回数を出力せよ。

入力例 1

5
1 4 3 5 2

出力例 1

1 と 4 を入れ替え、その後 1 と 3 を入れ替えることで p は 4,3,1,5,2 となり、これは条件を満たします。これが最小回数なので、答えは 2 となります。

入力例 2

2
1 2

出力例 2

1 と 2 を入れ替えれば条件を満たします。

入力例 3

2
2 1

出力例 3

初めから条件を満たしています。

入力例 4

9
1 2 4 9 5 8 7 3 6

出力例 4

Score : 400 points

Problem Statement

You are given a permutation p_1,p_2,...,p_N consisting of 1,2,..,N. You can perform the following operation any number of times (possibly zero):

Operation: Swap two adjacent elements in the permutation.

You want to have p_i ≠ i for all 1≤i≤N. Find the minimum required number of operations to achieve this.

Constraints

2≤N≤10^5
p_1,p_2,..,p_N is a permutation of 1,2,..,N.

Input

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

N
p_1 p_2 .. p_N

Output

Print the minimum required number of operations

Sample Input 1

5
1 4 3 5 2

Sample Output 1

Swap 1 and 4, then swap 1 and 3. p is now 4,3,1,5,2 and satisfies the condition. This is the minimum possible number, so the answer is 2.

Sample Input 2

2
1 2

Sample Output 2

Swapping 1 and 2 satisfies the condition.

Sample Input 3

2
2 1

Sample Output 3

The condition is already satisfied initially.

Sample Input 4

9
1 2 4 9 5 8 7 3 6