AtCoder Daily Training EASY 2026/01/21 18:00start

A - Scary Fee

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

あなたはコワスギ銀行の通帳を持っています。コワスギ銀行の預金通帳には、引き出し額に応じて手数料が変わるという怖すぎる性質があります。

コワスギ銀行の通帳からお金を引き出すには、1\,000 円単位で引き出し額を指定したうえで、引き出し額 1\,000 円あたり C 円の手数料を残高から別途支払う必要があります。銀行の残高が 0 円未満になる引き出しを行うことはできません。

あなたが持っているコワスギ銀行の通帳の残高が X 円のとき、そこから最大で何円を引き出せますか？

制約

1 \leq X \leq 10^7
1 \leq C \leq 999
入力される値はすべて整数

入力

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

X C

出力

答えを出力せよ。

入力例 1

650000 8

出力例 1

644\,000 円を引き出すために必要な手数料は 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 円になるので、644\,000 + 5\,152 \leq 650\,000 より、644\,000 円は引き出すことができます。

一方で、645\,000 円引き出すために必要な手数料は 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 円になるので、645\,000 + 5\,160 > 650\,000 より、645\,000 円は引き出すことができません。

入力例 2

1003 4

出力例 2

まったくお金が引き出せないこともありえます。

入力例 3

10000000 24

出力例 3

Score : 150 points

Problem Statement

You have a bankbook from The Terrifying Bank. The deposit passbook of the bank has a terrifyingly scary property that the commission fee changes according to the withdrawal amount.

To withdraw money from the passbook, you need to specify the withdrawal amount in units of 1\,000 yen, and pay a commission fee of C yen per 1\,000 yen of withdrawal amount separately from the balance. Withdrawals are not allowed if they would leave the balance below 0 yen.

When the balance of your passbook from the bank is X yen, what is the maximum amount of money you can withdraw from it?

Constraints

1 \leq X \leq 10^7
1 \leq C \leq 999
All input values are integers.

Input

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

X C

Output

Output the answer.

Sample Input 1

650000 8

Sample Output 1

The commission fee required to withdraw 644\,000 yen is 644\,000 \times \displaystyle\frac{8}{1000} = 5\,152 yen, so since 644\,000 + 5\,152 \leq 650\,000, you can withdraw 644\,000 yen.

On the other hand, the commission fee required to withdraw 645\,000 yen is 645\,000 \times \displaystyle\frac{8}{1000} = 5\,160 yen, so since 645\,000 + 5\,160 > 650\,000, you cannot withdraw 645\,000 yen.

Sample Input 2

1003 4

Sample Output 2

It is possible that no money can be withdrawn at all.

Sample Input 3

10000000 24

Sample Output 3

B - T-shirt

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

あるプログラミングコンテストでは、以下のルールに従って参加者に T シャツをプレゼントします。

上位 A 位までの参加者は、必ず T シャツが貰える。
加えて、上位 A+1 位から B 位までの参加者のうち C 人が一様ランダムに選ばれ、選ばれた参加者は T シャツを貰える。

コンテストには 1000 人が参加し、全ての参加者が相異なる順位を取りました。
このコンテストの参加者であるいろはちゃんは、X 位を取りました。
このとき、いろはちゃんが T シャツを貰える確率を求めてください。

制約

入力はすべて整数
1 \le A < B \le 1000
1 \le C \le B-A
1 \le X \le 1000

入力

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

A B C X

出力

答えを出力せよ。なお、想定解との絶対誤差または相対誤差が 10^{−6} 以下であれば、正解として扱われる。

入力例 1

30 500 20 103

出力例 1

0.042553191489

いろはちゃんは 103 位を取りました。
31 位から 500 位までの 470 人の参加者の中から 20 人が一様ランダムに選ばれ、ここで選ばれるといろはちゃんは T シャツを貰えます。この確率は \frac{20}{470}=0.04255319\dots です。

入力例 2

50 500 100 1

出力例 2

1.000000000000

いろはちゃんは 1 位を取りました。この入力において、いろはちゃんは確実に T シャツを貰えます。

入力例 3

1 2 1 1000

出力例 3

0.000000000000

いろはちゃんは 1000 位を取りました。この入力において、いろはちゃんが T シャツを貰えることはありません。

Score : 100 points

Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

All participants who ranked A-th or higher get a T-shirt.
Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

All values in input are integers.
1 \le A < B \le 1000
1 \le C \le B-A
1 \le X \le 1000

Input

Input is given from Standard Input in the following format:

A B C X

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{−6}.

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

C - Modulo Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

-10^{18} 以上 10^{18} 以下の整数 N が与えられます。

以下の条件を満たす 0 以上 998244353 未満の整数 x を求めてください。なお、答えが一意に定まることが証明できます。

N-x は 998244353 の倍数

制約

N は -10^{18} 以上 10^{18} 以下の整数

入力

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

出力

答えを出力せよ。

入力例 1

998244354

出力例 1

998244354-1 = 998244353 は 998244353 の倍数なので条件を満たします。

入力例 2

-9982443534

出力例 2

998244349

-9982443534-998244349= -10980687883 は 998244353 の倍数なので条件を満たします。

Score : 200 points

Problem Statement

You are given an integer N between -10^{18} and 10^{18} (inclusive).

Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.

N-x is a multiple of 998244353.

Constraints

N is an integer between -10^{18} and 10^{18} (inclusive).

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

998244354

Sample Output 1

998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.

Sample Input 2

-9982443534

Sample Output 2

998244349

-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.

D - Rotate

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 行 N 列のマス目が与えられます。上から i 行目、左から j 列目のマスには整数 A_{i,j} が書かれています。ここで、A_{i,j} は 0 か 1 であることが保証されます。

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目を出力してください。

ただし外側のマスとは、1 行目、N 行目、1 列目、N 列目のいずれか 1 つ以上に属するマスの集合のことを指します。

制約

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
入力は全て整数

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

マス目の外側のマスに書かれた整数を時計回りに 1 個ずつずらしたときのマス目において、上から i 行目、左から j 列目のマスに書かれている整数を B_{i,j} と置く。このとき、以下の形式で出力せよ。

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

入力例 1

出力例 1

上から i 行目、左から j 列目のマスを (i,j) と呼ぶこととします。

外側のマスは (1,1) から時計回りに列挙すると (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1),(2,1) の 12 個です。

これらのマスに書かれている整数を、時計回りに 1 個ずつ動かすと出力欄のようになります。

入力例 2

2
11
11

出力例 2

11
11

入力例 3

出力例 3

Score : 200 points

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

2 \le N \le 100
0 \le A_{i,j} \le 1(1 \le i,j \le N)
All input values are integers.

Input

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Let B_{i,j} be the integer written on the square at the i-th row from the top and j-th column from the left in the grid resulting from shifting the outer squares clockwise by one square each. Print them in the following format:

B_{1,1}B_{1,2}\dots B_{1,N}
B_{2,1}B_{2,2}\dots B_{2,N}
\vdots
B_{N,1}B_{N,2}\dots B_{N,N}

Sample Input 1

Sample Output 1

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

Sample Output 3

E - Make it Simple

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフから辺を取り除いてグラフを単純にするためには、少なくとも何本の辺を取り除く必要がありますか？
ここでグラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 5 \times 10^5
1 \leq u_i \leq N
1 \leq v_i \leq N
入力される値は全て整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

グラフを単純にするために取り除く必要がある辺の本数の最小値を出力せよ。

入力例 1

出力例 1

辺 3 と辺 5 を取り除くとグラフを単純にすることが出来て、これが取り除く辺の本数が最小となる選び方の 1 つです。よって答えは 2 本です。

入力例 2

1 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 5 \times 10^5
1 \leq u_i \leq N
1 \leq v_i \leq N
All input values are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the minimum number of edges that must be removed to make the graph simple.

Sample Input 1

Sample Output 1

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

Sample Input 3