AtCoder Daily Training EASY 2026/04/16 18:00start

A - World Cup

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

あるスポーツ大会は西暦年を 4 で割った余りが 2 である年の 6 月に開催されます。
現在が西暦 Y 年の 1 月である時、このスポーツ大会が次に開催されるのは西暦何年になるかを求めてください。

制約

2000 \leq Y \leq 3000
Y は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

2022 は 4 で割った余りが 2 なので、現在が西暦 2022 年の 1 月である時、次の開催は同年の 6 月です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 100 points

Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

2000 \leq Y \leq 3000
Y is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

B - 1-2-4 Test

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 問の問題からなる試験があり、それぞれの問題の配点は 1 点、2 点、4 点でした。

高橋君、青木君、すぬけ君の 3 人がこの試験を受け、高橋君は A 点、青木君は B 点を取りました。

すぬけ君は、高橋君と青木君のうち少なくとも一方が解けた問題は解け、 2 人とも解けなかった問題は解けませんでした。

すぬけ君の点数を求めてください。

ただし、この問題の制約下で、すぬけ君の点数は一意に定まる事が証明できます。

制約

0\leq A,B \leq 7
A,B は整数

入力

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

A B

出力

すぬけ君の点数を整数で出力せよ。

入力例 1

1 2

出力例 1

高橋君は 1 点を取った事から、 1 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。
同様に、青木君は 2 点を取った事から、 2 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。

よって、すぬけ君は 1 点の問題と 2 点の問題を正解し、高橋君と青木君がともに解けなかった 4 点の問題はすぬけ君も解けなかったことになるので、3 点を取ったことがわかります。よって、3 を出力します。

入力例 2

5 3

出力例 2

高橋君は 5 点を取った事から、 1 点の問題と 4 点の問題を正解し、 2 点の問題は解けなかったことがわかります。
同様に、青木君は 3 点を取った事から、 1 点の問題と 2 点の問題を正解し、 4 点の問題は解けなかったことがわかります。

よって、3 問すべてについて、高橋君と青木君の少なくとも一方が正解しているため、すぬけ君はすベての問題に正解し、7 点を取ったことがわかります。よって、7 を出力します。

入力例 3

0 0

出力例 3

高橋君と青木君は 2 人ともいずれの問題も解けていません。よって、すぬけ君もいずれの問題も解けておらず、 0 を出力します。

Score : 100 points

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

0\leq A,B \leq 7
A and B are integers.

Input

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

A B

Output

Print Snuke's score as an integer.

Sample Input 1

1 2

Sample Output 1

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

C - chess960

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。
K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

S は長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。また、K は 2 つの R の間にあります。よって条件を満たします。

入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。

入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.
K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

Output

Print Yes if S satisfies the conditions; print No otherwise.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

D - Digit Sum

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 n の桁和を、 n を十進法で表したときの各桁の和と定めます。例えば 2026 の桁和は 2+0+2+6=10 です。

N 以下の正整数のうち、桁和が K であるものの個数を求めてください。

制約

1\leq N,K \leq 10^5
入力は全て整数

入力

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

N K

出力

答えを出力せよ。

入力例 1

30 4

出力例 1

30 以下の正整数のうち、桁和が 4 であるものは、4,13,22 の 3 個です。

入力例 2

2026 10

出力例 2

入力例 3

99999 45

出力例 3

Score : 200 points

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits when n is represented in decimal. For example, the digit sum of 2026 is 2+0+2+6=10.

Find the number of positive integers not exceeding N whose digit sum is K.

Constraints

1\leq N,K \leq 10^5
All input values are integers.

Input

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

N K

Output

Output the answer.

Sample Input 1

30 4

Sample Output 1

Among the positive integers not exceeding 30, there are three integers whose digit sum is 4: 4,13,22.

Sample Input 2

2026 10

Sample Output 2

Sample Input 3

99999 45

Sample Output 3

E - ~

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。

A の長さ |A| は 4 以上である
A_1 < A_2 である
A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である　
A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である

数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_N) が与えられます。P の連続部分列であってチルダ型である数列の個数を求めてください。

制約

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) を並べ替えて得られる数列
入力される値はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

6
1 3 6 4 2 5

出力例 1

数列 (1, 3, 6, 4, 2, 5) の連続部分列のうちチルダ型であるものは (3, 6, 4, 2, 5), (1, 3, 6, 4, 2, 5) の 2 つのみです。

入力例 2

6
1 2 3 4 5 6

出力例 2

入力例 3

12
11 3 8 9 5 2 10 4 1 6 12 7

出力例 3

Score : 350 points

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

The length |A| is at least 4.
A_1 < A_2.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

Sample Input 3

12
11 3 8 9 5 2 10 4 1 6 12 7