AtCoder Daily Training EASY 2026/08/20 16:00start

A - Four Digits

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0 以上 9999 以下の整数 N が与えられます。

N の先頭に必要なだけ 0 をつけ、4 桁の文字列にしたものを出力してください。

制約

0 \leq N \leq 9999
N は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

321 は 3 桁なので、先頭に 1 つ 0 をつけると 4 桁になります。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 100 points

Problem Statement

You are given an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

0 \leq N \leq 9999
N is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

B - Sigma Cubes

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

正整数 N が与えられます。

i=1,2,\ldots,N について (-1)^i \times i^3 を計算したときの、それら N 個の値の総和を求めてください。

すなわち、 \displaystyle \sum_{i=1}^N (-1)^i \times i^3 を求めてください。

制約

N は 1 以上 10 以下の整数

入力

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

出力

\displaystyle \sum_{i=1}^N (-1)^i \times i^3 の値を出力せよ。

入力例 1

出力例 1

-20

i=1 のとき： (-1)^i\times i^3=-1 です。
i=2 のとき： (-1)^i\times i^3=8 です。
i=3 のとき： (-1)^i\times i^3=-27 です。

したがって、 -1 + 8 - 27 = -20 を出力してください。

入力例 2

出力例 2

-425

入力例 3

出力例 3

Score : 100 points

Problem Statement

You are given a positive integer N.

For i=1,2,\ldots,N, calculate (-1)^i \times i^3, and find the sum of these N values.

That is, find \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Constraints

N is an integer between 1 and 10, inclusive.

Input

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

Output

Output the value of \displaystyle \sum_{i=1}^N (-1)^i \times i^3.

Sample Input 1

Sample Output 1

-20

When i=1: (-1)^i\times i^3=-1.
When i=2: (-1)^i\times i^3=8.
When i=3: (-1)^i\times i^3=-27.

Therefore, output -1 + 8 - 27 = -20.

Sample Input 2

Sample Output 2

-425

Sample Input 3

Sample Output 3

C - log2(N)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 N が与えられるので、 2^k \le N となる最大の整数 k を求めてください。

制約

N は 1 \le N \le 10^{18} を満たす整数である

入力

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

出力

答えを整数として出力せよ。

入力例 1

出力例 1

k=2 は 2^2=4 \le 6 を満たします。
k \ge 3 である全ての整数 k について 2^k > 6 となります。

以上より、答えは k=2 となります。

入力例 2

出力例 2

2^0=1 であることに注意してください。

入力例 3

1000000000000000000

出力例 3

入力が 32 bit 整数に収まらない場合があります。

Score : 200 points

Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

N is an integer satisfying 1 \le N \le 10^{18}.

Input

Input is given from Standard Input in the following format:

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

k=2 satisfies 2^2=4 \le 6.
For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

Sample Output 2

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

The input value may not fit into a 32-bit integer.

D - P(X or Y)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

1,2,3,4,5,6 の 6 種類の目が出るサイコロを 2 つ振ったときに、次の 2 つの条件の少なくとも一方を満たす確率を求めてください。

2 つの出目の合計が X 以上である。
2 つの出目の差の絶対値が Y 以上である。

ここで、どちらのサイコロについても 6 種類のどの目が出るかは同様に確からしく、それぞれのサイコロの出目は独立であるとします。

制約

2\leq X\leq13
0\leq Y\leq6
入力はすべて整数

入力

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

X Y

出力

2 つのサイコロの出目が 2 つの条件の少なくとも一方を満たす確率を出力せよ。出力された値と真の値との絶対誤差が 10 ^ {-9} 以下のとき、正答と判定される。

入力例 1

9 3

出力例 1

0.555555555555555555555555555555

2 つのサイコロの出目がそれぞれ x と y であることを (x,y) で表すことにすると、それぞれの条件を満たすのは次の場合です。

2 つのサイコロの出目の和が 9 以上になるのは、(3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6) のとき
2 つのサイコロの出目の差が 3 以上になるのは、(1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3) のとき

これらの条件の少なくとも一方を満たすのは (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6) の 20 通りのいずれかのときです。

よって、求める答えは \dfrac{20}{36}=\dfrac59=0.5555555555\ldots です。

絶対誤差が 10 ^ {-9} 以下のとき正答と判定されるので、0.5555555565 や 0.55555555456789 などと出力しても正解となります。

入力例 2

13 6

出力例 2

2 つのサイコロの出目の和が 13 以上になることも、差が 6 以上になることもありません。

よって、求める答えは 0 です。

入力例 3

10 3

出力例 3

0.5

Score : 250 points

Problem Statement

Two dice, each with six faces 1,2,3,4,5,6, are rolled. Find the probability that at least one of the following two conditions holds:

The sum of the two outcomes is at least X.
The absolute difference of the two outcomes is at least Y.

Each face of each die is equally likely, and the two dice are independent.

Constraints

2 \le X \le 13
0 \le Y \le 6
All input values are integers.

Input

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

X Y

Output

Output the probability that the two outcomes satisfy at least one of the two conditions. Your answer is accepted if its absolute error from the true value is at most 10^{-9}.

Sample Input 1

9 3

Sample Output 1

0.555555555555555555555555555555

Let (x,y) denote the event that the dice show x and y.

The sum is at least 9 for (3,6),(4,5),(4,6),(5,4),(5,5),(5,6),(6,3),(6,4),(6,5),(6,6).
The difference is at least 3 for (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(5,1),(5,2),(6,1),(6,2),(6,3).

At least one of these conditions holds for the following 20 pairs: (1,4),(1,5),(1,6),(2,5),(2,6),(3,6),(4,1),(4,5),(4,6),(5,1),(5,2),(5,4),(5,5),(5,6),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6).

Thus, the answer is \dfrac{20}{36}=\dfrac59=0.5555555555\ldots.

Because an absolute error of at most 10^{-9} is allowed, outputs such as 0.5555555565 or 0.55555555456789 are accepted.

Sample Input 2

13 6

Sample Output 2

Neither the sum of two dice can be 13 or greater, nor can their difference be 6 or greater.

Thus, the answer is 0.

Sample Input 3

10 3

Sample Output 3

0.5

E - Minimum Glutton

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

N 個の料理があり、i 個目の料理の甘さは A_i、しょっぱさは B_i です。

高橋君はこれらの N 個の料理を好きな順番で並べ、その順に食べようとします。

高橋君は並べた順番の通りに料理を食べていきますが、食べた料理の甘さの合計が X より大きくなるかしょっぱさの合計が Y より大きくなるとその時点で食べるのをやめます。

高橋君が食べることになる料理の個数としてあり得る最小値を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq X, Y \leq 2 \times 10^{14}
1 \leq A_i, B_i \leq 10^9
入力される値はすべて整数

入力

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

N X Y
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

答えを出力せよ。

入力例 1

4 7 18
2 3 5 1
8 8 1 4

出力例 1

i 個目の料理のことを料理 i と書きます。

高橋君が 4 個の料理を料理 2, 3, 1, 4 の順に並べ替えたとき、料理 2, 3 を食べた時点での食べた料理の甘さの合計が 8 となり 7 より大きくなります。したがってこの場合は高橋君が食べることになる料理の個数は 2 個です。

高橋君が食べる料理の個数が 1 個以下になることはないため、2 を出力します。

入力例 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

出力例 2

入力例 3

8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1

出力例 3

Score : 250 points

Problem Statement

There are N dishes, and the i-th dish has a sweetness of A_i and a saltiness of B_i.

Takahashi plans to arrange these N dishes in any order he likes and eat them in that order.

He will eat the dishes in the arranged order, but he will stop eating as soon as the total sweetness of the dishes he has eaten exceeds X or the total saltiness exceeds Y.

Find the minimum possible number of dishes that he will end up eating.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq X, Y \leq 2 \times 10^{14}
1 \leq A_i, B_i \leq 10^9
All input values are integers.

Input

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

N X Y
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Print the answer.

Sample Input 1

4 7 18
2 3 5 1
8 8 1 4

Sample Output 1

The i-th dish will be denoted as dish i.

If he arranges the four dishes in the order 2, 3, 1, 4, as soon as he eats dishes 2 and 3, their total sweetness is 8, which is greater than 7. Therefore, in this case, he will end up eating two dishes.

The number of dishes he will eat cannot be 1 or less, so print 2.

Sample Input 2

5 200000000000000 200000000000000
1 1 1 1 1
2 2 2 2 2

Sample Output 2

Sample Input 3

8 30 30
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1