AtCoder Daily Training MEDIUM 2024/09/24 19:30start

C - Nice Grid

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

次の図に示す、各マスが黒または白に塗られた縦 15 行 \times 横 15 列のグリッドにおいて、上から R 行目、左から C 列目のマスが何色かを出力して下さい。

制約

1 \leq R, C \leq 15
R, C は整数

入力

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

R C

出力

図のグリッドにおいて上から R 行目、左から C 列目のマスが黒色の場合は black と、白色の場合は white と出力せよ。ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

3 5

出力例 1

black

図のグリッドにおいて上から 3 行目、左から 5 列目のマスは黒色です。よって、black と出力します。

入力例 2

4 5

出力例 2

white

図のグリッドにおいて上から 4 行目、左から 5 列目のマスは白色です。よって、white と出力します。

Score : 200 points

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

1 \leq R, C \leq 15
R and C are integers.

Input

Input is given from Standard Input in the following format:

R C

Output

In the grid above, if the color of the cell at the R-th row from the top and C-th column from the left is black, then print black; if the cell is white, then print white. Note that the judge is case-sensitive.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

D - 11/11

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 国では、1 年が N か月からなる暦を使っています。 i 月 (1\leq i\leq N) は、i 月 1 日から i 月 D _ i 日までの D _ i 日からなります。

AtCoder 国において、1 年のうち日付がゾロ目になる日が何日あるか求めてください。

ただし、i 月 j 日 (1\leq i\leq N,1\leq j\leq D _ i) の日付がゾロ目になるとは、1 種類の数字だけを用いて i と j を十進法で表すことができることをいいます。

制約

1\leq N\leq100
1\leq D _ i\leq100\ (1\leq i\leq N)
入力はすべて整数

入力

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

N
D _ 1 D _ 2 \ldots D _ N

出力

答えを出力せよ。

入力例 1

12
31 29 31 30 31 30 31 31 30 31 30 31

出力例 1

AtCoder 国では、 1 月 1 日、1 月 11 日、2 月 2 日、2 月 22 日、3 月 3 日、4 月 4 日、5 月 5 日、6 月 6 日、7 月 7 日、8 月 8 日、9 月 9 日、11 月 1 日、11 月 11 日の合計 13 日の日付がゾロ目になります。

入力例 2

10
10 1 2 3 4 5 6 7 8 100

出力例 2

AtCoder 国では、1 月 1 日のみが日付がゾロ目になります。

入力例 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

出力例 3

Score : 200 points

Problem Statement

AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.

How many days in a year of AtCoder have "repdigits" dates?

Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.

Constraints

1\leq N\leq100
1\leq D _ i\leq100\ (1\leq i\leq N)
All input values are integers.

Input

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

N
D _ 1 D _ 2 \ldots D _ N

Output

Print the answer.

Sample Input 1

12
31 29 31 30 31 30 31 31 30 31 30 31

Sample Output 1

In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.

Sample Input 2

10
10 1 2 3 4 5 6 7 8 100

Sample Output 2

In AtCoder Kingdom, only January 1 has a repdigit date.

Sample Input 3

30
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

Sample Output 3

E - Robot Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

子供と大人があわせて N 人います。i 番目の人の体重は W_i です。
それぞれの人が子供か大人かは、0 と 1 からなる長さ N の文字列 S によって表され、
S の i 文字目が 0 であるとき i 番目の人が子供であることを、1 であるとき i 番目の人が大人であることをさします。

ロボットである高橋君に対して実数 X を設定すると、高橋君はそれぞれの人に対して、体重が X 未満なら子供、X 以上なら大人と判定します。
実数 X に対してf(X) を、高橋君に X を設定したときに N 人のうち子供か大人かを正しく判定できる人数で定めます。

X が実数全体を動くとき、f(X) の最大値を求めてください。

制約

1\leq N\leq 2\times 10^5
S は 0 と 1 からなる長さ N の文字列
1\leq W_i\leq 10^9
N,W_i は整数

入力

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

N
S
W_1 W_2 \ldots W_N

出力

f(X) の最大値を整数で一行に出力せよ。

入力例 1

5
10101
60 45 30 40 80

出力例 1

X=50 と設定すると、高橋君は 2,3,4 番目の人を子供、 1,5 番目の人を大人と判定します。
実際には 2,4 番目の人が子供、 1,3,5 番目の人が大人であるので、このとき、1,2,4,5 番目の合計 4 人に対して正しく判定できています。よって、f(50)=4 です。

5 人全員に対して正しく判定できるような X は存在しないのでこのときが最大です。よって、4 を出力します。

入力例 2

3
000
1 2 3

出力例 2

例えば、X=10 とすると最大値 f(10)=3 を達成します。
全員が大人、または全員が子供である可能性もあることに注意してください。

入力例 3

5
10101
60 50 50 50 60

出力例 3

例えば、X=55 とすると最大値 f(55)=4 を達成します。
同じ体重の人が複数人存在する可能性もあることに注意してください。

Score : 300 points

Problem Statement

There are N people, each of whom is either a child or an adult. The i-th person has a weight of W_i.
Whether each person is a child or an adult is specified by a string S of length N consisting of 0 and 1.
If the i-th character of S is 0, then the i-th person is a child; if it is 1, then the i-th person is an adult.

When Takahashi the robot is given a real number X, Takahashi judges a person with a weight less than X to be a child and a person with a weight more than or equal to X to be an adult.
For a real value X, let f(X) be the number of people whom Takahashi correctly judges whether they are children or adults.

Find the maximum value of f(X) for all real values of X.

Constraints

1\leq N\leq 2\times 10^5
S is a string of length N consisting of 0 and 1.
1\leq W_i\leq 10^9
N and W_i are integers.

Input

Input is given from Standard Input in the following format:

N
S
W_1 W_2 \ldots W_N

Output

Print the maximum value of f(X) as an integer in a single line.

Sample Input 1

5
10101
60 45 30 40 80

Sample Output 1

When Takahashi is given X=50, it judges the 2-nd, 3-rd, and 4-th people to be children and the 1-st and 5-th to be adults.
In reality, the 2-nd and 4-th are children, and the 1-st, 3-rd, and 5-th are adults, so the 1-st, 2-nd, 4-th, and 5-th people are correctly judged. Thus, f(50)=4.

This is the maximum since there is no X that judges correctly for all 5 people. Thus, 4 should be printed.

Sample Input 2

3
000
1 2 3

Sample Output 2

For example, X=10 achieves the maximum value f(10)=3.
Note that the people may be all children or all adults.

Sample Input 3

5
10101
60 50 50 50 60

Sample Output 3

For example, X=55 achieves the maximum value f(55)=4.
Note that there may be multiple people with the same weight.

F - Socks

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 枚の靴下があります。i 枚目の靴下の色は A_i です。

あなたは以下の操作をできるだけ多い回数行いたいです。最大で何回行うことができますか？

まだペアになっていない靴下の中から同じ色の靴下を 2 枚選んでペアにする。

制約

1\leq N \leq 5\times 10^5
1\leq A_i \leq 10^9
入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

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

入力例 1

6
4 1 7 4 1 4

出力例 1

以下のようにして、2 回の操作を行うことができます。

色が 1 である靴下を 2 枚選んでペアにする。
色が 4 である靴下を 2 枚選んでペアにする。

このとき、色が 4 である靴下と 7 である靴下が 1 枚ずつ残るため、これ以上操作はできません。また、どのように操作をしても 3 回以上操作を行うことはできないため、2 を出力します。

入力例 2

1
158260522

出力例 2

入力例 3

10
295 2 29 295 29 2 29 295 2 29

出力例 3

Score : 300 points

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

Choose two same-colored socks that are not paired yet, and pair them.

Constraints

1\leq N \leq 5\times 10^5
1\leq A_i \leq 10^9
All values in the input are integers.

Input

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

N
A_1 A_2 \dots A_N

Output

Print an integer representing the answer.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

You can do the operation twice as follows.

Choose two socks with the color 1 and pair them.
Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

G - Attend Many Events

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

AtCoder Land には N 個の地点と M 個の道があります。i 個目の道は地点 a_i と b_i を双方向に結び、通過するのに d_i 分かかります。

これから、AtCoder Land で K 個のイベントが開催されます。i 個目のイベントに参加するには、時刻 t_i 分に地点 c_i にいる必要があります。イベントにかかる時間は 0 分です。

あなたは、時刻 0 分に地点 1 にいます。適切に行動したとき、最大で何個のイベントに参加できるか求めてください。

制約

1 \leq N \leq 1000
0 \leq M \leq 1000
1 \leq K \leq 1000
1 \leq a_i < b_i \leq N
i \neq j なら (a_i, b_i) \neq (a_j, b_j)
1 \leq d_i \leq 10^9
1 \leq c_i \leq N
1 \leq t_i \leq 10^9
i \neq j なら (c_i,t_i) \neq (c_j,t_j)
入力はすべて整数

入力

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

N M K
a_1 b_1 d_1
a_2 b_2 d_2
\vdots
a_M b_M d_M
c_1 t_1
c_2 t_2
\vdots
c_K t_K

出力

答えを出力せよ。

入力例 1

出力例 1

たとえば、次のように行動することで、2 つのイベントに参加することができます。

はじめ、時刻 0 分に地点 1 にいる
道 1 を通って時刻 1 分に地点 2 に到着する
時刻 2 分に地点 2 でイベント 2 に参加する
道 1 を通って時刻 3 分に地点 1 に到着する
道 2 を通って時刻 6 分に地点 3 に到着する
時刻 7 分に地点 3 でイベント 3 に参加する

3 つ以上のイベントに参加することはできないので、答えは 2 です。

入力例 2

1 0 2
1 1
1 100

出力例 2

道が存在しないため、地点 1 から動くことはできませんが、地点 1 で開催される 2 つのイベントに参加することができます。

入力例 3

5 8 10
1 2 149622151
1 4 177783960
4 5 118947237
1 3 33222944
1 5 295060863
3 5 110881471
2 3 34104208
3 4 273071547
2 650287940
4 839296263
3 462224593
1 492601449
4 384836991
1 191890310
5 576823355
3 782177068
3 404011431
1 818008580