AtCoder Beginner Contest 196

A - Difference Max

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

整数 a, b, c, d が与えられます。
a ≤ x ≤ b,\ c ≤ y ≤ d となるように整数 x, y を選ぶとき、 x - y の最大値を求めてください。

制約

入力は全て整数
-100 ≤ a ≤ b ≤ 100
-100 ≤ c ≤ d ≤ 100

入力

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

a b
c d

出力

答えを出力せよ。

入力例 1

0 10
0 10

出力例 1

(x, y) = (10, 0) のとき最大値 x - y = 10 をとります。

入力例 2

-100 -100
100 100

出力例 2

-200

入力例 3

-100 100
-100 100

出力例 3

Score : 100 points

Problem Statement

Given are integers a, b, c, and d.
We will choose integers x and y such that a ≤ x ≤ b and c ≤ y ≤ d. Find the maximum possible value of x - y here.

Constraints

All values in input are integers.
-100 ≤ a ≤ b ≤ 100
-100 ≤ c ≤ d ≤ 100

Input

Input is given from Standard Input in the following format:

a b
c d

Output

Print the answer.

Sample Input 1

0 10
0 10

Sample Output 1

(x, y) = (10, 0) achieves the maximum value x - y = 10.

Sample Input 2

-100 -100
100 100

Sample Output 2

-200

Sample Input 3

-100 100
-100 100

Sample Output 3

B - Round Down

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

整数または小数 X が与えられるので、小数点以下を切り捨てて整数で出力してください。

制約

0 \le X \le 10^{100}
X は整数、または小数点以下が 100 桁以下の小数であり、先頭に余計な 0 は付かない

入力

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

出力

X を、小数点以下を切り捨てて整数の形式で出力せよ。

入力例 1

5.90

出力例 1

5.90 の小数点以下を切り捨てた 5 を整数で出力します。整数の形式でない 5.0 などは不正解になります。

入力例 2

出力例 2

X は小数点を含まないかもしれません。

入力例 3

84939825309432908832902189.9092309409809091329

出力例 3

84939825309432908832902189

大きい数の扱いに注意してください。

Score : 200 points

Problem Statement

Given an integer or a decimal X, round it down to an integer and print the result.

Constraints

0 \le X \le 10^{100}
X is an integer or a decimal with at most 100 digits after the decimal point, without unnecessary leading zeros.

Input

Input is given from Standard Input in the following format:

Output

Round X down to an integer and print the result (as an integer).

Sample Input 1

5.90

Sample Output 1

We round down 5.90 to an integer, 5, and print it as an integer. Non-integer outputs such as 5.0 will be judged as incorrect.

Sample Input 2

Sample Output 2

There may be no decimal point in X.

Sample Input 3

84939825309432908832902189.9092309409809091329

Sample Output 3

84939825309432908832902189

Take care when handling large numbers.

C - Doubled

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

整数 N が与えられます。
以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか？

x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。

制約

N は整数
1 ≤ N < 10^{12}

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

11, 22, 33 の 3 個が条件を満たします。

入力例 2

出力例 2

例えば 1313 は、十進表記が 4 桁で、その前半も後半も 13 であるため条件を満たします。

入力例 3

10000000

出力例 3

Score : 300 points

Problem Statement

Given is an integer N.
How many integers x between 1 and N (inclusive) satisfy the following condition?

The decimal representation (without leading zeros) of x has an even number of digits, and its first and second halves are equal as strings.

Constraints

N is an integer.
1 ≤ N < 10^{12}

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

Three numbers 11, 22, and 33 satisfy the condition.

Sample Input 2

Sample Output 2

For example, the decimal representation of 1313 has four digits, and its first and second halves are both 13, so 1313 satisfies the condition.

Sample Input 3

10000000

Sample Output 3

D - Hanjo

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

縦 H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1 メートルの区別できない畳 (長方形のタイル) A 枚と、1 メートル × 1 メートルの区別できない半畳 (正方形のタイル) B 枚を敷き詰めます。 2 メートル × 1 メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか？
なお、2A + B = HW であることが保証されます。また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

入力は全て整数
1 ≤ H, W
HW ≤ 16
0 ≤ A, B
2A + B = HW

入力

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

H W A B

出力

答えを出力せよ。

入力例 1

2 2 1 2

出力例 1

以下の 4 つです。

入力例 2

3 3 4 1

出力例 2

以下の 6 つと、これらを回転させたものが含まれます。

入力例 3

4 4 8 0

出力例 3

Score : 400 points

Problem Statement

We have a rectangular room that is H meters long and W meters wide.
We will cover this room with A indistinguishable 2 meters \times 1 meters rectangular tatami mats and B indistinguishable 1 meter \times 1 meter square tatami mats. The rectangular mats can be used in either direction: they can be 2 meters long and 1 meter wide, or 1 meter long and 2 meters wide.
How many ways are there to do this?
Here, it is guaranteed that 2A + B = HW, and two ways are distinguished if they match only after rotation, reflection, or both.

Constraints

All values in input are integers.
1 ≤ H, W
HW ≤ 16
0 ≤ A, B
2A + B = HW

Input

Input is given from Standard Input in the following format:

H W A B

Output

Print the answer.

Sample Input 1

2 2 1 2

Sample Output 1

There are four ways as follows:

Sample Input 2

3 3 4 1

Sample Output 2

There are six ways as follows, and their rotations.

Sample Input 3

4 4 8 0

Sample Output 3

E - Filters

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数列 A = (a_1, a_2, \dots, a_N), T = (t_1, t_2, \dots, t_N), X = (x_1, x_2, \dots, x_Q) が与えられます。
N 個の関数 f_1(x), f_2(x), \dots, f_N(x) を、

f_i(x) = \begin{cases} x + a_i & (t_i = 1)\\ \max(x, a_i) & (t_i = 2)\\ \min(x, a_i) & (t_i = 3)\\ \end{cases}

と定義します。

i = 1, 2, \dots, Q のそれぞれについて、 f_N( \dots f_2(f_1(x_i)) \dots ) を求めてください。

制約

入力は全て整数
1 ≤ N ≤ 2 \times 10^5
1 ≤ Q ≤ 2 \times 10^5
|a_i| ≤ 10^9
1 ≤ t_i ≤ 3
|x_i| ≤ 10^9

入力

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

N
a_1 t_1
a_2 t_2
\vdots
a_N t_N
Q
x_1 x_2 \cdots x_Q

出力

Q 行にかけて出力せよ。 i 行目には、 f_N( \dots f_2(f_1(x_i)) \dots ) を出力せよ。

入力例 1

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

出力例 1

f_1(x) = \max(x, -10), f_2(x) = x + 10, f_3(x) = \min(x, 10) です。
したがって、

f_3(f_2(f_1(-15))) = 0
f_3(f_2(f_1(-10))) = 0
f_3(f_2(f_1(-5))) = 5
f_3(f_2(f_1(0))) = 10
f_3(f_2(f_1(5))) = 10

となります。

Score : 500 points

Problem Statement

Given are integer sequences A = (a_1, a_2, \dots, a_N), T = (t_1, t_2, \dots, t_N), and X = (x_1, x_2, \dots, x_Q).
Let us define N functions f_1(x), f_2(x), \dots, f_N(x) as follows:

f_i(x) = \begin{cases} x + a_i & (t_i = 1)\\ \max(x, a_i) & (t_i = 2)\\ \min(x, a_i) & (t_i = 3)\\ \end{cases}

For each i = 1, 2, \dots, Q, find f_N( \dots f_2(f_1(x_i)) \dots ).

Constraints

All values in input are integers.
1 ≤ N ≤ 2 \times 10^5
1 ≤ Q ≤ 2 \times 10^5
|a_i| ≤ 10^9
1 ≤ t_i ≤ 3
|x_i| ≤ 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 t_1
a_2 t_2
\vdots
a_N t_N
Q
x_1 x_2 \cdots x_Q

Output

Print Q lines. The i-th line should contain f_N( \dots f_2(f_1(x_i)) \dots ).

Sample Input 1

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

Sample Output 1

We have f_1(x) = \max(x, -10), f_2(x) = x + 10, f_3(x) = \min(x, 10), thus:

f_3(f_2(f_1(-15))) = 0
f_3(f_2(f_1(-10))) = 0
f_3(f_2(f_1(-5))) = 5
f_3(f_2(f_1(0))) = 10
f_3(f_2(f_1(5))) = 10

F - Substring 2

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

0, 1 からなる文字列 S, T が与えられます。
T が S の部分文字列となるように、T のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？

部分文字列とは？

S のある連続した部分を取り出してできる文字列が T と一致するとき、T は S の部分文字列であるといいます。例えば、000 は 10001 の部分文字列ですが、11 は 10001 の部分文字列ではありません。

制約

S, T は 0, 1 からなる
1 ≤ |T| ≤ |S| ≤ 10^6

入力

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

S
T

出力

答えを出力せよ。

入力例 1

0001
101

出力例 1

T を 001 と書き換えると、S の 2 文字目から 4 文字目が T と一致します。

入力例 2

0101010
1010101

出力例 2

入力例 3

10101000010011011110
0010011111

出力例 3

Score : 600 points

Problem Statement

Given are strings S and T consisting of 0 and 1.
We will change some of the characters in T so that T becomes a substring of S.
How many characters do we need to change at least?

What is a substring?

T is said to be a substring of S when some contiguous part of S matches T. For example, 000 is a substring of 10001, while 11 is not.

Constraints

Each of S and T consists of 0 and 1.
1 ≤ |T| ≤ |S| ≤ 10^6

Input

Input is given from Standard Input in the following format:

S
T

Output

Print the answer.

Sample Input 1

0001
101

Sample Output 1

Changing T to 001 makes it match the 2-nd through 4-th characters of S.

Sample Input 2

0101010
1010101

Sample Output 2

Sample Input 3

10101000010011011110
0010011111