AtCoder Daily Training EASY 2024/11/14 16:30start

A - Election 2

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

AtCoder 市では市長選挙が行われています。候補者は高橋氏と青木氏です。

2 人のどちらかに投じられた有効票は N 票あり、現在開票が行われています。なお、 N は奇数です。

現在の開票作業の途中経過は高橋氏に T 票、青木氏に A 票です。

現時点で勝敗が確定しているかを判定してください。

制約

1 \leq N \leq 99
N は奇数
0 \leq T,A \leq N
T+A \leq N
入力はすべて整数

入力

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

N T A

出力

現時点で勝敗が確定しているならば Yes 、そうでなければ No と出力せよ。

入力例 1

7 4 2

出力例 1

Yes

残りの 1 票が青木氏に入っても、高橋氏は勝利します。高橋氏の勝利が確定しているため、Yes と出力します。

入力例 2

99 12 48

出力例 2

No

現時点では青木氏が多く票を獲得していますが、高橋氏が残りの 39 票を獲得すると高橋氏が勝利します。よって、No と出力します。

入力例 3

1 0 0

出力例 3

No

Score : 100 points

Problem Statement

A mayoral election is being held in AtCoder City. The candidates are Takahashi and Aoki.

There are N valid votes cast for either of the two candidates, and the counting is currently underway. Here, N is an odd number.

The current vote count is T votes for Takahashi and A votes for Aoki.

Determine if the outcome of the election is already decided at this point.

Constraints

1 \leq N \leq 99
N is an odd number.
0 \leq T, A \leq N
T + A \leq N
All input values are integers.

Input

The input is given from standard input in the following format:

N T A

Output

Print Yes if the outcome of the election is already decided, and No otherwise.

Sample Input 1

7 4 2

Sample Output 1

Yes

Even if the remaining one vote goes to Aoki, Takahashi will still win. That is, his victory is decided, so print Yes.

Sample Input 2

99 12 48

Sample Output 2

No

Although Aoki currently has more votes, Takahashi would win if he receives the remaining 39 votes. Therefore, print No.

Sample Input 3

1 0 0

Sample Output 3

No

B - Batting Average

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

高橋君は野球ゲームを作っています。
高橋君はバッターの打率を指定された桁数の分だけ表示するプログラムを作ることにしました。

整数 A, B があります。ここで A, B は 1 \leq A \leq 10, 0 \leq B \leq A を満たします。
このとき、文字列 S を次のように定義します。

\dfrac{B}{A} を小数点第 4 位で四捨五入した値を「整数部 1 桁」「 . 」「小数部 3 桁」の順に末尾ゼロを省略せずに表記した文字列。

例えば A=7, B = 4 の場合は、\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots で、これを小数点第 4 位で四捨五入した値は 0.571 です。よって S は 0.571 になります。

A, B が入力として与えられるので S を出力してください。

制約

1 \leq A \leq 10
0 \leq B \leq A
A, B は整数

入力

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

A B

出力

S を問題文の指示に従った形式で出力せよ。問題文の指示と異なる形式で出力した場合は誤答となることに注意せよ。

入力例 1

7 4

出力例 1

0.571

問題文本文でも説明した通り、\dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots で、これを小数点第 4 位で四捨五入した値は 0.571 です。よって S は 0.571 になります。

入力例 2

7 3

出力例 2

0.429

\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots で、これを小数点第 4 位で四捨五入した値は 0.429 です。(繰り上がりが発生するのに注意してください。)
よって S は 0.429 となります。

入力例 3

2 1

出力例 3

0.500

\dfrac{B}{A} = \dfrac{1}{2} = 0.5 で、これを小数点第 4 位で四捨五入した値も同様に 0.5 です。
よって S は 0.500 となります。小数部を 3 桁並べる必要があるのに注意してください。

入力例 4

10 10

出力例 4

1.000

入力例 5

1 0

出力例 5

0.000

Score : 100 points

Problem Statement

Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.

There are integers A and B, which satisfy 1 \leq A \leq 10 and 0 \leq B \leq A.
Let S be the string obtained as follows.

Round off \dfrac{B}{A} to three decimal digits, then write the integer part (1 digit), . (the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.

For example, if A=7 and B=4, then \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

You are given A and B as the input and asked to print S.

Constraints

1 \leq A \leq 10
0 \leq B \leq A
A and B are integers.

Input

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

A B

Output

Print S in the format specified in the Problem Statement. Note that answers in different formats will be considered wrong.

Sample Input 1

7 4

Sample Output 1

0.571

As explained in the Problem Statement, \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

Sample Input 2

7 3

Sample Output 2

0.429

\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots rounded off to three decimal digits is 0.429. (Note that it got rounded up.)
Thus, S is 0.429.

Sample Input 3

2 1

Sample Output 3

0.500

\dfrac{B}{A} = \dfrac{1}{2} = 0.5 rounded off to three decimal digits is again 0.5.
Thus, S is 0.500. Note that it must have three decimal places.

Sample Input 4

10 10

Sample Output 4

1.000

Sample Input 5

1 0

Sample Output 5

0.000

C - Binary Alchemy

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 種類の元素があり、元素には 1, 2, \ldots, N の番号が付けられています。

元素どうしは合成させることができ、元素 i と元素 j を合成すると i \geq j のとき元素 A_{i, j} に、i < j のとき元素 A_{j, i} に変化します。

元素 1 に対して元素 1, 2, \ldots, N をこの順に合成したとき、最終的に得られる元素を求めてください。

制約

1 \leq N \leq 100
1 \leq A_{i, j} \leq N
入力される値はすべて整数

入力

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

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

出力

最終的に得られる元素の番号を出力せよ。

入力例 1

出力例 1

元素 1 と元素 1 を合成すると、元素 3 が得られます。
元素 3 と元素 2 を合成すると、元素 1 が得られます。
元素 1 と元素 3 を合成すると、元素 3 が得られます。
元素 3 と元素 4 を合成すると、元素 2 が得られます。

したがって、出力するべき値は 2 です。

入力例 2

出力例 2

入力例 3

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

出力例 3

Score : 200 points

Problem Statement

There are N types of elements numbered 1, 2, \ldots, N.

Elements can be combined with each other. When elements i and j are combined, they transform into element A_{i, j} if i \geq j, and into element A_{j, i} if i < j.

Starting with element 1, combine it with elements 1, 2, \ldots, N in this order. Find the final element obtained.

Constraints

1 \leq N \leq 100
1 \leq A_{i, j} \leq N
All input values are integers.

Input

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

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

Output

Print the number representing the final element obtained.

Sample Input 1

Sample Output 1

Combining element 1 with element 1 results in element 3.
Combining element 3 with element 2 results in element 1.
Combining element 1 with element 3 results in element 3.
Combining element 3 with element 4 results in element 2.

Therefore, the value to be printed is 2.

Sample Input 2

Sample Output 2

Sample Input 3

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

Sample Output 3

D - Hit and Blow

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N) が与えられます。
A の要素はすべて異なります。B の要素もすべて異なります。

次の 2 つを出力してください。

A にも B にも含まれ、その位置も一致している整数の個数。言い換えると、A_i = B_i を満たす整数 i の個数。
A にも B にも含まれるが、その位置は異なる整数の個数。言い換えると、A_i = B_j, i \neq j を満たす整数の組 (i, j) の個数。

制約

1 \leq N \leq 1000
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
A_1, A_2, \dots, A_N はすべて異なる。
B_1, B_2, \dots, B_N はすべて異なる。
入力はすべて整数である。

入力

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

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

答えを 2 行出力せよ。1 行目には 1. の個数、2 行目には 2. の個数を出力せよ。

入力例 1

4
1 3 5 2
2 3 1 4

出力例 1

1
2

A にも B にも含まれ、その位置も一致している整数は A_2 = B_2 = 3 の 1 個です。
A にも B にも含まれるが、その位置は異なる整数は A_1 = B_3 = 1 と A_4 = B_1 = 2 の 2 個です。

入力例 2

3
1 2 3
4 5 6

出力例 2

0
0

1., 2. ともに条件を満たす整数は存在しません。

入力例 3

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

出力例 3

3
2

Score : 200 points

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

1 \leq N \leq 1000
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
A_1, A_2, \dots, A_N are all different.
B_1, B_2, \dots, B_N are all different.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the answers in two lines: the answer to1. in the first line, and the answer to2. in the second line.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

E - Distribution

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

N 人のすぬけ君が円周上に並んでおり、反時計回りに 1,2,...,N の番号がついています。

i\, (1 \leq i \leq N) 番目のすぬけ君は時刻 t に宝石をもらうと S_i 単位時間後、すなわち時刻 t+S_i にその宝石を (i+1) 番目のすぬけ君に渡します。ただし、(N+1) 番目のすぬけ君とは 1 番目のすぬけ君のことを指すとします。

また、高橋君は時刻 T_i に i 番目のすぬけ君に宝石を渡します。

全ての i\, (1 \leq i \leq N) について、i 番目のすぬけ君が初めて宝石をもらう時刻を求めてください。なお、宝石の受け渡しにかかる時間は無視できるものとします。

制約

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
入力は全て整数である。

入力

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

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

出力

N 行出力せよ。i\, (1 \leq i \leq N) 行目には、i 番目のすぬけ君が初めて宝石をもらう時刻を出力すること。

入力例 1

3
4 1 5
3 10 100

出力例 1

3
7
8

時刻 13 までのすぬけ君と高橋君の行動を時系列順に並べます。

時刻 3 : 高橋君が 1 番目のすぬけ君に宝石を渡します。

時刻 7 : 1 番目のすぬけ君が 2 番目のすぬけ君に宝石を渡します。

時刻 8 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 10 : 高橋君が 2 番目のすぬけ君に宝石を渡します。

時刻 11 : 2 番目のすぬけ君が 3 番目のすぬけ君に宝石を渡します。

時刻 13 : 3 番目のすぬけ君が 1 番目のすぬけ君に宝石を渡します。

時刻 14 以降も彼らは宝石の受け渡しを行いますが、答えには影響しません。

入力例 2

4
100 100 100 100
1 1 1 1

出力例 2

S_i や T_i が相異なるとは限らないことに注意してください。

入力例 3

4
1 2 3 4
1 2 4 7

出力例 3

あるすぬけくんが同時刻に複数の宝石の受け渡しをする可能性があること、特に高橋くんとすぬけくんの両方から同時に宝石を貰う可能性があることに注意してください。

入力例 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

出力例 4

Score : 300 points

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

1 \leq N \leq 200000
1 \leq S_i,T_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
S_1 S_2 \ldots S_N
T_1 T_2 \ldots T_N

Output

Print N lines. The i-th line (1 \leq i \leq N) should contain the time when Snuke i receives a gem for the first time.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4